← Back to branch summary

~bzr-pqm/bzr/bzr.dev

« back to all changes in this revision

Viewing changes to bzrlib/btree_index.py

  • Committer: Canonical.com Patch Queue Manager
  • Date: 2010-09-29 22:03:03 UTC
  • mfrom: (5416.2.6 jam-integration)
  • Revision ID: pqm@pqm.ubuntu.com-20100929220303-cr95h8iwtggco721
(mbp) Add 'break-lock --force'

Show diffs side-by-side

added added

removed removed

Lines of Context:
bzrlib/btree_index.py
33
33
    osutils,
34
34
    static_tuple,
35
35
    trace,
 
36
    transport,
36
37
    )
37
38
from bzrlib.index import _OPTION_NODE_REFS, _OPTION_KEY_ELEMENTS, _OPTION_LEN
38
 
from bzrlib.transport import get_transport
39
39
 
40
40
 
41
41
_BTSIGNATURE = "B+Tree Graph Index 2\n"
193
193
            new_backing_file, size = self._spill_mem_keys_without_combining()
194
194
        # Note: The transport here isn't strictly needed, because we will use
195
195
        #       direct access to the new_backing._file object
196
 
        new_backing = BTreeGraphIndex(get_transport('.'), '<temp>', size)
 
196
        new_backing = BTreeGraphIndex(transport.get_transport('.'),
 
197
                                      '<temp>', size)
197
198
        # GC will clean up the file
198
199
        new_backing._file = new_backing_file
199
200
        if self._combine_backing_indices:
567
568
                    else:
568
569
                        # yield keys
569
570
                        for value in key_dict.itervalues():
570
 
                            yield (self, ) + value
 
571
                            yield (self, ) + tuple(value)
571
572
            else:
572
573
                yield (self, ) + key_dict
573
574
 
601
602
        """In memory index's have no known corruption at the moment."""
602
603
 
603
604
 
604
 
class _LeafNode(object):
 
605
class _LeafNode(dict):
605
606
    """A leaf node for a serialised B+Tree index."""
606
607
 
607
 
    __slots__ = ('keys', 'min_key', 'max_key')
 
608
    __slots__ = ('min_key', 'max_key', '_keys')
608
609
 
609
610
    def __init__(self, bytes, key_length, ref_list_length):
610
611
        """Parse bytes to create a leaf node object."""
616
617
            self.max_key = key_list[-1][0]
617
618
        else:
618
619
            self.min_key = self.max_key = None
619
 
        self.keys = dict(key_list)
 
620
        super(_LeafNode, self).__init__(key_list)
 
621
        self._keys = dict(self)
 
622
 
 
623
    def all_items(self):
 
624
        """Return a sorted list of (key, (value, refs)) items"""
 
625
        items = self.items()
 
626
        items.sort()
 
627
        return items
 
628
 
 
629
    def all_keys(self):
 
630
        """Return a sorted list of all keys."""
 
631
        keys = self.keys()
 
632
        keys.sort()
 
633
        return keys
620
634
 
621
635
 
622
636
class _InternalNode(object):
647
661
    memory except when very large walks are done.
648
662
    """
649
663
 
650
 
    def __init__(self, transport, name, size, unlimited_cache=False):
 
664
    def __init__(self, transport, name, size, unlimited_cache=False,
 
665
                 offset=0):
651
666
        """Create a B+Tree index object on the index name.
652
667
 
653
668
        :param transport: The transport to read data for the index from.
660
675
        :param unlimited_cache: If set to True, then instead of using an
661
676
            LRUCache with size _NODE_CACHE_SIZE, we will use a dict and always
662
677
            cache all leaf nodes.
 
678
        :param offset: The start of the btree index data isn't byte 0 of the
 
679
            file. Instead it starts at some point later.
663
680
        """
664
681
        self._transport = transport
665
682
        self._name = name
667
684
        self._file = None
668
685
        self._recommended_pages = self._compute_recommended_pages()
669
686
        self._root_node = None
 
687
        self._base_offset = offset
 
688
        self._leaf_factory = _LeafNode
670
689
        # Default max size is 100,000 leave values
671
690
        self._leaf_value_cache = None # lru_cache.LRUCache(100*1000)
672
691
        if unlimited_cache:
945
964
        """Cache directly from key => value, skipping the btree."""
946
965
        if self._leaf_value_cache is not None:
947
966
            for node in nodes.itervalues():
948
 
                for key, value in node.keys.iteritems():
 
967
                for key, value in node.all_items():
949
968
                    if key in self._leaf_value_cache:
950
969
                        # Don't add the rest of the keys, we've seen this node
951
970
                        # before.
975
994
        if self._row_offsets[-1] == 1:
976
995
            # There is only the root node, and we read that via key_count()
977
996
            if self.node_ref_lists:
978
 
                for key, (value, refs) in sorted(self._root_node.keys.items()):
 
997
                for key, (value, refs) in self._root_node.all_items():
979
998
                    yield (self, key, value, refs)
980
999
            else:
981
 
                for key, (value, refs) in sorted(self._root_node.keys.items()):
 
1000
                for key, (value, refs) in self._root_node.all_items():
982
1001
                    yield (self, key, value)
983
1002
            return
984
1003
        start_of_leaves = self._row_offsets[-2]
994
1013
        # for spilling index builds to disk.
995
1014
        if self.node_ref_lists:
996
1015
            for _, node in nodes:
997
 
                for key, (value, refs) in sorted(node.keys.items()):
 
1016
                for key, (value, refs) in node.all_items():
998
1017
                    yield (self, key, value, refs)
999
1018
        else:
1000
1019
            for _, node in nodes:
1001
 
                for key, (value, refs) in sorted(node.keys.items()):
 
1020
                for key, (value, refs) in node.all_items():
1002
1021
                    yield (self, key, value)
1003
1022
 
1004
1023
    @staticmethod
1165
1184
                continue
1166
1185
            node = nodes[node_index]
1167
1186
            for next_sub_key in sub_keys:
1168
 
                if next_sub_key in node.keys:
1169
 
                    value, refs = node.keys[next_sub_key]
 
1187
                if next_sub_key in node:
 
1188
                    value, refs = node[next_sub_key]
1170
1189
                    if self.node_ref_lists:
1171
1190
                        yield (self, next_sub_key, value, refs)
1172
1191
                    else:
1240
1259
            # sub_keys is all of the keys we are looking for that should exist
1241
1260
            # on this page, if they aren't here, then they won't be found
1242
1261
            node = nodes[node_index]
1243
 
            node_keys = node.keys
1244
1262
            parents_to_check = set()
1245
1263
            for next_sub_key in sub_keys:
1246
 
                if next_sub_key not in node_keys:
 
1264
                if next_sub_key not in node:
1247
1265
                    # This one is just not present in the index at all
1248
1266
                    missing_keys.add(next_sub_key)
1249
1267
                else:
1250
 
                    value, refs = node_keys[next_sub_key]
 
1268
                    value, refs = node[next_sub_key]
1251
1269
                    parent_keys = refs[ref_list_num]
1252
1270
                    parent_map[next_sub_key] = parent_keys
1253
1271
                    parents_to_check.update(parent_keys)
1260
1278
            while parents_to_check:
1261
1279
                next_parents_to_check = set()
1262
1280
                for key in parents_to_check:
1263
 
                    if key in node_keys:
1264
 
                        value, refs = node_keys[key]
 
1281
                    if key in node:
 
1282
                        value, refs = node[key]
1265
1283
                        parent_keys = refs[ref_list_num]
1266
1284
                        parent_map[key] = parent_keys
1267
1285
                        next_parents_to_check.update(parent_keys)
1494
1512
        # list of (offset, length) regions of the file that should, evenually
1495
1513
        # be read in to data_ranges, either from 'bytes' or from the transport
1496
1514
        ranges = []
 
1515
        base_offset = self._base_offset
1497
1516
        for index in nodes:
1498
 
            offset = index * _PAGE_SIZE
 
1517
            offset = (index * _PAGE_SIZE)
1499
1518
            size = _PAGE_SIZE
1500
1519
            if index == 0:
1501
1520
                # Root node - special case
1505
1524
                    # The only case where we don't know the size, is for very
1506
1525
                    # small indexes. So we read the whole thing
1507
1526
                    bytes = self._transport.get_bytes(self._name)
1508
 
                    self._size = len(bytes)
 
1527
                    num_bytes = len(bytes)
 
1528
                    self._size = num_bytes - base_offset
1509
1529
                    # the whole thing should be parsed out of 'bytes'
1510
 
                    ranges.append((0, len(bytes)))
 
1530
                    ranges = [(start, min(_PAGE_SIZE, num_bytes - start))
 
1531
                        for start in xrange(base_offset, num_bytes, _PAGE_SIZE)]
1511
1532
                    break
1512
1533
            else:
1513
1534
                if offset > self._size:
1515
1536
                                         ' of the file %s > %s'
1516
1537
                                         % (offset, self._size))
1517
1538
                size = min(size, self._size - offset)
1518
 
            ranges.append((offset, size))
 
1539
            ranges.append((base_offset + offset, size))
1519
1540
        if not ranges:
1520
1541
            return
1521
1542
        elif bytes is not None:
1522
1543
            # already have the whole file
1523
 
            data_ranges = [(start, bytes[start:start+_PAGE_SIZE])
1524
 
                           for start in xrange(0, len(bytes), _PAGE_SIZE)]
 
1544
            data_ranges = [(start, bytes[start:start+size])
 
1545
                           for start, size in ranges]
1525
1546
        elif self._file is None:
1526
1547
            data_ranges = self._transport.readv(self._name, ranges)
1527
1548
        else:
1530
1551
                self._file.seek(offset)
1531
1552
                data_ranges.append((offset, self._file.read(size)))
1532
1553
        for offset, data in data_ranges:
 
1554
            offset -= base_offset
1533
1555
            if offset == 0:
1534
1556
                # extract the header
1535
1557
                offset, data = self._parse_header_from_bytes(data)
1537
1559
                    continue
1538
1560
            bytes = zlib.decompress(data)
1539
1561
            if bytes.startswith(_LEAF_FLAG):
1540
 
                node = _LeafNode(bytes, self._key_length, self.node_ref_lists)
 
1562
                node = self._leaf_factory(bytes, self._key_length,
 
1563
                                          self.node_ref_lists)
1541
1564
            elif bytes.startswith(_INTERNAL_FLAG):
1542
1565
                node = _InternalNode(bytes)
1543
1566
            else:
1562
1585
            pass
1563
1586
 
1564
1587
 
 
1588
_gcchk_factory = _LeafNode
 
1589
 
1565
1590
try:
1566
1591
    from bzrlib import _btree_serializer_pyx as _btree_serializer
 
1592
    _gcchk_factory = _btree_serializer._parse_into_chk
1567
1593
except ImportError, e:
1568
1594
    osutils.failed_to_load_extension(e)
1569
1595
    from bzrlib import _btree_serializer_py as _btree_serializer