← 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: 2009-03-27 22:29:55 UTC
  • mto: (3735.39.2 clean)
  • mto: This revision was merged to the branch mainline in revision 4280.
  • Revision ID: john@arbash-meinel.com-20090327222955-utifmfm888zerixt
Implement apply_delta_to_source which doesn't have to malloc another string.

Show diffs side-by-side

added added

removed removed

Lines of Context:
bzrlib/btree_index.py
1
 
# Copyright (C) 2008, 2009, 2010 Canonical Ltd
 
1
# Copyright (C) 2008 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
import array
 
21
import bisect
21
22
from bisect import bisect_right
 
23
from copy import deepcopy
22
24
import math
 
25
import struct
23
26
import tempfile
24
27
import zlib
25
28
 
31
34
    index,
32
35
    lru_cache,
33
36
    osutils,
34
 
    static_tuple,
35
37
    trace,
36
 
    transport,
37
38
    )
38
39
from bzrlib.index import _OPTION_NODE_REFS, _OPTION_KEY_ELEMENTS, _OPTION_LEN
 
40
from bzrlib.transport import get_transport
39
41
 
40
42
 
41
43
_BTSIGNATURE = "B+Tree Graph Index 2\n"
62
64
    def __init__(self):
63
65
        """Create a _BuilderRow."""
64
66
        self.nodes = 0
65
 
        self.spool = None# tempfile.TemporaryFile(prefix='bzr-index-row-')
 
67
        self.spool = tempfile.TemporaryFile()
66
68
        self.writer = None
67
69
 
68
70
    def finish_node(self, pad=True):
69
71
        byte_lines, _, padding = self.writer.finish()
70
72
        if self.nodes == 0:
71
 
            self.spool = cStringIO.StringIO()
72
73
            # padded note:
73
74
            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
79
75
        skipped_bytes = 0
80
76
        if not pad and padding:
81
77
            del byte_lines[-1]
160
156
        :param value: The value to associate with the key. It may be any
161
157
            bytes as long as it does not contain \0 or \n.
162
158
        """
163
 
        # Ensure that 'key' is a StaticTuple
164
 
        key = static_tuple.StaticTuple.from_sequence(key).intern()
165
159
        # we don't care about absent_references
166
160
        node_refs, _ = self._check_key_ref_value(key, references, value)
167
161
        if key in self._nodes:
168
162
            raise errors.BadIndexDuplicateKey(key, self)
169
 
        self._nodes[key] = static_tuple.StaticTuple(node_refs, value)
 
163
        self._nodes[key] = (node_refs, value)
 
164
        self._keys.add(key)
170
165
        if self._nodes_by_key is not None and self._key_length > 1:
171
166
            self._update_nodes_by_key(key, value, node_refs)
172
 
        if len(self._nodes) < self._spill_at:
 
167
        if len(self._keys) < self._spill_at:
173
168
            return
174
169
        self._spill_mem_keys_to_disk()
175
170
 
191
186
             backing_pos) = self._spill_mem_keys_and_combine()
192
187
        else:
193
188
            new_backing_file, size = self._spill_mem_keys_without_combining()
 
189
        dir_path, base_name = osutils.split(new_backing_file.name)
194
190
        # Note: The transport here isn't strictly needed, because we will use
195
191
        #       direct access to the new_backing._file object
196
 
        new_backing = BTreeGraphIndex(transport.get_transport('.'),
197
 
                                      '<temp>', size)
 
192
        new_backing = BTreeGraphIndex(get_transport(dir_path),
 
193
                                      base_name, size)
198
194
        # GC will clean up the file
199
195
        new_backing._file = new_backing_file
200
196
        if self._combine_backing_indices:
205
201
                self._backing_indices[backing_pos] = None
206
202
        else:
207
203
            self._backing_indices.append(new_backing)
 
204
        self._keys = set()
208
205
        self._nodes = {}
209
206
        self._nodes_by_key = None
210
207
 
322
319
            new_row = True
323
320
            for row in reversed(rows[:-1]):
324
321
                # Mark the start of the next node in the node above. If it
325
 
                # doesn't fit then propagate upwards until we find one that
 
322
                # doesn't fit then propogate upwards until we find one that
326
323
                # it does fit into.
327
324
                if row.writer.write(key_line):
328
325
                    row.finish_node()
373
370
        self.row_lengths = []
374
371
        # Loop over all nodes adding them to the bottom row
375
372
        # (rows[-1]). When we finish a chunk in a row,
376
 
        # propagate the key that didn't fit (comes after the chunk) to the
 
373
        # propogate the key that didn't fit (comes after the chunk) to the
377
374
        # row above, transitively.
378
375
        for node in node_iterator:
379
376
            if key_count == 0:
386
383
        for row in reversed(rows):
387
384
            pad = (type(row) != _LeafBuilderRow)
388
385
            row.finish_node(pad=pad)
 
386
        result = tempfile.NamedTemporaryFile(prefix='bzr-index-')
389
387
        lines = [_BTSIGNATURE]
390
388
        lines.append(_OPTION_NODE_REFS + str(self.reference_lists) + '\n')
391
389
        lines.append(_OPTION_KEY_ELEMENTS + str(self._key_length) + '\n')
392
390
        lines.append(_OPTION_LEN + str(key_count) + '\n')
393
391
        row_lengths = [row.nodes for row in rows]
394
392
        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()
399
393
        result.writelines(lines)
400
394
        position = sum(map(len, lines))
401
395
        root_row = True
412
406
            # Special case the first node as it may be prefixed
413
407
            node = row.spool.read(_PAGE_SIZE)
414
408
            result.write(node[reserved:])
415
 
            if len(node) == _PAGE_SIZE:
416
 
                result.write("\x00" * (reserved - position))
 
409
            result.write("\x00" * (reserved - position))
417
410
            position = 0 # Only the root row actually has an offset
418
411
            copied_len = osutils.pumpfile(row.spool, result)
419
412
            if copied_len != (row.nodes - 1) * _PAGE_SIZE:
438
431
    def iter_all_entries(self):
439
432
        """Iterate over all keys within the index
440
433
 
441
 
        :return: An iterable of (index, key, value, reference_lists). There is
442
 
            no defined order for the result iteration - it will be in the most
 
434
        :return: An iterable of (index, key, reference_lists, value). There is no
 
435
            defined order for the result iteration - it will be in the most
443
436
            efficient order for the index (in this case dictionary hash order).
444
437
        """
445
438
        if 'evil' in debug.debug_flags:
464
457
            efficient order for the index (keys iteration order in this case).
465
458
        """
466
459
        keys = set(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]
 
460
        local_keys = keys.intersection(self._keys)
476
461
        if self.reference_lists:
477
462
            for key in local_keys:
478
 
                node = nodes[key]
 
463
                node = self._nodes[key]
479
464
                yield self, key, node[1], node[0]
480
465
        else:
481
466
            for key in local_keys:
482
 
                node = nodes[key]
 
467
                node = self._nodes[key]
483
468
                yield self, key, node[1]
484
469
        # Find things that are in backing indices that have not been handled
485
470
        # yet.
568
553
                    else:
569
554
                        # yield keys
570
555
                        for value in key_dict.itervalues():
571
 
                            yield (self, ) + tuple(value)
 
556
                            yield (self, ) + value
572
557
            else:
573
558
                yield (self, ) + key_dict
574
559
 
595
580
 
596
581
        For InMemoryGraphIndex the estimate is exact.
597
582
        """
598
 
        return len(self._nodes) + sum(backing.key_count() for backing in
 
583
        return len(self._keys) + sum(backing.key_count() for backing in
599
584
            self._backing_indices if backing is not None)
600
585
 
601
586
    def validate(self):
602
587
        """In memory index's have no known corruption at the moment."""
603
588
 
604
589
 
605
 
class _LeafNode(dict):
 
590
class _LeafNode(object):
606
591
    """A leaf node for a serialised B+Tree index."""
607
592
 
608
 
    __slots__ = ('min_key', 'max_key', '_keys')
609
 
 
610
593
    def __init__(self, bytes, key_length, ref_list_length):
611
594
        """Parse bytes to create a leaf node object."""
612
595
        # splitlines mangles the \r delimiters.. don't use it.
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
        self.keys = dict(_btree_serializer._parse_leaf_lines(bytes,
 
597
            key_length, ref_list_length))
634
598
 
635
599
 
636
600
class _InternalNode(object):
637
601
    """An internal node for a serialised B+Tree index."""
638
602
 
639
 
    __slots__ = ('keys', 'offset')
640
 
 
641
603
    def __init__(self, bytes):
642
604
        """Parse bytes to create an internal node object."""
643
605
        # splitlines mangles the \r delimiters.. don't use it.
646
608
    def _parse_lines(self, lines):
647
609
        nodes = []
648
610
        self.offset = int(lines[1][7:])
649
 
        as_st = static_tuple.StaticTuple.from_sequence
650
611
        for line in lines[2:]:
651
612
            if line == '':
652
613
                break
653
 
            nodes.append(as_st(map(intern, line.split('\0'))).intern())
 
614
            nodes.append(tuple(line.split('\0')))
654
615
        return nodes
655
616
 
656
617
 
661
622
    memory except when very large walks are done.
662
623
    """
663
624
 
664
 
    def __init__(self, transport, name, size, unlimited_cache=False,
665
 
                 offset=0):
 
625
    def __init__(self, transport, name, size):
666
626
        """Create a B+Tree index object on the index name.
667
627
 
668
628
        :param transport: The transport to read data for the index from.
672
632
            the initial read (to read the root node header) can be done
673
633
            without over-reading even on empty indices, and on small indices
674
634
            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.
680
635
        """
681
636
        self._transport = transport
682
637
        self._name = name
684
639
        self._file = None
685
640
        self._recommended_pages = self._compute_recommended_pages()
686
641
        self._root_node = None
687
 
        self._base_offset = offset
688
 
        self._leaf_factory = _LeafNode
689
642
        # Default max size is 100,000 leave values
690
643
        self._leaf_value_cache = None # lru_cache.LRUCache(100*1000)
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)
 
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)
700
650
        self._key_count = None
701
651
        self._row_lengths = None
702
652
        self._row_offsets = None # Start of each row, [-1] is the end
734
684
                if start_of_leaves is None:
735
685
                    start_of_leaves = self._row_offsets[-2]
736
686
                if node_pos < start_of_leaves:
737
 
                    self._internal_node_cache[node_pos] = node
 
687
                    self._internal_node_cache.add(node_pos, node)
738
688
                else:
739
 
                    self._leaf_node_cache[node_pos] = node
 
689
                    self._leaf_node_cache.add(node_pos, node)
740
690
            found[node_pos] = node
741
691
        return found
742
692
 
881
831
            new_tips = next_tips
882
832
        return final_offsets
883
833
 
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
 
 
897
834
    def external_references(self, ref_list_num):
898
835
        if self._root_node is None:
899
836
            self._get_root_node()
964
901
        """Cache directly from key => value, skipping the btree."""
965
902
        if self._leaf_value_cache is not None:
966
903
            for node in nodes.itervalues():
967
 
                for key, value in node.all_items():
 
904
                for key, value in node.keys.iteritems():
968
905
                    if key in self._leaf_value_cache:
969
906
                        # Don't add the rest of the keys, we've seen this node
970
907
                        # before.
994
931
        if self._row_offsets[-1] == 1:
995
932
            # There is only the root node, and we read that via key_count()
996
933
            if self.node_ref_lists:
997
 
                for key, (value, refs) in self._root_node.all_items():
 
934
                for key, (value, refs) in sorted(self._root_node.keys.items()):
998
935
                    yield (self, key, value, refs)
999
936
            else:
1000
 
                for key, (value, refs) in self._root_node.all_items():
 
937
                for key, (value, refs) in sorted(self._root_node.keys.items()):
1001
938
                    yield (self, key, value)
1002
939
            return
1003
940
        start_of_leaves = self._row_offsets[-2]
1013
950
        # for spilling index builds to disk.
1014
951
        if self.node_ref_lists:
1015
952
            for _, node in nodes:
1016
 
                for key, (value, refs) in node.all_items():
 
953
                for key, (value, refs) in sorted(node.keys.items()):
1017
954
                    yield (self, key, value, refs)
1018
955
        else:
1019
956
            for _, node in nodes:
1020
 
                for key, (value, refs) in node.all_items():
 
957
                for key, (value, refs) in sorted(node.keys.items()):
1021
958
                    yield (self, key, value)
1022
959
 
1023
960
    @staticmethod
1102
1039
            output.append(cur_out)
1103
1040
        return output
1104
1041
 
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
 
 
1138
1042
    def iter_entries(self, keys):
1139
1043
        """Iterate over keys within the index.
1140
1044
 
1178
1082
        needed_keys = keys
1179
1083
        if not needed_keys:
1180
1084
            return
1181
 
        nodes, nodes_and_keys = self._walk_through_internal_nodes(needed_keys)
 
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)
1182
1111
        for node_index, sub_keys in nodes_and_keys:
1183
1112
            if not sub_keys:
1184
1113
                continue
1185
1114
            node = nodes[node_index]
1186
1115
            for next_sub_key in sub_keys:
1187
 
                if next_sub_key in node:
1188
 
                    value, refs = node[next_sub_key]
 
1116
                if next_sub_key in node.keys:
 
1117
                    value, refs = node.keys[next_sub_key]
1189
1118
                    if self.node_ref_lists:
1190
1119
                        yield (self, next_sub_key, value, refs)
1191
1120
                    else:
1192
1121
                        yield (self, next_sub_key, value)
1193
1122
 
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
 
 
1320
1123
    def iter_entries_prefix(self, keys):
1321
1124
        """Iterate over keys within the index using prefix matching.
1322
1125
 
1512
1315
        # list of (offset, length) regions of the file that should, evenually
1513
1316
        # be read in to data_ranges, either from 'bytes' or from the transport
1514
1317
        ranges = []
1515
 
        base_offset = self._base_offset
1516
1318
        for index in nodes:
1517
 
            offset = (index * _PAGE_SIZE)
 
1319
            offset = index * _PAGE_SIZE
1518
1320
            size = _PAGE_SIZE
1519
1321
            if index == 0:
1520
1322
                # Root node - special case
1524
1326
                    # The only case where we don't know the size, is for very
1525
1327
                    # small indexes. So we read the whole thing
1526
1328
                    bytes = self._transport.get_bytes(self._name)
1527
 
                    num_bytes = len(bytes)
1528
 
                    self._size = num_bytes - base_offset
 
1329
                    self._size = len(bytes)
1529
1330
                    # the whole thing should be parsed out of 'bytes'
1530
 
                    ranges = [(start, min(_PAGE_SIZE, num_bytes - start))
1531
 
                        for start in xrange(base_offset, num_bytes, _PAGE_SIZE)]
 
1331
                    ranges.append((0, len(bytes)))
1532
1332
                    break
1533
1333
            else:
1534
1334
                if offset > self._size:
1536
1336
                                         ' of the file %s > %s'
1537
1337
                                         % (offset, self._size))
1538
1338
                size = min(size, self._size - offset)
1539
 
            ranges.append((base_offset + offset, size))
 
1339
            ranges.append((offset, size))
1540
1340
        if not ranges:
1541
1341
            return
1542
1342
        elif bytes is not None:
1543
1343
            # already have the whole file
1544
 
            data_ranges = [(start, bytes[start:start+size])
1545
 
                           for start, size in ranges]
 
1344
            data_ranges = [(start, bytes[start:start+_PAGE_SIZE])
 
1345
                           for start in xrange(0, len(bytes), _PAGE_SIZE)]
1546
1346
        elif self._file is None:
1547
1347
            data_ranges = self._transport.readv(self._name, ranges)
1548
1348
        else:
1551
1351
                self._file.seek(offset)
1552
1352
                data_ranges.append((offset, self._file.read(size)))
1553
1353
        for offset, data in data_ranges:
1554
 
            offset -= base_offset
1555
1354
            if offset == 0:
1556
1355
                # extract the header
1557
1356
                offset, data = self._parse_header_from_bytes(data)
1559
1358
                    continue
1560
1359
            bytes = zlib.decompress(data)
1561
1360
            if bytes.startswith(_LEAF_FLAG):
1562
 
                node = self._leaf_factory(bytes, self._key_length,
1563
 
                                          self.node_ref_lists)
 
1361
                node = _LeafNode(bytes, self._key_length, self.node_ref_lists)
1564
1362
            elif bytes.startswith(_INTERNAL_FLAG):
1565
1363
                node = _InternalNode(bytes)
1566
1364
            else:
1585
1383
            pass
1586
1384
 
1587
1385
 
1588
 
_gcchk_factory = _LeafNode
1589
 
 
1590
1386
try:
1591
 
    from bzrlib import _btree_serializer_pyx as _btree_serializer
1592
 
    _gcchk_factory = _btree_serializer._parse_into_chk
1593
 
except ImportError, e:
1594
 
    osutils.failed_to_load_extension(e)
 
1387
    from bzrlib import _btree_serializer_c as _btree_serializer
 
1388
except ImportError:
1595
1389
    from bzrlib import _btree_serializer_py as _btree_serializer