← 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-01 08:02:42 UTC
  • mfrom: (5390.3.3 faster-revert-593560)
  • Revision ID: pqm@pqm.ubuntu.com-20100901080242-esg62ody4frwmy66
(spiv) Avoid repeatedly calling self.target.all_file_ids() in
 InterTree.iter_changes. (Andrew Bennetts)

Show diffs side-by-side

added added

removed removed

Lines of Context:
bzrlib/btree_index.py
602
602
        """In memory index's have no known corruption at the moment."""
603
603
 
604
604
 
605
 
class _LeafNode(object):
 
605
class _LeafNode(dict):
606
606
    """A leaf node for a serialised B+Tree index."""
607
607
 
608
 
    __slots__ = ('keys', 'min_key', 'max_key')
 
608
    __slots__ = ('min_key', 'max_key', '_keys')
609
609
 
610
610
    def __init__(self, bytes, key_length, ref_list_length):
611
611
        """Parse bytes to create a leaf node object."""
617
617
            self.max_key = key_list[-1][0]
618
618
        else:
619
619
            self.min_key = self.max_key = None
620
 
        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
621
634
 
622
635
 
623
636
class _InternalNode(object):
672
685
        self._recommended_pages = self._compute_recommended_pages()
673
686
        self._root_node = None
674
687
        self._base_offset = offset
 
688
        self._leaf_factory = _LeafNode
675
689
        # Default max size is 100,000 leave values
676
690
        self._leaf_value_cache = None # lru_cache.LRUCache(100*1000)
677
691
        if unlimited_cache:
950
964
        """Cache directly from key => value, skipping the btree."""
951
965
        if self._leaf_value_cache is not None:
952
966
            for node in nodes.itervalues():
953
 
                for key, value in node.keys.iteritems():
 
967
                for key, value in node.all_items():
954
968
                    if key in self._leaf_value_cache:
955
969
                        # Don't add the rest of the keys, we've seen this node
956
970
                        # before.
980
994
        if self._row_offsets[-1] == 1:
981
995
            # There is only the root node, and we read that via key_count()
982
996
            if self.node_ref_lists:
983
 
                for key, (value, refs) in sorted(self._root_node.keys.items()):
 
997
                for key, (value, refs) in self._root_node.all_items():
984
998
                    yield (self, key, value, refs)
985
999
            else:
986
 
                for key, (value, refs) in sorted(self._root_node.keys.items()):
 
1000
                for key, (value, refs) in self._root_node.all_items():
987
1001
                    yield (self, key, value)
988
1002
            return
989
1003
        start_of_leaves = self._row_offsets[-2]
999
1013
        # for spilling index builds to disk.
1000
1014
        if self.node_ref_lists:
1001
1015
            for _, node in nodes:
1002
 
                for key, (value, refs) in sorted(node.keys.items()):
 
1016
                for key, (value, refs) in node.all_items():
1003
1017
                    yield (self, key, value, refs)
1004
1018
        else:
1005
1019
            for _, node in nodes:
1006
 
                for key, (value, refs) in sorted(node.keys.items()):
 
1020
                for key, (value, refs) in node.all_items():
1007
1021
                    yield (self, key, value)
1008
1022
 
1009
1023
    @staticmethod
1170
1184
                continue
1171
1185
            node = nodes[node_index]
1172
1186
            for next_sub_key in sub_keys:
1173
 
                if next_sub_key in node.keys:
1174
 
                    value, refs = node.keys[next_sub_key]
 
1187
                if next_sub_key in node:
 
1188
                    value, refs = node[next_sub_key]
1175
1189
                    if self.node_ref_lists:
1176
1190
                        yield (self, next_sub_key, value, refs)
1177
1191
                    else:
1245
1259
            # sub_keys is all of the keys we are looking for that should exist
1246
1260
            # on this page, if they aren't here, then they won't be found
1247
1261
            node = nodes[node_index]
1248
 
            node_keys = node.keys
1249
1262
            parents_to_check = set()
1250
1263
            for next_sub_key in sub_keys:
1251
 
                if next_sub_key not in node_keys:
 
1264
                if next_sub_key not in node:
1252
1265
                    # This one is just not present in the index at all
1253
1266
                    missing_keys.add(next_sub_key)
1254
1267
                else:
1255
 
                    value, refs = node_keys[next_sub_key]
 
1268
                    value, refs = node[next_sub_key]
1256
1269
                    parent_keys = refs[ref_list_num]
1257
1270
                    parent_map[next_sub_key] = parent_keys
1258
1271
                    parents_to_check.update(parent_keys)
1265
1278
            while parents_to_check:
1266
1279
                next_parents_to_check = set()
1267
1280
                for key in parents_to_check:
1268
 
                    if key in node_keys:
1269
 
                        value, refs = node_keys[key]
 
1281
                    if key in node:
 
1282
                        value, refs = node[key]
1270
1283
                        parent_keys = refs[ref_list_num]
1271
1284
                        parent_map[key] = parent_keys
1272
1285
                        next_parents_to_check.update(parent_keys)
1546
1559
                    continue
1547
1560
            bytes = zlib.decompress(data)
1548
1561
            if bytes.startswith(_LEAF_FLAG):
1549
 
                node = _LeafNode(bytes, self._key_length, self.node_ref_lists)
 
1562
                node = self._leaf_factory(bytes, self._key_length,
 
1563
                                          self.node_ref_lists)
1550
1564
            elif bytes.startswith(_INTERNAL_FLAG):
1551
1565
                node = _InternalNode(bytes)
1552
1566
            else:
1571
1585
            pass
1572
1586
 
1573
1587
 
 
1588
_gcchk_factory = _LeafNode
 
1589
 
1574
1590
try:
1575
1591
    from bzrlib import _btree_serializer_pyx as _btree_serializer
 
1592
    _gcchk_factory = _btree_serializer._parse_into_chk
1576
1593
except ImportError, e:
1577
1594
    osutils.failed_to_load_extension(e)
1578
1595
    from bzrlib import _btree_serializer_py as _btree_serializer