← Back to branch summary

~bzr-pqm/bzr/bzr.dev

« back to all changes in this revision

Viewing changes to bzrlib/btree_index.py

  • Committer: John Arbash Meinel
  • Date: 2010-08-30 21:23:49 UTC
  • mto: This revision was merged to the branch mainline in revision 5398.
  • Revision ID: john@arbash-meinel.com-20100830212349-figt9yz2cic6hy68
Remove the 'false' invocation.

Show diffs side-by-side

added added

removed removed

Lines of Context:
bzrlib/btree_index.py
1
 
# Copyright (C) 2008 Canonical Ltd
 
1
# Copyright (C) 2008, 2009, 2010 Canonical Ltd
2
2
#
3
3
# This program is free software; you can redistribute it and/or modify
4
4
# it under the terms of the GNU General Public License as published by
17
17
 
18
18
"""B+Tree indices"""
19
19
 
 
20
import cStringIO
20
21
from bisect import bisect_right
21
22
import math
22
23
import tempfile
30
31
    index,
31
32
    lru_cache,
32
33
    osutils,
 
34
    static_tuple,
33
35
    trace,
 
36
    transport,
34
37
    )
35
38
from bzrlib.index import _OPTION_NODE_REFS, _OPTION_KEY_ELEMENTS, _OPTION_LEN
36
 
from bzrlib.transport import get_transport
37
39
 
38
40
 
39
41
_BTSIGNATURE = "B+Tree Graph Index 2\n"
60
62
    def __init__(self):
61
63
        """Create a _BuilderRow."""
62
64
        self.nodes = 0
63
 
        self.spool = tempfile.TemporaryFile()
 
65
        self.spool = None# tempfile.TemporaryFile(prefix='bzr-index-row-')
64
66
        self.writer = None
65
67
 
66
68
    def finish_node(self, pad=True):
67
69
        byte_lines, _, padding = self.writer.finish()
68
70
        if self.nodes == 0:
 
71
            self.spool = cStringIO.StringIO()
69
72
            # padded note:
70
73
            self.spool.write("\x00" * _RESERVED_HEADER_BYTES)
 
74
        elif self.nodes == 1:
 
75
            # We got bigger than 1 node, switch to a temp file
 
76
            spool = tempfile.TemporaryFile(prefix='bzr-index-row-')
 
77
            spool.write(self.spool.getvalue())
 
78
            self.spool = spool
71
79
        skipped_bytes = 0
72
80
        if not pad and padding:
73
81
            del byte_lines[-1]
152
160
        :param value: The value to associate with the key. It may be any
153
161
            bytes as long as it does not contain \0 or \n.
154
162
        """
 
163
        # Ensure that 'key' is a StaticTuple
 
164
        key = static_tuple.StaticTuple.from_sequence(key).intern()
155
165
        # we don't care about absent_references
156
166
        node_refs, _ = self._check_key_ref_value(key, references, value)
157
167
        if key in self._nodes:
158
168
            raise errors.BadIndexDuplicateKey(key, self)
159
 
        self._nodes[key] = (node_refs, value)
160
 
        self._keys.add(key)
 
169
        self._nodes[key] = static_tuple.StaticTuple(node_refs, value)
161
170
        if self._nodes_by_key is not None and self._key_length > 1:
162
171
            self._update_nodes_by_key(key, value, node_refs)
163
 
        if len(self._keys) < self._spill_at:
 
172
        if len(self._nodes) < self._spill_at:
164
173
            return
165
174
        self._spill_mem_keys_to_disk()
166
175
 
182
191
             backing_pos) = self._spill_mem_keys_and_combine()
183
192
        else:
184
193
            new_backing_file, size = self._spill_mem_keys_without_combining()
185
 
        dir_path, base_name = osutils.split(new_backing_file.name)
186
194
        # Note: The transport here isn't strictly needed, because we will use
187
195
        #       direct access to the new_backing._file object
188
 
        new_backing = BTreeGraphIndex(get_transport(dir_path),
189
 
                                      base_name, size)
 
196
        new_backing = BTreeGraphIndex(transport.get_transport('.'),
 
197
                                      '<temp>', size)
190
198
        # GC will clean up the file
191
199
        new_backing._file = new_backing_file
192
200
        if self._combine_backing_indices:
197
205
                self._backing_indices[backing_pos] = None
198
206
        else:
199
207
            self._backing_indices.append(new_backing)
200
 
        self._keys = set()
201
208
        self._nodes = {}
202
209
        self._nodes_by_key = None
203
210
 
379
386
        for row in reversed(rows):
380
387
            pad = (type(row) != _LeafBuilderRow)
381
388
            row.finish_node(pad=pad)
382
 
        result = tempfile.NamedTemporaryFile(prefix='bzr-index-')
383
389
        lines = [_BTSIGNATURE]
384
390
        lines.append(_OPTION_NODE_REFS + str(self.reference_lists) + '\n')
385
391
        lines.append(_OPTION_KEY_ELEMENTS + str(self._key_length) + '\n')
386
392
        lines.append(_OPTION_LEN + str(key_count) + '\n')
387
393
        row_lengths = [row.nodes for row in rows]
388
394
        lines.append(_OPTION_ROW_LENGTHS + ','.join(map(str, row_lengths)) + '\n')
 
395
        if row_lengths and row_lengths[-1] > 1:
 
396
            result = tempfile.NamedTemporaryFile(prefix='bzr-index-')
 
397
        else:
 
398
            result = cStringIO.StringIO()
389
399
        result.writelines(lines)
390
400
        position = sum(map(len, lines))
391
401
        root_row = True
402
412
            # Special case the first node as it may be prefixed
403
413
            node = row.spool.read(_PAGE_SIZE)
404
414
            result.write(node[reserved:])
405
 
            result.write("\x00" * (reserved - position))
 
415
            if len(node) == _PAGE_SIZE:
 
416
                result.write("\x00" * (reserved - position))
406
417
            position = 0 # Only the root row actually has an offset
407
418
            copied_len = osutils.pumpfile(row.spool, result)
408
419
            if copied_len != (row.nodes - 1) * _PAGE_SIZE:
453
464
            efficient order for the index (keys iteration order in this case).
454
465
        """
455
466
        keys = set(keys)
456
 
        local_keys = keys.intersection(self._keys)
 
467
        # Note: We don't use keys.intersection() here. If you read the C api,
 
468
        #       set.intersection(other) special cases when other is a set and
 
469
        #       will iterate the smaller of the two and lookup in the other.
 
470
        #       It does *not* do this for any other type (even dict, unlike
 
471
        #       some other set functions.) Since we expect keys is generally <<
 
472
        #       self._nodes, it is faster to iterate over it in a list
 
473
        #       comprehension
 
474
        nodes = self._nodes
 
475
        local_keys = [key for key in keys if key in nodes]
457
476
        if self.reference_lists:
458
477
            for key in local_keys:
459
 
                node = self._nodes[key]
 
478
                node = nodes[key]
460
479
                yield self, key, node[1], node[0]
461
480
        else:
462
481
            for key in local_keys:
463
 
                node = self._nodes[key]
 
482
                node = nodes[key]
464
483
                yield self, key, node[1]
465
484
        # Find things that are in backing indices that have not been handled
466
485
        # yet.
549
568
                    else:
550
569
                        # yield keys
551
570
                        for value in key_dict.itervalues():
552
 
                            yield (self, ) + value
 
571
                            yield (self, ) + tuple(value)
553
572
            else:
554
573
                yield (self, ) + key_dict
555
574
 
576
595
 
577
596
        For InMemoryGraphIndex the estimate is exact.
578
597
        """
579
 
        return len(self._keys) + sum(backing.key_count() for backing in
 
598
        return len(self._nodes) + sum(backing.key_count() for backing in
580
599
            self._backing_indices if backing is not None)
581
600
 
582
601
    def validate(self):
583
602
        """In memory index's have no known corruption at the moment."""
584
603
 
585
604
 
586
 
class _LeafNode(object):
 
605
class _LeafNode(dict):
587
606
    """A leaf node for a serialised B+Tree index."""
588
607
 
589
 
    __slots__ = ('keys',)
 
608
    __slots__ = ('min_key', 'max_key', '_keys')
590
609
 
591
610
    def __init__(self, bytes, key_length, ref_list_length):
592
611
        """Parse bytes to create a leaf node object."""
593
612
        # splitlines mangles the \r delimiters.. don't use it.
594
 
        self.keys = dict(_btree_serializer._parse_leaf_lines(bytes,
595
 
            key_length, ref_list_length))
 
613
        key_list = _btree_serializer._parse_leaf_lines(bytes,
 
614
            key_length, ref_list_length)
 
615
        if key_list:
 
616
            self.min_key = key_list[0][0]
 
617
            self.max_key = key_list[-1][0]
 
618
        else:
 
619
            self.min_key = self.max_key = None
 
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
596
634
 
597
635
 
598
636
class _InternalNode(object):
608
646
    def _parse_lines(self, lines):
609
647
        nodes = []
610
648
        self.offset = int(lines[1][7:])
 
649
        as_st = static_tuple.StaticTuple.from_sequence
611
650
        for line in lines[2:]:
612
651
            if line == '':
613
652
                break
614
 
            nodes.append(tuple(map(intern, line.split('\0'))))
 
653
            nodes.append(as_st(map(intern, line.split('\0'))).intern())
615
654
        return nodes
616
655
 
617
656
 
622
661
    memory except when very large walks are done.
623
662
    """
624
663
 
625
 
    def __init__(self, transport, name, size):
 
664
    def __init__(self, transport, name, size, unlimited_cache=False,
 
665
                 offset=0):
626
666
        """Create a B+Tree index object on the index name.
627
667
 
628
668
        :param transport: The transport to read data for the index from.
632
672
            the initial read (to read the root node header) can be done
633
673
            without over-reading even on empty indices, and on small indices
634
674
            allows single-IO to read the entire index.
 
675
        :param unlimited_cache: If set to True, then instead of using an
 
676
            LRUCache with size _NODE_CACHE_SIZE, we will use a dict and always
 
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.
635
680
        """
636
681
        self._transport = transport
637
682
        self._name = name
639
684
        self._file = None
640
685
        self._recommended_pages = self._compute_recommended_pages()
641
686
        self._root_node = None
 
687
        self._base_offset = offset
 
688
        self._leaf_factory = _LeafNode
642
689
        # Default max size is 100,000 leave values
643
690
        self._leaf_value_cache = None # lru_cache.LRUCache(100*1000)
644
 
        self._leaf_node_cache = lru_cache.LRUCache(_NODE_CACHE_SIZE)
645
 
        # We could limit this, but even a 300k record btree has only 3k leaf
646
 
        # nodes, and only 20 internal nodes. So the default of 100 nodes in an
647
 
        # LRU would mean we always cache everything anyway, no need to pay the
648
 
        # overhead of LRU
649
 
        self._internal_node_cache = fifo_cache.FIFOCache(100)
 
691
        if unlimited_cache:
 
692
            self._leaf_node_cache = {}
 
693
            self._internal_node_cache = {}
 
694
        else:
 
695
            self._leaf_node_cache = lru_cache.LRUCache(_NODE_CACHE_SIZE)
 
696
            # We use a FIFO here just to prevent possible blowout. However, a
 
697
            # 300k record btree has only 3k leaf nodes, and only 20 internal
 
698
            # nodes. A value of 100 scales to ~100*100*100 = 1M records.
 
699
            self._internal_node_cache = fifo_cache.FIFOCache(100)
650
700
        self._key_count = None
651
701
        self._row_lengths = None
652
702
        self._row_offsets = None # Start of each row, [-1] is the end
684
734
                if start_of_leaves is None:
685
735
                    start_of_leaves = self._row_offsets[-2]
686
736
                if node_pos < start_of_leaves:
687
 
                    self._internal_node_cache.add(node_pos, node)
 
737
                    self._internal_node_cache[node_pos] = node
688
738
                else:
689
 
                    self._leaf_node_cache.add(node_pos, node)
 
739
                    self._leaf_node_cache[node_pos] = node
690
740
            found[node_pos] = node
691
741
        return found
692
742
 
831
881
            new_tips = next_tips
832
882
        return final_offsets
833
883
 
 
884
    def clear_cache(self):
 
885
        """Clear out any cached/memoized values.
 
886
 
 
887
        This can be called at any time, but generally it is used when we have
 
888
        extracted some information, but don't expect to be requesting any more
 
889
        from this index.
 
890
        """
 
891
        # Note that we don't touch self._root_node or self._internal_node_cache
 
892
        # We don't expect either of those to be big, and it can save
 
893
        # round-trips in the future. We may re-evaluate this if InternalNode
 
894
        # memory starts to be an issue.
 
895
        self._leaf_node_cache.clear()
 
896
 
834
897
    def external_references(self, ref_list_num):
835
898
        if self._root_node is None:
836
899
            self._get_root_node()
901
964
        """Cache directly from key => value, skipping the btree."""
902
965
        if self._leaf_value_cache is not None:
903
966
            for node in nodes.itervalues():
904
 
                for key, value in node.keys.iteritems():
 
967
                for key, value in node.all_items():
905
968
                    if key in self._leaf_value_cache:
906
969
                        # Don't add the rest of the keys, we've seen this node
907
970
                        # before.
931
994
        if self._row_offsets[-1] == 1:
932
995
            # There is only the root node, and we read that via key_count()
933
996
            if self.node_ref_lists:
934
 
                for key, (value, refs) in sorted(self._root_node.keys.items()):
 
997
                for key, (value, refs) in self._root_node.all_items():
935
998
                    yield (self, key, value, refs)
936
999
            else:
937
 
                for key, (value, refs) in sorted(self._root_node.keys.items()):
 
1000
                for key, (value, refs) in self._root_node.all_items():
938
1001
                    yield (self, key, value)
939
1002
            return
940
1003
        start_of_leaves = self._row_offsets[-2]
950
1013
        # for spilling index builds to disk.
951
1014
        if self.node_ref_lists:
952
1015
            for _, node in nodes:
953
 
                for key, (value, refs) in sorted(node.keys.items()):
 
1016
                for key, (value, refs) in node.all_items():
954
1017
                    yield (self, key, value, refs)
955
1018
        else:
956
1019
            for _, node in nodes:
957
 
                for key, (value, refs) in sorted(node.keys.items()):
 
1020
                for key, (value, refs) in node.all_items():
958
1021
                    yield (self, key, value)
959
1022
 
960
1023
    @staticmethod
1039
1102
            output.append(cur_out)
1040
1103
        return output
1041
1104
 
 
1105
    def _walk_through_internal_nodes(self, keys):
 
1106
        """Take the given set of keys, and find the corresponding LeafNodes.
 
1107
 
 
1108
        :param keys: An unsorted iterable of keys to search for
 
1109
        :return: (nodes, index_and_keys)
 
1110
            nodes is a dict mapping {index: LeafNode}
 
1111
            keys_at_index is a list of tuples of [(index, [keys for Leaf])]
 
1112
        """
 
1113
        # 6 seconds spent in miss_torture using the sorted() line.
 
1114
        # Even with out of order disk IO it seems faster not to sort it when
 
1115
        # large queries are being made.
 
1116
        keys_at_index = [(0, sorted(keys))]
 
1117
 
 
1118
        for row_pos, next_row_start in enumerate(self._row_offsets[1:-1]):
 
1119
            node_indexes = [idx for idx, s_keys in keys_at_index]
 
1120
            nodes = self._get_internal_nodes(node_indexes)
 
1121
 
 
1122
            next_nodes_and_keys = []
 
1123
            for node_index, sub_keys in keys_at_index:
 
1124
                node = nodes[node_index]
 
1125
                positions = self._multi_bisect_right(sub_keys, node.keys)
 
1126
                node_offset = next_row_start + node.offset
 
1127
                next_nodes_and_keys.extend([(node_offset + pos, s_keys)
 
1128
                                           for pos, s_keys in positions])
 
1129
            keys_at_index = next_nodes_and_keys
 
1130
        # We should now be at the _LeafNodes
 
1131
        node_indexes = [idx for idx, s_keys in keys_at_index]
 
1132
 
 
1133
        # TODO: We may *not* want to always read all the nodes in one
 
1134
        #       big go. Consider setting a max size on this.
 
1135
        nodes = self._get_leaf_nodes(node_indexes)
 
1136
        return nodes, keys_at_index
 
1137
 
1042
1138
    def iter_entries(self, keys):
1043
1139
        """Iterate over keys within the index.
1044
1140
 
1082
1178
        needed_keys = keys
1083
1179
        if not needed_keys:
1084
1180
            return
1085
 
        # 6 seconds spent in miss_torture using the sorted() line.
1086
 
        # Even with out of order disk IO it seems faster not to sort it when
1087
 
        # large queries are being made.
1088
 
        needed_keys = sorted(needed_keys)
1089
 
 
1090
 
        nodes_and_keys = [(0, needed_keys)]
1091
 
 
1092
 
        for row_pos, next_row_start in enumerate(self._row_offsets[1:-1]):
1093
 
            node_indexes = [idx for idx, s_keys in nodes_and_keys]
1094
 
            nodes = self._get_internal_nodes(node_indexes)
1095
 
 
1096
 
            next_nodes_and_keys = []
1097
 
            for node_index, sub_keys in nodes_and_keys:
1098
 
                node = nodes[node_index]
1099
 
                positions = self._multi_bisect_right(sub_keys, node.keys)
1100
 
                node_offset = next_row_start + node.offset
1101
 
                next_nodes_and_keys.extend([(node_offset + pos, s_keys)
1102
 
                                           for pos, s_keys in positions])
1103
 
            nodes_and_keys = next_nodes_and_keys
1104
 
        # We should now be at the _LeafNodes
1105
 
        node_indexes = [idx for idx, s_keys in nodes_and_keys]
1106
 
 
1107
 
        # TODO: We may *not* want to always read all the nodes in one
1108
 
        #       big go. Consider setting a max size on this.
1109
 
 
1110
 
        nodes = self._get_leaf_nodes(node_indexes)
 
1181
        nodes, nodes_and_keys = self._walk_through_internal_nodes(needed_keys)
1111
1182
        for node_index, sub_keys in nodes_and_keys:
1112
1183
            if not sub_keys:
1113
1184
                continue
1114
1185
            node = nodes[node_index]
1115
1186
            for next_sub_key in sub_keys:
1116
 
                if next_sub_key in node.keys:
1117
 
                    value, refs = node.keys[next_sub_key]
 
1187
                if next_sub_key in node:
 
1188
                    value, refs = node[next_sub_key]
1118
1189
                    if self.node_ref_lists:
1119
1190
                        yield (self, next_sub_key, value, refs)
1120
1191
                    else:
1121
1192
                        yield (self, next_sub_key, value)
1122
1193
 
 
1194
    def _find_ancestors(self, keys, ref_list_num, parent_map, missing_keys):
 
1195
        """Find the parent_map information for the set of keys.
 
1196
 
 
1197
        This populates the parent_map dict and missing_keys set based on the
 
1198
        queried keys. It also can fill out an arbitrary number of parents that
 
1199
        it finds while searching for the supplied keys.
 
1200
 
 
1201
        It is unlikely that you want to call this directly. See
 
1202
        "CombinedGraphIndex.find_ancestry()" for a more appropriate API.
 
1203
 
 
1204
        :param keys: A keys whose ancestry we want to return
 
1205
            Every key will either end up in 'parent_map' or 'missing_keys'.
 
1206
        :param ref_list_num: This index in the ref_lists is the parents we
 
1207
            care about.
 
1208
        :param parent_map: {key: parent_keys} for keys that are present in this
 
1209
            index. This may contain more entries than were in 'keys', that are
 
1210
            reachable ancestors of the keys requested.
 
1211
        :param missing_keys: keys which are known to be missing in this index.
 
1212
            This may include parents that were not directly requested, but we
 
1213
            were able to determine that they are not present in this index.
 
1214
        :return: search_keys    parents that were found but not queried to know
 
1215
            if they are missing or present. Callers can re-query this index for
 
1216
            those keys, and they will be placed into parent_map or missing_keys
 
1217
        """
 
1218
        if not self.key_count():
 
1219
            # We use key_count() to trigger reading the root node and
 
1220
            # determining info about this BTreeGraphIndex
 
1221
            # If we don't have any keys, then everything is missing
 
1222
            missing_keys.update(keys)
 
1223
            return set()
 
1224
        if ref_list_num >= self.node_ref_lists:
 
1225
            raise ValueError('No ref list %d, index has %d ref lists'
 
1226
                % (ref_list_num, self.node_ref_lists))
 
1227
 
 
1228
        # The main trick we are trying to accomplish is that when we find a
 
1229
        # key listing its parents, we expect that the parent key is also likely
 
1230
        # to sit on the same page. Allowing us to expand parents quickly
 
1231
        # without suffering the full stack of bisecting, etc.
 
1232
        nodes, nodes_and_keys = self._walk_through_internal_nodes(keys)
 
1233
 
 
1234
        # These are parent keys which could not be immediately resolved on the
 
1235
        # page where the child was present. Note that we may already be
 
1236
        # searching for that key, and it may actually be present [or known
 
1237
        # missing] on one of the other pages we are reading.
 
1238
        # TODO:
 
1239
        #   We could try searching for them in the immediate previous or next
 
1240
        #   page. If they occur "later" we could put them in a pending lookup
 
1241
        #   set, and then for each node we read thereafter we could check to
 
1242
        #   see if they are present.
 
1243
        #   However, we don't know the impact of keeping this list of things
 
1244
        #   that I'm going to search for every node I come across from here on
 
1245
        #   out.
 
1246
        #   It doesn't handle the case when the parent key is missing on a
 
1247
        #   page that we *don't* read. So we already have to handle being
 
1248
        #   re-entrant for that.
 
1249
        #   Since most keys contain a date string, they are more likely to be
 
1250
        #   found earlier in the file than later, but we would know that right
 
1251
        #   away (key < min_key), and wouldn't keep searching it on every other
 
1252
        #   page that we read.
 
1253
        #   Mostly, it is an idea, one which should be benchmarked.
 
1254
        parents_not_on_page = set()
 
1255
 
 
1256
        for node_index, sub_keys in nodes_and_keys:
 
1257
            if not sub_keys:
 
1258
                continue
 
1259
            # sub_keys is all of the keys we are looking for that should exist
 
1260
            # on this page, if they aren't here, then they won't be found
 
1261
            node = nodes[node_index]
 
1262
            parents_to_check = set()
 
1263
            for next_sub_key in sub_keys:
 
1264
                if next_sub_key not in node:
 
1265
                    # This one is just not present in the index at all
 
1266
                    missing_keys.add(next_sub_key)
 
1267
                else:
 
1268
                    value, refs = node[next_sub_key]
 
1269
                    parent_keys = refs[ref_list_num]
 
1270
                    parent_map[next_sub_key] = parent_keys
 
1271
                    parents_to_check.update(parent_keys)
 
1272
            # Don't look for things we've already found
 
1273
            parents_to_check = parents_to_check.difference(parent_map)
 
1274
            # this can be used to test the benefit of having the check loop
 
1275
            # inlined.
 
1276
            # parents_not_on_page.update(parents_to_check)
 
1277
            # continue
 
1278
            while parents_to_check:
 
1279
                next_parents_to_check = set()
 
1280
                for key in parents_to_check:
 
1281
                    if key in node:
 
1282
                        value, refs = node[key]
 
1283
                        parent_keys = refs[ref_list_num]
 
1284
                        parent_map[key] = parent_keys
 
1285
                        next_parents_to_check.update(parent_keys)
 
1286
                    else:
 
1287
                        # This parent either is genuinely missing, or should be
 
1288
                        # found on another page. Perf test whether it is better
 
1289
                        # to check if this node should fit on this page or not.
 
1290
                        # in the 'everything-in-one-pack' scenario, this *not*
 
1291
                        # doing the check is 237ms vs 243ms.
 
1292
                        # So slightly better, but I assume the standard 'lots
 
1293
                        # of packs' is going to show a reasonable improvement
 
1294
                        # from the check, because it avoids 'going around
 
1295
                        # again' for everything that is in another index
 
1296
                        # parents_not_on_page.add(key)
 
1297
                        # Missing for some reason
 
1298
                        if key < node.min_key:
 
1299
                            # in the case of bzr.dev, 3.4k/5.3k misses are
 
1300
                            # 'earlier' misses (65%)
 
1301
                            parents_not_on_page.add(key)
 
1302
                        elif key > node.max_key:
 
1303
                            # This parent key would be present on a different
 
1304
                            # LeafNode
 
1305
                            parents_not_on_page.add(key)
 
1306
                        else:
 
1307
                            # assert key != node.min_key and key != node.max_key
 
1308
                            # If it was going to be present, it would be on
 
1309
                            # *this* page, so mark it missing.
 
1310
                            missing_keys.add(key)
 
1311
                parents_to_check = next_parents_to_check.difference(parent_map)
 
1312
                # Might want to do another .difference() from missing_keys
 
1313
        # parents_not_on_page could have been found on a different page, or be
 
1314
        # known to be missing. So cull out everything that has already been
 
1315
        # found.
 
1316
        search_keys = parents_not_on_page.difference(
 
1317
            parent_map).difference(missing_keys)
 
1318
        return search_keys
 
1319
 
1123
1320
    def iter_entries_prefix(self, keys):
1124
1321
        """Iterate over keys within the index using prefix matching.
1125
1322
 
1315
1512
        # list of (offset, length) regions of the file that should, evenually
1316
1513
        # be read in to data_ranges, either from 'bytes' or from the transport
1317
1514
        ranges = []
 
1515
        base_offset = self._base_offset
1318
1516
        for index in nodes:
1319
 
            offset = index * _PAGE_SIZE
 
1517
            offset = (index * _PAGE_SIZE)
1320
1518
            size = _PAGE_SIZE
1321
1519
            if index == 0:
1322
1520
                # Root node - special case
1326
1524
                    # The only case where we don't know the size, is for very
1327
1525
                    # small indexes. So we read the whole thing
1328
1526
                    bytes = self._transport.get_bytes(self._name)
1329
 
                    self._size = len(bytes)
 
1527
                    num_bytes = len(bytes)
 
1528
                    self._size = num_bytes - base_offset
1330
1529
                    # the whole thing should be parsed out of 'bytes'
1331
 
                    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)]
1332
1532
                    break
1333
1533
            else:
1334
1534
                if offset > self._size:
1336
1536
                                         ' of the file %s > %s'
1337
1537
                                         % (offset, self._size))
1338
1538
                size = min(size, self._size - offset)
1339
 
            ranges.append((offset, size))
 
1539
            ranges.append((base_offset + offset, size))
1340
1540
        if not ranges:
1341
1541
            return
1342
1542
        elif bytes is not None:
1343
1543
            # already have the whole file
1344
 
            data_ranges = [(start, bytes[start:start+_PAGE_SIZE])
1345
 
                           for start in xrange(0, len(bytes), _PAGE_SIZE)]
 
1544
            data_ranges = [(start, bytes[start:start+size])
 
1545
                           for start, size in ranges]
1346
1546
        elif self._file is None:
1347
1547
            data_ranges = self._transport.readv(self._name, ranges)
1348
1548
        else:
1351
1551
                self._file.seek(offset)
1352
1552
                data_ranges.append((offset, self._file.read(size)))
1353
1553
        for offset, data in data_ranges:
 
1554
            offset -= base_offset
1354
1555
            if offset == 0:
1355
1556
                # extract the header
1356
1557
                offset, data = self._parse_header_from_bytes(data)
1358
1559
                    continue
1359
1560
            bytes = zlib.decompress(data)
1360
1561
            if bytes.startswith(_LEAF_FLAG):
1361
 
                node = _LeafNode(bytes, self._key_length, self.node_ref_lists)
 
1562
                node = self._leaf_factory(bytes, self._key_length,
 
1563
                                          self.node_ref_lists)
1362
1564
            elif bytes.startswith(_INTERNAL_FLAG):
1363
1565
                node = _InternalNode(bytes)
1364
1566
            else:
1383
1585
            pass
1384
1586
 
1385
1587
 
 
1588
_gcchk_factory = _LeafNode
 
1589
 
1386
1590
try:
1387
1591
    from bzrlib import _btree_serializer_pyx as _btree_serializer
1388
 
except ImportError:
 
1592
    _gcchk_factory = _btree_serializer._parse_into_chk
 
1593
except ImportError, e:
 
1594
    osutils.failed_to_load_extension(e)
1389
1595
    from bzrlib import _btree_serializer_py as _btree_serializer