← Back to branch summary

~bzr-pqm/bzr/bzr.dev

« back to all changes in this revision

Viewing changes to bzrlib/btree_index.py

  • Committer: Andrew Bennetts
  • Date: 2009-04-02 05:53:12 UTC
  • mto: This revision was merged to the branch mainline in revision 4242.
  • Revision ID: andrew.bennetts@canonical.com-20090402055312-h7mvgumvm7e620mj
Fix nits in spelling and naming.

Show diffs side-by-side

added added

removed removed

Lines of Context:
bzrlib/btree_index.py
1
 
# Copyright (C) 2008-2011 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
21
 
 
22
 
from bzrlib.lazy_import import lazy_import
23
 
lazy_import(globals(), """
 
20
import array
24
21
import bisect
 
22
from bisect import bisect_right
 
23
from copy import deepcopy
25
24
import math
 
25
import struct
26
26
import tempfile
27
27
import zlib
28
 
""")
29
28
 
30
29
from bzrlib import (
31
30
    chunk_writer,
32
31
    debug,
33
32
    errors,
34
 
    fifo_cache,
35
33
    index,
36
34
    lru_cache,
37
35
    osutils,
38
 
    static_tuple,
39
36
    trace,
40
 
    transport,
41
37
    )
42
38
from bzrlib.index import _OPTION_NODE_REFS, _OPTION_KEY_ELEMENTS, _OPTION_LEN
 
39
from bzrlib.transport import get_transport
43
40
 
44
41
 
45
42
_BTSIGNATURE = "B+Tree Graph Index 2\n"
66
63
    def __init__(self):
67
64
        """Create a _BuilderRow."""
68
65
        self.nodes = 0
69
 
        self.spool = None# tempfile.TemporaryFile(prefix='bzr-index-row-')
 
66
        self.spool = tempfile.TemporaryFile()
70
67
        self.writer = None
71
68
 
72
69
    def finish_node(self, pad=True):
73
70
        byte_lines, _, padding = self.writer.finish()
74
71
        if self.nodes == 0:
75
 
            self.spool = cStringIO.StringIO()
76
72
            # padded note:
77
73
            self.spool.write("\x00" * _RESERVED_HEADER_BYTES)
78
 
        elif self.nodes == 1:
79
 
            # We got bigger than 1 node, switch to a temp file
80
 
            spool = tempfile.TemporaryFile(prefix='bzr-index-row-')
81
 
            spool.write(self.spool.getvalue())
82
 
            self.spool = spool
83
74
        skipped_bytes = 0
84
75
        if not pad and padding:
85
76
            del byte_lines[-1]
162
153
        :param references: An iterable of iterables of keys. Each is a
163
154
            reference to another key.
164
155
        :param value: The value to associate with the key. It may be any
165
 
            bytes as long as it does not contain \\0 or \\n.
 
156
            bytes as long as it does not contain \0 or \n.
166
157
        """
167
 
        # Ensure that 'key' is a StaticTuple
168
 
        key = static_tuple.StaticTuple.from_sequence(key).intern()
169
158
        # we don't care about absent_references
170
159
        node_refs, _ = self._check_key_ref_value(key, references, value)
171
160
        if key in self._nodes:
172
161
            raise errors.BadIndexDuplicateKey(key, self)
173
 
        self._nodes[key] = static_tuple.StaticTuple(node_refs, value)
 
162
        self._nodes[key] = (node_refs, value)
 
163
        self._keys.add(key)
174
164
        if self._nodes_by_key is not None and self._key_length > 1:
175
165
            self._update_nodes_by_key(key, value, node_refs)
176
 
        if len(self._nodes) < self._spill_at:
 
166
        if len(self._keys) < self._spill_at:
177
167
            return
178
168
        self._spill_mem_keys_to_disk()
179
169
 
195
185
             backing_pos) = self._spill_mem_keys_and_combine()
196
186
        else:
197
187
            new_backing_file, size = self._spill_mem_keys_without_combining()
 
188
        dir_path, base_name = osutils.split(new_backing_file.name)
198
189
        # Note: The transport here isn't strictly needed, because we will use
199
190
        #       direct access to the new_backing._file object
200
 
        new_backing = BTreeGraphIndex(transport.get_transport('.'),
201
 
                                      '<temp>', size)
 
191
        new_backing = BTreeGraphIndex(get_transport(dir_path),
 
192
                                      base_name, size)
202
193
        # GC will clean up the file
203
194
        new_backing._file = new_backing_file
204
195
        if self._combine_backing_indices:
209
200
                self._backing_indices[backing_pos] = None
210
201
        else:
211
202
            self._backing_indices.append(new_backing)
 
203
        self._keys = set()
212
204
        self._nodes = {}
213
205
        self._nodes_by_key = None
214
206
 
326
318
            new_row = True
327
319
            for row in reversed(rows[:-1]):
328
320
                # Mark the start of the next node in the node above. If it
329
 
                # doesn't fit then propagate upwards until we find one that
 
321
                # doesn't fit then propogate upwards until we find one that
330
322
                # it does fit into.
331
323
                if row.writer.write(key_line):
332
324
                    row.finish_node()
377
369
        self.row_lengths = []
378
370
        # Loop over all nodes adding them to the bottom row
379
371
        # (rows[-1]). When we finish a chunk in a row,
380
 
        # propagate the key that didn't fit (comes after the chunk) to the
 
372
        # propogate the key that didn't fit (comes after the chunk) to the
381
373
        # row above, transitively.
382
374
        for node in node_iterator:
383
375
            if key_count == 0:
390
382
        for row in reversed(rows):
391
383
            pad = (type(row) != _LeafBuilderRow)
392
384
            row.finish_node(pad=pad)
 
385
        result = tempfile.NamedTemporaryFile(prefix='bzr-index-')
393
386
        lines = [_BTSIGNATURE]
394
387
        lines.append(_OPTION_NODE_REFS + str(self.reference_lists) + '\n')
395
388
        lines.append(_OPTION_KEY_ELEMENTS + str(self._key_length) + '\n')
396
389
        lines.append(_OPTION_LEN + str(key_count) + '\n')
397
390
        row_lengths = [row.nodes for row in rows]
398
391
        lines.append(_OPTION_ROW_LENGTHS + ','.join(map(str, row_lengths)) + '\n')
399
 
        if row_lengths and row_lengths[-1] > 1:
400
 
            result = tempfile.NamedTemporaryFile(prefix='bzr-index-')
401
 
        else:
402
 
            result = cStringIO.StringIO()
403
392
        result.writelines(lines)
404
393
        position = sum(map(len, lines))
405
394
        root_row = True
416
405
            # Special case the first node as it may be prefixed
417
406
            node = row.spool.read(_PAGE_SIZE)
418
407
            result.write(node[reserved:])
419
 
            if len(node) == _PAGE_SIZE:
420
 
                result.write("\x00" * (reserved - position))
 
408
            result.write("\x00" * (reserved - position))
421
409
            position = 0 # Only the root row actually has an offset
422
410
            copied_len = osutils.pumpfile(row.spool, result)
423
411
            if copied_len != (row.nodes - 1) * _PAGE_SIZE:
442
430
    def iter_all_entries(self):
443
431
        """Iterate over all keys within the index
444
432
 
445
 
        :return: An iterable of (index, key, value, reference_lists). There is
446
 
            no defined order for the result iteration - it will be in the most
 
433
        :return: An iterable of (index, key, reference_lists, value). There is no
 
434
            defined order for the result iteration - it will be in the most
447
435
            efficient order for the index (in this case dictionary hash order).
448
436
        """
449
437
        if 'evil' in debug.debug_flags:
468
456
            efficient order for the index (keys iteration order in this case).
469
457
        """
470
458
        keys = set(keys)
471
 
        # Note: We don't use keys.intersection() here. If you read the C api,
472
 
        #       set.intersection(other) special cases when other is a set and
473
 
        #       will iterate the smaller of the two and lookup in the other.
474
 
        #       It does *not* do this for any other type (even dict, unlike
475
 
        #       some other set functions.) Since we expect keys is generally <<
476
 
        #       self._nodes, it is faster to iterate over it in a list
477
 
        #       comprehension
478
 
        nodes = self._nodes
479
 
        local_keys = [key for key in keys if key in nodes]
 
459
        local_keys = keys.intersection(self._keys)
480
460
        if self.reference_lists:
481
461
            for key in local_keys:
482
 
                node = nodes[key]
 
462
                node = self._nodes[key]
483
463
                yield self, key, node[1], node[0]
484
464
        else:
485
465
            for key in local_keys:
486
 
                node = nodes[key]
 
466
                node = self._nodes[key]
487
467
                yield self, key, node[1]
488
468
        # Find things that are in backing indices that have not been handled
489
469
        # yet.
572
552
                    else:
573
553
                        # yield keys
574
554
                        for value in key_dict.itervalues():
575
 
                            yield (self, ) + tuple(value)
 
555
                            yield (self, ) + value
576
556
            else:
577
557
                yield (self, ) + key_dict
578
558
 
599
579
 
600
580
        For InMemoryGraphIndex the estimate is exact.
601
581
        """
602
 
        return len(self._nodes) + sum(backing.key_count() for backing in
 
582
        return len(self._keys) + sum(backing.key_count() for backing in
603
583
            self._backing_indices if backing is not None)
604
584
 
605
585
    def validate(self):
606
586
        """In memory index's have no known corruption at the moment."""
607
587
 
608
588
 
609
 
class _LeafNode(dict):
 
589
class _LeafNode(object):
610
590
    """A leaf node for a serialised B+Tree index."""
611
591
 
612
 
    __slots__ = ('min_key', 'max_key', '_keys')
613
 
 
614
592
    def __init__(self, bytes, key_length, ref_list_length):
615
593
        """Parse bytes to create a leaf node object."""
616
594
        # splitlines mangles the \r delimiters.. don't use it.
617
 
        key_list = _btree_serializer._parse_leaf_lines(bytes,
618
 
            key_length, ref_list_length)
619
 
        if key_list:
620
 
            self.min_key = key_list[0][0]
621
 
            self.max_key = key_list[-1][0]
622
 
        else:
623
 
            self.min_key = self.max_key = None
624
 
        super(_LeafNode, self).__init__(key_list)
625
 
        self._keys = dict(self)
626
 
 
627
 
    def all_items(self):
628
 
        """Return a sorted list of (key, (value, refs)) items"""
629
 
        items = self.items()
630
 
        items.sort()
631
 
        return items
632
 
 
633
 
    def all_keys(self):
634
 
        """Return a sorted list of all keys."""
635
 
        keys = self.keys()
636
 
        keys.sort()
637
 
        return keys
 
595
        self.keys = dict(_btree_serializer._parse_leaf_lines(bytes,
 
596
            key_length, ref_list_length))
638
597
 
639
598
 
640
599
class _InternalNode(object):
641
600
    """An internal node for a serialised B+Tree index."""
642
601
 
643
 
    __slots__ = ('keys', 'offset')
644
 
 
645
602
    def __init__(self, bytes):
646
603
        """Parse bytes to create an internal node object."""
647
604
        # splitlines mangles the \r delimiters.. don't use it.
650
607
    def _parse_lines(self, lines):
651
608
        nodes = []
652
609
        self.offset = int(lines[1][7:])
653
 
        as_st = static_tuple.StaticTuple.from_sequence
654
610
        for line in lines[2:]:
655
611
            if line == '':
656
612
                break
657
 
            nodes.append(as_st(map(intern, line.split('\0'))).intern())
 
613
            nodes.append(tuple(line.split('\0')))
658
614
        return nodes
659
615
 
660
616
 
665
621
    memory except when very large walks are done.
666
622
    """
667
623
 
668
 
    def __init__(self, transport, name, size, unlimited_cache=False,
669
 
                 offset=0):
 
624
    def __init__(self, transport, name, size):
670
625
        """Create a B+Tree index object on the index name.
671
626
 
672
627
        :param transport: The transport to read data for the index from.
676
631
            the initial read (to read the root node header) can be done
677
632
            without over-reading even on empty indices, and on small indices
678
633
            allows single-IO to read the entire index.
679
 
        :param unlimited_cache: If set to True, then instead of using an
680
 
            LRUCache with size _NODE_CACHE_SIZE, we will use a dict and always
681
 
            cache all leaf nodes.
682
 
        :param offset: The start of the btree index data isn't byte 0 of the
683
 
            file. Instead it starts at some point later.
684
634
        """
685
635
        self._transport = transport
686
636
        self._name = name
688
638
        self._file = None
689
639
        self._recommended_pages = self._compute_recommended_pages()
690
640
        self._root_node = None
691
 
        self._base_offset = offset
692
 
        self._leaf_factory = _LeafNode
693
641
        # Default max size is 100,000 leave values
694
642
        self._leaf_value_cache = None # lru_cache.LRUCache(100*1000)
695
 
        if unlimited_cache:
696
 
            self._leaf_node_cache = {}
697
 
            self._internal_node_cache = {}
698
 
        else:
699
 
            self._leaf_node_cache = lru_cache.LRUCache(_NODE_CACHE_SIZE)
700
 
            # We use a FIFO here just to prevent possible blowout. However, a
701
 
            # 300k record btree has only 3k leaf nodes, and only 20 internal
702
 
            # nodes. A value of 100 scales to ~100*100*100 = 1M records.
703
 
            self._internal_node_cache = fifo_cache.FIFOCache(100)
 
643
        self._leaf_node_cache = lru_cache.LRUCache(_NODE_CACHE_SIZE)
 
644
        self._internal_node_cache = lru_cache.LRUCache()
704
645
        self._key_count = None
705
646
        self._row_lengths = None
706
647
        self._row_offsets = None # Start of each row, [-1] is the end
738
679
                if start_of_leaves is None:
739
680
                    start_of_leaves = self._row_offsets[-2]
740
681
                if node_pos < start_of_leaves:
741
 
                    self._internal_node_cache[node_pos] = node
 
682
                    self._internal_node_cache.add(node_pos, node)
742
683
                else:
743
 
                    self._leaf_node_cache[node_pos] = node
 
684
                    self._leaf_node_cache.add(node_pos, node)
744
685
            found[node_pos] = node
745
686
        return found
746
687
 
885
826
            new_tips = next_tips
886
827
        return final_offsets
887
828
 
888
 
    def clear_cache(self):
889
 
        """Clear out any cached/memoized values.
890
 
 
891
 
        This can be called at any time, but generally it is used when we have
892
 
        extracted some information, but don't expect to be requesting any more
893
 
        from this index.
894
 
        """
895
 
        # Note that we don't touch self._root_node or self._internal_node_cache
896
 
        # We don't expect either of those to be big, and it can save
897
 
        # round-trips in the future. We may re-evaluate this if InternalNode
898
 
        # memory starts to be an issue.
899
 
        self._leaf_node_cache.clear()
900
 
 
901
829
    def external_references(self, ref_list_num):
902
830
        if self._root_node is None:
903
831
            self._get_root_node()
968
896
        """Cache directly from key => value, skipping the btree."""
969
897
        if self._leaf_value_cache is not None:
970
898
            for node in nodes.itervalues():
971
 
                for key, value in node.all_items():
 
899
                for key, value in node.keys.iteritems():
972
900
                    if key in self._leaf_value_cache:
973
901
                        # Don't add the rest of the keys, we've seen this node
974
902
                        # before.
998
926
        if self._row_offsets[-1] == 1:
999
927
            # There is only the root node, and we read that via key_count()
1000
928
            if self.node_ref_lists:
1001
 
                for key, (value, refs) in self._root_node.all_items():
 
929
                for key, (value, refs) in sorted(self._root_node.keys.items()):
1002
930
                    yield (self, key, value, refs)
1003
931
            else:
1004
 
                for key, (value, refs) in self._root_node.all_items():
 
932
                for key, (value, refs) in sorted(self._root_node.keys.items()):
1005
933
                    yield (self, key, value)
1006
934
            return
1007
935
        start_of_leaves = self._row_offsets[-2]
1017
945
        # for spilling index builds to disk.
1018
946
        if self.node_ref_lists:
1019
947
            for _, node in nodes:
1020
 
                for key, (value, refs) in node.all_items():
 
948
                for key, (value, refs) in sorted(node.keys.items()):
1021
949
                    yield (self, key, value, refs)
1022
950
        else:
1023
951
            for _, node in nodes:
1024
 
                for key, (value, refs) in node.all_items():
 
952
                for key, (value, refs) in sorted(node.keys.items()):
1025
953
                    yield (self, key, value)
1026
954
 
1027
955
    @staticmethod
1051
979
        # iter_steps = len(in_keys) + len(fixed_keys)
1052
980
        # bisect_steps = len(in_keys) * math.log(len(fixed_keys), 2)
1053
981
        if len(in_keys) == 1: # Bisect will always be faster for M = 1
1054
 
            return [(bisect.bisect_right(fixed_keys, in_keys[0]), in_keys)]
 
982
            return [(bisect_right(fixed_keys, in_keys[0]), in_keys)]
1055
983
        # elif bisect_steps < iter_steps:
1056
984
        #     offsets = {}
1057
985
        #     for key in in_keys:
1106
1034
            output.append(cur_out)
1107
1035
        return output
1108
1036
 
1109
 
    def _walk_through_internal_nodes(self, keys):
1110
 
        """Take the given set of keys, and find the corresponding LeafNodes.
1111
 
 
1112
 
        :param keys: An unsorted iterable of keys to search for
1113
 
        :return: (nodes, index_and_keys)
1114
 
            nodes is a dict mapping {index: LeafNode}
1115
 
            keys_at_index is a list of tuples of [(index, [keys for Leaf])]
1116
 
        """
1117
 
        # 6 seconds spent in miss_torture using the sorted() line.
1118
 
        # Even with out of order disk IO it seems faster not to sort it when
1119
 
        # large queries are being made.
1120
 
        keys_at_index = [(0, sorted(keys))]
1121
 
 
1122
 
        for row_pos, next_row_start in enumerate(self._row_offsets[1:-1]):
1123
 
            node_indexes = [idx for idx, s_keys in keys_at_index]
1124
 
            nodes = self._get_internal_nodes(node_indexes)
1125
 
 
1126
 
            next_nodes_and_keys = []
1127
 
            for node_index, sub_keys in keys_at_index:
1128
 
                node = nodes[node_index]
1129
 
                positions = self._multi_bisect_right(sub_keys, node.keys)
1130
 
                node_offset = next_row_start + node.offset
1131
 
                next_nodes_and_keys.extend([(node_offset + pos, s_keys)
1132
 
                                           for pos, s_keys in positions])
1133
 
            keys_at_index = next_nodes_and_keys
1134
 
        # We should now be at the _LeafNodes
1135
 
        node_indexes = [idx for idx, s_keys in keys_at_index]
1136
 
 
1137
 
        # TODO: We may *not* want to always read all the nodes in one
1138
 
        #       big go. Consider setting a max size on this.
1139
 
        nodes = self._get_leaf_nodes(node_indexes)
1140
 
        return nodes, keys_at_index
1141
 
 
1142
1037
    def iter_entries(self, keys):
1143
1038
        """Iterate over keys within the index.
1144
1039
 
1182
1077
        needed_keys = keys
1183
1078
        if not needed_keys:
1184
1079
            return
1185
 
        nodes, nodes_and_keys = self._walk_through_internal_nodes(needed_keys)
 
1080
        # 6 seconds spent in miss_torture using the sorted() line.
 
1081
        # Even with out of order disk IO it seems faster not to sort it when
 
1082
        # large queries are being made.
 
1083
        needed_keys = sorted(needed_keys)
 
1084
 
 
1085
        nodes_and_keys = [(0, needed_keys)]
 
1086
 
 
1087
        for row_pos, next_row_start in enumerate(self._row_offsets[1:-1]):
 
1088
            node_indexes = [idx for idx, s_keys in nodes_and_keys]
 
1089
            nodes = self._get_internal_nodes(node_indexes)
 
1090
 
 
1091
            next_nodes_and_keys = []
 
1092
            for node_index, sub_keys in nodes_and_keys:
 
1093
                node = nodes[node_index]
 
1094
                positions = self._multi_bisect_right(sub_keys, node.keys)
 
1095
                node_offset = next_row_start + node.offset
 
1096
                next_nodes_and_keys.extend([(node_offset + pos, s_keys)
 
1097
                                           for pos, s_keys in positions])
 
1098
            nodes_and_keys = next_nodes_and_keys
 
1099
        # We should now be at the _LeafNodes
 
1100
        node_indexes = [idx for idx, s_keys in nodes_and_keys]
 
1101
 
 
1102
        # TODO: We may *not* want to always read all the nodes in one
 
1103
        #       big go. Consider setting a max size on this.
 
1104
 
 
1105
        nodes = self._get_leaf_nodes(node_indexes)
1186
1106
        for node_index, sub_keys in nodes_and_keys:
1187
1107
            if not sub_keys:
1188
1108
                continue
1189
1109
            node = nodes[node_index]
1190
1110
            for next_sub_key in sub_keys:
1191
 
                if next_sub_key in node:
1192
 
                    value, refs = node[next_sub_key]
 
1111
                if next_sub_key in node.keys:
 
1112
                    value, refs = node.keys[next_sub_key]
1193
1113
                    if self.node_ref_lists:
1194
1114
                        yield (self, next_sub_key, value, refs)
1195
1115
                    else:
1196
1116
                        yield (self, next_sub_key, value)
1197
1117
 
1198
 
    def _find_ancestors(self, keys, ref_list_num, parent_map, missing_keys):
1199
 
        """Find the parent_map information for the set of keys.
1200
 
 
1201
 
        This populates the parent_map dict and missing_keys set based on the
1202
 
        queried keys. It also can fill out an arbitrary number of parents that
1203
 
        it finds while searching for the supplied keys.
1204
 
 
1205
 
        It is unlikely that you want to call this directly. See
1206
 
        "CombinedGraphIndex.find_ancestry()" for a more appropriate API.
1207
 
 
1208
 
        :param keys: A keys whose ancestry we want to return
1209
 
            Every key will either end up in 'parent_map' or 'missing_keys'.
1210
 
        :param ref_list_num: This index in the ref_lists is the parents we
1211
 
            care about.
1212
 
        :param parent_map: {key: parent_keys} for keys that are present in this
1213
 
            index. This may contain more entries than were in 'keys', that are
1214
 
            reachable ancestors of the keys requested.
1215
 
        :param missing_keys: keys which are known to be missing in this index.
1216
 
            This may include parents that were not directly requested, but we
1217
 
            were able to determine that they are not present in this index.
1218
 
        :return: search_keys    parents that were found but not queried to know
1219
 
            if they are missing or present. Callers can re-query this index for
1220
 
            those keys, and they will be placed into parent_map or missing_keys
1221
 
        """
1222
 
        if not self.key_count():
1223
 
            # We use key_count() to trigger reading the root node and
1224
 
            # determining info about this BTreeGraphIndex
1225
 
            # If we don't have any keys, then everything is missing
1226
 
            missing_keys.update(keys)
1227
 
            return set()
1228
 
        if ref_list_num >= self.node_ref_lists:
1229
 
            raise ValueError('No ref list %d, index has %d ref lists'
1230
 
                % (ref_list_num, self.node_ref_lists))
1231
 
 
1232
 
        # The main trick we are trying to accomplish is that when we find a
1233
 
        # key listing its parents, we expect that the parent key is also likely
1234
 
        # to sit on the same page. Allowing us to expand parents quickly
1235
 
        # without suffering the full stack of bisecting, etc.
1236
 
        nodes, nodes_and_keys = self._walk_through_internal_nodes(keys)
1237
 
 
1238
 
        # These are parent keys which could not be immediately resolved on the
1239
 
        # page where the child was present. Note that we may already be
1240
 
        # searching for that key, and it may actually be present [or known
1241
 
        # missing] on one of the other pages we are reading.
1242
 
        # TODO:
1243
 
        #   We could try searching for them in the immediate previous or next
1244
 
        #   page. If they occur "later" we could put them in a pending lookup
1245
 
        #   set, and then for each node we read thereafter we could check to
1246
 
        #   see if they are present.
1247
 
        #   However, we don't know the impact of keeping this list of things
1248
 
        #   that I'm going to search for every node I come across from here on
1249
 
        #   out.
1250
 
        #   It doesn't handle the case when the parent key is missing on a
1251
 
        #   page that we *don't* read. So we already have to handle being
1252
 
        #   re-entrant for that.
1253
 
        #   Since most keys contain a date string, they are more likely to be
1254
 
        #   found earlier in the file than later, but we would know that right
1255
 
        #   away (key < min_key), and wouldn't keep searching it on every other
1256
 
        #   page that we read.
1257
 
        #   Mostly, it is an idea, one which should be benchmarked.
1258
 
        parents_not_on_page = set()
1259
 
 
1260
 
        for node_index, sub_keys in nodes_and_keys:
1261
 
            if not sub_keys:
1262
 
                continue
1263
 
            # sub_keys is all of the keys we are looking for that should exist
1264
 
            # on this page, if they aren't here, then they won't be found
1265
 
            node = nodes[node_index]
1266
 
            parents_to_check = set()
1267
 
            for next_sub_key in sub_keys:
1268
 
                if next_sub_key not in node:
1269
 
                    # This one is just not present in the index at all
1270
 
                    missing_keys.add(next_sub_key)
1271
 
                else:
1272
 
                    value, refs = node[next_sub_key]
1273
 
                    parent_keys = refs[ref_list_num]
1274
 
                    parent_map[next_sub_key] = parent_keys
1275
 
                    parents_to_check.update(parent_keys)
1276
 
            # Don't look for things we've already found
1277
 
            parents_to_check = parents_to_check.difference(parent_map)
1278
 
            # this can be used to test the benefit of having the check loop
1279
 
            # inlined.
1280
 
            # parents_not_on_page.update(parents_to_check)
1281
 
            # continue
1282
 
            while parents_to_check:
1283
 
                next_parents_to_check = set()
1284
 
                for key in parents_to_check:
1285
 
                    if key in node:
1286
 
                        value, refs = node[key]
1287
 
                        parent_keys = refs[ref_list_num]
1288
 
                        parent_map[key] = parent_keys
1289
 
                        next_parents_to_check.update(parent_keys)
1290
 
                    else:
1291
 
                        # This parent either is genuinely missing, or should be
1292
 
                        # found on another page. Perf test whether it is better
1293
 
                        # to check if this node should fit on this page or not.
1294
 
                        # in the 'everything-in-one-pack' scenario, this *not*
1295
 
                        # doing the check is 237ms vs 243ms.
1296
 
                        # So slightly better, but I assume the standard 'lots
1297
 
                        # of packs' is going to show a reasonable improvement
1298
 
                        # from the check, because it avoids 'going around
1299
 
                        # again' for everything that is in another index
1300
 
                        # parents_not_on_page.add(key)
1301
 
                        # Missing for some reason
1302
 
                        if key < node.min_key:
1303
 
                            # in the case of bzr.dev, 3.4k/5.3k misses are
1304
 
                            # 'earlier' misses (65%)
1305
 
                            parents_not_on_page.add(key)
1306
 
                        elif key > node.max_key:
1307
 
                            # This parent key would be present on a different
1308
 
                            # LeafNode
1309
 
                            parents_not_on_page.add(key)
1310
 
                        else:
1311
 
                            # assert key != node.min_key and key != node.max_key
1312
 
                            # If it was going to be present, it would be on
1313
 
                            # *this* page, so mark it missing.
1314
 
                            missing_keys.add(key)
1315
 
                parents_to_check = next_parents_to_check.difference(parent_map)
1316
 
                # Might want to do another .difference() from missing_keys
1317
 
        # parents_not_on_page could have been found on a different page, or be
1318
 
        # known to be missing. So cull out everything that has already been
1319
 
        # found.
1320
 
        search_keys = parents_not_on_page.difference(
1321
 
            parent_map).difference(missing_keys)
1322
 
        return search_keys
1323
 
 
1324
1118
    def iter_entries_prefix(self, keys):
1325
1119
        """Iterate over keys within the index using prefix matching.
1326
1120
 
1516
1310
        # list of (offset, length) regions of the file that should, evenually
1517
1311
        # be read in to data_ranges, either from 'bytes' or from the transport
1518
1312
        ranges = []
1519
 
        base_offset = self._base_offset
1520
1313
        for index in nodes:
1521
 
            offset = (index * _PAGE_SIZE)
 
1314
            offset = index * _PAGE_SIZE
1522
1315
            size = _PAGE_SIZE
1523
1316
            if index == 0:
1524
1317
                # Root node - special case
1528
1321
                    # The only case where we don't know the size, is for very
1529
1322
                    # small indexes. So we read the whole thing
1530
1323
                    bytes = self._transport.get_bytes(self._name)
1531
 
                    num_bytes = len(bytes)
1532
 
                    self._size = num_bytes - base_offset
 
1324
                    self._size = len(bytes)
1533
1325
                    # the whole thing should be parsed out of 'bytes'
1534
 
                    ranges = [(start, min(_PAGE_SIZE, num_bytes - start))
1535
 
                        for start in xrange(base_offset, num_bytes, _PAGE_SIZE)]
 
1326
                    ranges.append((0, len(bytes)))
1536
1327
                    break
1537
1328
            else:
1538
1329
                if offset > self._size:
1540
1331
                                         ' of the file %s > %s'
1541
1332
                                         % (offset, self._size))
1542
1333
                size = min(size, self._size - offset)
1543
 
            ranges.append((base_offset + offset, size))
 
1334
            ranges.append((offset, size))
1544
1335
        if not ranges:
1545
1336
            return
1546
1337
        elif bytes is not None:
1547
1338
            # already have the whole file
1548
 
            data_ranges = [(start, bytes[start:start+size])
1549
 
                           for start, size in ranges]
 
1339
            data_ranges = [(start, bytes[start:start+_PAGE_SIZE])
 
1340
                           for start in xrange(0, len(bytes), _PAGE_SIZE)]
1550
1341
        elif self._file is None:
1551
1342
            data_ranges = self._transport.readv(self._name, ranges)
1552
1343
        else:
1555
1346
                self._file.seek(offset)
1556
1347
                data_ranges.append((offset, self._file.read(size)))
1557
1348
        for offset, data in data_ranges:
1558
 
            offset -= base_offset
1559
1349
            if offset == 0:
1560
1350
                # extract the header
1561
1351
                offset, data = self._parse_header_from_bytes(data)
1563
1353
                    continue
1564
1354
            bytes = zlib.decompress(data)
1565
1355
            if bytes.startswith(_LEAF_FLAG):
1566
 
                node = self._leaf_factory(bytes, self._key_length,
1567
 
                                          self.node_ref_lists)
 
1356
                node = _LeafNode(bytes, self._key_length, self.node_ref_lists)
1568
1357
            elif bytes.startswith(_INTERNAL_FLAG):
1569
1358
                node = _InternalNode(bytes)
1570
1359
            else:
1589
1378
            pass
1590
1379
 
1591
1380
 
1592
 
_gcchk_factory = _LeafNode
1593
 
 
1594
1381
try:
1595
 
    from bzrlib import _btree_serializer_pyx as _btree_serializer
1596
 
    _gcchk_factory = _btree_serializer._parse_into_chk
1597
 
except ImportError, e:
1598
 
    osutils.failed_to_load_extension(e)
 
1382
    from bzrlib import _btree_serializer_c as _btree_serializer
 
1383
except ImportError:
1599
1384
    from bzrlib import _btree_serializer_py as _btree_serializer