← Back to branch summary

~bzr-pqm/bzr/bzr.dev

« back to all changes in this revision

Viewing changes to bzrlib/btree_index.py

  • Committer: Tarmac
  • Author(s): Vincent Ladeuil
  • Date: 2017-01-30 14:42:05 UTC
  • mfrom: (6620.1.1 trunk)
  • Revision ID: tarmac-20170130144205-r8fh2xpmiuxyozpv
Merge  2.7 into trunk including fix for bug #1657238 [r=vila]

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-2011 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 array
 
20
from __future__ import absolute_import
 
21
 
 
22
import cStringIO
 
23
 
 
24
from bzrlib.lazy_import import lazy_import
 
25
lazy_import(globals(), """
21
26
import bisect
22
 
from bisect import bisect_right
23
 
from copy import deepcopy
24
27
import math
25
 
import struct
26
28
import tempfile
27
29
import zlib
 
30
""")
28
31
 
29
32
from bzrlib import (
30
33
    chunk_writer,
34
37
    index,
35
38
    lru_cache,
36
39
    osutils,
 
40
    static_tuple,
37
41
    trace,
 
42
    transport,
38
43
    )
39
44
from bzrlib.index import _OPTION_NODE_REFS, _OPTION_KEY_ELEMENTS, _OPTION_LEN
40
 
from bzrlib.transport import get_transport
41
45
 
42
46
 
43
47
_BTSIGNATURE = "B+Tree Graph Index 2\n"
64
68
    def __init__(self):
65
69
        """Create a _BuilderRow."""
66
70
        self.nodes = 0
67
 
        self.spool = tempfile.TemporaryFile()
 
71
        self.spool = None# tempfile.TemporaryFile(prefix='bzr-index-row-')
68
72
        self.writer = None
69
73
 
70
74
    def finish_node(self, pad=True):
71
75
        byte_lines, _, padding = self.writer.finish()
72
76
        if self.nodes == 0:
 
77
            self.spool = cStringIO.StringIO()
73
78
            # padded note:
74
79
            self.spool.write("\x00" * _RESERVED_HEADER_BYTES)
 
80
        elif self.nodes == 1:
 
81
            # We got bigger than 1 node, switch to a temp file
 
82
            spool = tempfile.TemporaryFile(prefix='bzr-index-row-')
 
83
            spool.write(self.spool.getvalue())
 
84
            self.spool = spool
75
85
        skipped_bytes = 0
76
86
        if not pad and padding:
77
87
            del byte_lines[-1]
154
164
        :param references: An iterable of iterables of keys. Each is a
155
165
            reference to another key.
156
166
        :param value: The value to associate with the key. It may be any
157
 
            bytes as long as it does not contain \0 or \n.
 
167
            bytes as long as it does not contain \\0 or \\n.
158
168
        """
 
169
        # Ensure that 'key' is a StaticTuple
 
170
        key = static_tuple.StaticTuple.from_sequence(key).intern()
159
171
        # we don't care about absent_references
160
172
        node_refs, _ = self._check_key_ref_value(key, references, value)
161
173
        if key in self._nodes:
162
174
            raise errors.BadIndexDuplicateKey(key, self)
163
 
        self._nodes[key] = (node_refs, value)
164
 
        self._keys.add(key)
 
175
        self._nodes[key] = static_tuple.StaticTuple(node_refs, value)
165
176
        if self._nodes_by_key is not None and self._key_length > 1:
166
177
            self._update_nodes_by_key(key, value, node_refs)
167
 
        if len(self._keys) < self._spill_at:
 
178
        if len(self._nodes) < self._spill_at:
168
179
            return
169
180
        self._spill_mem_keys_to_disk()
170
181
 
186
197
             backing_pos) = self._spill_mem_keys_and_combine()
187
198
        else:
188
199
            new_backing_file, size = self._spill_mem_keys_without_combining()
189
 
        dir_path, base_name = osutils.split(new_backing_file.name)
190
200
        # Note: The transport here isn't strictly needed, because we will use
191
201
        #       direct access to the new_backing._file object
192
 
        new_backing = BTreeGraphIndex(get_transport(dir_path),
193
 
                                      base_name, size)
 
202
        new_backing = BTreeGraphIndex(transport.get_transport_from_path('.'),
 
203
                                      '<temp>', size)
194
204
        # GC will clean up the file
195
205
        new_backing._file = new_backing_file
196
206
        if self._combine_backing_indices:
201
211
                self._backing_indices[backing_pos] = None
202
212
        else:
203
213
            self._backing_indices.append(new_backing)
204
 
        self._keys = set()
205
214
        self._nodes = {}
206
215
        self._nodes_by_key = None
207
216
 
287
296
            flag when writing out. This is used by the _spill_mem_keys_to_disk
288
297
            functionality.
289
298
        """
 
299
        new_leaf = False
290
300
        if rows[-1].writer is None:
291
301
            # opening a new leaf chunk;
 
302
            new_leaf = True
292
303
            for pos, internal_row in enumerate(rows[:-1]):
293
304
                # flesh out any internal nodes that are needed to
294
305
                # preserve the height of the tree
313
324
                optimize_for_size=self._optimize_for_size)
314
325
            rows[-1].writer.write(_LEAF_FLAG)
315
326
        if rows[-1].writer.write(line):
 
327
            # if we failed to write, despite having an empty page to write to,
 
328
            # then line is too big. raising the error avoids infinite recursion
 
329
            # searching for a suitably large page that will not be found.
 
330
            if new_leaf:
 
331
                raise errors.BadIndexKey(string_key)
316
332
            # this key did not fit in the node:
317
333
            rows[-1].finish_node()
318
334
            key_line = string_key + "\n"
319
335
            new_row = True
320
336
            for row in reversed(rows[:-1]):
321
337
                # Mark the start of the next node in the node above. If it
322
 
                # doesn't fit then propogate upwards until we find one that
 
338
                # doesn't fit then propagate upwards until we find one that
323
339
                # it does fit into.
324
340
                if row.writer.write(key_line):
325
341
                    row.finish_node()
370
386
        self.row_lengths = []
371
387
        # Loop over all nodes adding them to the bottom row
372
388
        # (rows[-1]). When we finish a chunk in a row,
373
 
        # propogate the key that didn't fit (comes after the chunk) to the
 
389
        # propagate the key that didn't fit (comes after the chunk) to the
374
390
        # row above, transitively.
375
391
        for node in node_iterator:
376
392
            if key_count == 0:
383
399
        for row in reversed(rows):
384
400
            pad = (type(row) != _LeafBuilderRow)
385
401
            row.finish_node(pad=pad)
386
 
        result = tempfile.NamedTemporaryFile(prefix='bzr-index-')
387
402
        lines = [_BTSIGNATURE]
388
403
        lines.append(_OPTION_NODE_REFS + str(self.reference_lists) + '\n')
389
404
        lines.append(_OPTION_KEY_ELEMENTS + str(self._key_length) + '\n')
390
405
        lines.append(_OPTION_LEN + str(key_count) + '\n')
391
406
        row_lengths = [row.nodes for row in rows]
392
407
        lines.append(_OPTION_ROW_LENGTHS + ','.join(map(str, row_lengths)) + '\n')
 
408
        if row_lengths and row_lengths[-1] > 1:
 
409
            result = tempfile.NamedTemporaryFile(prefix='bzr-index-')
 
410
        else:
 
411
            result = cStringIO.StringIO()
393
412
        result.writelines(lines)
394
413
        position = sum(map(len, lines))
395
414
        root_row = True
406
425
            # Special case the first node as it may be prefixed
407
426
            node = row.spool.read(_PAGE_SIZE)
408
427
            result.write(node[reserved:])
409
 
            result.write("\x00" * (reserved - position))
 
428
            if len(node) == _PAGE_SIZE:
 
429
                result.write("\x00" * (reserved - position))
410
430
            position = 0 # Only the root row actually has an offset
411
431
            copied_len = osutils.pumpfile(row.spool, result)
412
432
            if copied_len != (row.nodes - 1) * _PAGE_SIZE:
431
451
    def iter_all_entries(self):
432
452
        """Iterate over all keys within the index
433
453
 
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
 
454
        :return: An iterable of (index, key, value, reference_lists). There is
 
455
            no defined order for the result iteration - it will be in the most
436
456
            efficient order for the index (in this case dictionary hash order).
437
457
        """
438
458
        if 'evil' in debug.debug_flags:
457
477
            efficient order for the index (keys iteration order in this case).
458
478
        """
459
479
        keys = set(keys)
460
 
        local_keys = keys.intersection(self._keys)
 
480
        # Note: We don't use keys.intersection() here. If you read the C api,
 
481
        #       set.intersection(other) special cases when other is a set and
 
482
        #       will iterate the smaller of the two and lookup in the other.
 
483
        #       It does *not* do this for any other type (even dict, unlike
 
484
        #       some other set functions.) Since we expect keys is generally <<
 
485
        #       self._nodes, it is faster to iterate over it in a list
 
486
        #       comprehension
 
487
        nodes = self._nodes
 
488
        local_keys = [key for key in keys if key in nodes]
461
489
        if self.reference_lists:
462
490
            for key in local_keys:
463
 
                node = self._nodes[key]
 
491
                node = nodes[key]
464
492
                yield self, key, node[1], node[0]
465
493
        else:
466
494
            for key in local_keys:
467
 
                node = self._nodes[key]
 
495
                node = nodes[key]
468
496
                yield self, key, node[1]
469
497
        # Find things that are in backing indices that have not been handled
470
498
        # yet.
553
581
                    else:
554
582
                        # yield keys
555
583
                        for value in key_dict.itervalues():
556
 
                            yield (self, ) + value
 
584
                            yield (self, ) + tuple(value)
557
585
            else:
558
586
                yield (self, ) + key_dict
559
587
 
580
608
 
581
609
        For InMemoryGraphIndex the estimate is exact.
582
610
        """
583
 
        return len(self._keys) + sum(backing.key_count() for backing in
 
611
        return len(self._nodes) + sum(backing.key_count() for backing in
584
612
            self._backing_indices if backing is not None)
585
613
 
586
614
    def validate(self):
587
615
        """In memory index's have no known corruption at the moment."""
588
616
 
589
617
 
590
 
class _LeafNode(object):
 
618
class _LeafNode(dict):
591
619
    """A leaf node for a serialised B+Tree index."""
592
620
 
 
621
    __slots__ = ('min_key', 'max_key', '_keys')
 
622
 
593
623
    def __init__(self, bytes, key_length, ref_list_length):
594
624
        """Parse bytes to create a leaf node object."""
595
625
        # splitlines mangles the \r delimiters.. don't use it.
596
 
        self.keys = dict(_btree_serializer._parse_leaf_lines(bytes,
597
 
            key_length, ref_list_length))
 
626
        key_list = _btree_serializer._parse_leaf_lines(bytes,
 
627
            key_length, ref_list_length)
 
628
        if key_list:
 
629
            self.min_key = key_list[0][0]
 
630
            self.max_key = key_list[-1][0]
 
631
        else:
 
632
            self.min_key = self.max_key = None
 
633
        super(_LeafNode, self).__init__(key_list)
 
634
        self._keys = dict(self)
 
635
 
 
636
    def all_items(self):
 
637
        """Return a sorted list of (key, (value, refs)) items"""
 
638
        items = self.items()
 
639
        items.sort()
 
640
        return items
 
641
 
 
642
    def all_keys(self):
 
643
        """Return a sorted list of all keys."""
 
644
        keys = self.keys()
 
645
        keys.sort()
 
646
        return keys
598
647
 
599
648
 
600
649
class _InternalNode(object):
601
650
    """An internal node for a serialised B+Tree index."""
602
651
 
 
652
    __slots__ = ('keys', 'offset')
 
653
 
603
654
    def __init__(self, bytes):
604
655
        """Parse bytes to create an internal node object."""
605
656
        # splitlines mangles the \r delimiters.. don't use it.
608
659
    def _parse_lines(self, lines):
609
660
        nodes = []
610
661
        self.offset = int(lines[1][7:])
 
662
        as_st = static_tuple.StaticTuple.from_sequence
611
663
        for line in lines[2:]:
612
664
            if line == '':
613
665
                break
614
 
            nodes.append(tuple(line.split('\0')))
 
666
            nodes.append(as_st(map(intern, line.split('\0'))).intern())
615
667
        return nodes
616
668
 
617
669
 
622
674
    memory except when very large walks are done.
623
675
    """
624
676
 
625
 
    def __init__(self, transport, name, size):
 
677
    def __init__(self, transport, name, size, unlimited_cache=False,
 
678
                 offset=0):
626
679
        """Create a B+Tree index object on the index name.
627
680
 
628
681
        :param transport: The transport to read data for the index from.
632
685
            the initial read (to read the root node header) can be done
633
686
            without over-reading even on empty indices, and on small indices
634
687
            allows single-IO to read the entire index.
 
688
        :param unlimited_cache: If set to True, then instead of using an
 
689
            LRUCache with size _NODE_CACHE_SIZE, we will use a dict and always
 
690
            cache all leaf nodes.
 
691
        :param offset: The start of the btree index data isn't byte 0 of the
 
692
            file. Instead it starts at some point later.
635
693
        """
636
694
        self._transport = transport
637
695
        self._name = name
639
697
        self._file = None
640
698
        self._recommended_pages = self._compute_recommended_pages()
641
699
        self._root_node = None
 
700
        self._base_offset = offset
 
701
        self._leaf_factory = _LeafNode
642
702
        # Default max size is 100,000 leave values
643
703
        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)
 
704
        if unlimited_cache:
 
705
            self._leaf_node_cache = {}
 
706
            self._internal_node_cache = {}
 
707
        else:
 
708
            self._leaf_node_cache = lru_cache.LRUCache(_NODE_CACHE_SIZE)
 
709
            # We use a FIFO here just to prevent possible blowout. However, a
 
710
            # 300k record btree has only 3k leaf nodes, and only 20 internal
 
711
            # nodes. A value of 100 scales to ~100*100*100 = 1M records.
 
712
            self._internal_node_cache = fifo_cache.FIFOCache(100)
650
713
        self._key_count = None
651
714
        self._row_lengths = None
652
715
        self._row_offsets = None # Start of each row, [-1] is the end
684
747
                if start_of_leaves is None:
685
748
                    start_of_leaves = self._row_offsets[-2]
686
749
                if node_pos < start_of_leaves:
687
 
                    self._internal_node_cache.add(node_pos, node)
 
750
                    self._internal_node_cache[node_pos] = node
688
751
                else:
689
 
                    self._leaf_node_cache.add(node_pos, node)
 
752
                    self._leaf_node_cache[node_pos] = node
690
753
            found[node_pos] = node
691
754
        return found
692
755
 
831
894
            new_tips = next_tips
832
895
        return final_offsets
833
896
 
 
897
    def clear_cache(self):
 
898
        """Clear out any cached/memoized values.
 
899
 
 
900
        This can be called at any time, but generally it is used when we have
 
901
        extracted some information, but don't expect to be requesting any more
 
902
        from this index.
 
903
        """
 
904
        # Note that we don't touch self._root_node or self._internal_node_cache
 
905
        # We don't expect either of those to be big, and it can save
 
906
        # round-trips in the future. We may re-evaluate this if InternalNode
 
907
        # memory starts to be an issue.
 
908
        self._leaf_node_cache.clear()
 
909
 
834
910
    def external_references(self, ref_list_num):
835
911
        if self._root_node is None:
836
912
            self._get_root_node()
901
977
        """Cache directly from key => value, skipping the btree."""
902
978
        if self._leaf_value_cache is not None:
903
979
            for node in nodes.itervalues():
904
 
                for key, value in node.keys.iteritems():
 
980
                for key, value in node.all_items():
905
981
                    if key in self._leaf_value_cache:
906
982
                        # Don't add the rest of the keys, we've seen this node
907
983
                        # before.
931
1007
        if self._row_offsets[-1] == 1:
932
1008
            # There is only the root node, and we read that via key_count()
933
1009
            if self.node_ref_lists:
934
 
                for key, (value, refs) in sorted(self._root_node.keys.items()):
 
1010
                for key, (value, refs) in self._root_node.all_items():
935
1011
                    yield (self, key, value, refs)
936
1012
            else:
937
 
                for key, (value, refs) in sorted(self._root_node.keys.items()):
 
1013
                for key, (value, refs) in self._root_node.all_items():
938
1014
                    yield (self, key, value)
939
1015
            return
940
1016
        start_of_leaves = self._row_offsets[-2]
950
1026
        # for spilling index builds to disk.
951
1027
        if self.node_ref_lists:
952
1028
            for _, node in nodes:
953
 
                for key, (value, refs) in sorted(node.keys.items()):
 
1029
                for key, (value, refs) in node.all_items():
954
1030
                    yield (self, key, value, refs)
955
1031
        else:
956
1032
            for _, node in nodes:
957
 
                for key, (value, refs) in sorted(node.keys.items()):
 
1033
                for key, (value, refs) in node.all_items():
958
1034
                    yield (self, key, value)
959
1035
 
960
1036
    @staticmethod
984
1060
        # iter_steps = len(in_keys) + len(fixed_keys)
985
1061
        # bisect_steps = len(in_keys) * math.log(len(fixed_keys), 2)
986
1062
        if len(in_keys) == 1: # Bisect will always be faster for M = 1
987
 
            return [(bisect_right(fixed_keys, in_keys[0]), in_keys)]
 
1063
            return [(bisect.bisect_right(fixed_keys, in_keys[0]), in_keys)]
988
1064
        # elif bisect_steps < iter_steps:
989
1065
        #     offsets = {}
990
1066
        #     for key in in_keys:
1039
1115
            output.append(cur_out)
1040
1116
        return output
1041
1117
 
 
1118
    def _walk_through_internal_nodes(self, keys):
 
1119
        """Take the given set of keys, and find the corresponding LeafNodes.
 
1120
 
 
1121
        :param keys: An unsorted iterable of keys to search for
 
1122
        :return: (nodes, index_and_keys)
 
1123
            nodes is a dict mapping {index: LeafNode}
 
1124
            keys_at_index is a list of tuples of [(index, [keys for Leaf])]
 
1125
        """
 
1126
        # 6 seconds spent in miss_torture using the sorted() line.
 
1127
        # Even with out of order disk IO it seems faster not to sort it when
 
1128
        # large queries are being made.
 
1129
        keys_at_index = [(0, sorted(keys))]
 
1130
 
 
1131
        for row_pos, next_row_start in enumerate(self._row_offsets[1:-1]):
 
1132
            node_indexes = [idx for idx, s_keys in keys_at_index]
 
1133
            nodes = self._get_internal_nodes(node_indexes)
 
1134
 
 
1135
            next_nodes_and_keys = []
 
1136
            for node_index, sub_keys in keys_at_index:
 
1137
                node = nodes[node_index]
 
1138
                positions = self._multi_bisect_right(sub_keys, node.keys)
 
1139
                node_offset = next_row_start + node.offset
 
1140
                next_nodes_and_keys.extend([(node_offset + pos, s_keys)
 
1141
                                           for pos, s_keys in positions])
 
1142
            keys_at_index = next_nodes_and_keys
 
1143
        # We should now be at the _LeafNodes
 
1144
        node_indexes = [idx for idx, s_keys in keys_at_index]
 
1145
 
 
1146
        # TODO: We may *not* want to always read all the nodes in one
 
1147
        #       big go. Consider setting a max size on this.
 
1148
        nodes = self._get_leaf_nodes(node_indexes)
 
1149
        return nodes, keys_at_index
 
1150
 
1042
1151
    def iter_entries(self, keys):
1043
1152
        """Iterate over keys within the index.
1044
1153
 
1082
1191
        needed_keys = keys
1083
1192
        if not needed_keys:
1084
1193
            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)
 
1194
        nodes, nodes_and_keys = self._walk_through_internal_nodes(needed_keys)
1111
1195
        for node_index, sub_keys in nodes_and_keys:
1112
1196
            if not sub_keys:
1113
1197
                continue
1114
1198
            node = nodes[node_index]
1115
1199
            for next_sub_key in sub_keys:
1116
 
                if next_sub_key in node.keys:
1117
 
                    value, refs = node.keys[next_sub_key]
 
1200
                if next_sub_key in node:
 
1201
                    value, refs = node[next_sub_key]
1118
1202
                    if self.node_ref_lists:
1119
1203
                        yield (self, next_sub_key, value, refs)
1120
1204
                    else:
1121
1205
                        yield (self, next_sub_key, value)
1122
1206
 
 
1207
    def _find_ancestors(self, keys, ref_list_num, parent_map, missing_keys):
 
1208
        """Find the parent_map information for the set of keys.
 
1209
 
 
1210
        This populates the parent_map dict and missing_keys set based on the
 
1211
        queried keys. It also can fill out an arbitrary number of parents that
 
1212
        it finds while searching for the supplied keys.
 
1213
 
 
1214
        It is unlikely that you want to call this directly. See
 
1215
        "CombinedGraphIndex.find_ancestry()" for a more appropriate API.
 
1216
 
 
1217
        :param keys: A keys whose ancestry we want to return
 
1218
            Every key will either end up in 'parent_map' or 'missing_keys'.
 
1219
        :param ref_list_num: This index in the ref_lists is the parents we
 
1220
            care about.
 
1221
        :param parent_map: {key: parent_keys} for keys that are present in this
 
1222
            index. This may contain more entries than were in 'keys', that are
 
1223
            reachable ancestors of the keys requested.
 
1224
        :param missing_keys: keys which are known to be missing in this index.
 
1225
            This may include parents that were not directly requested, but we
 
1226
            were able to determine that they are not present in this index.
 
1227
        :return: search_keys    parents that were found but not queried to know
 
1228
            if they are missing or present. Callers can re-query this index for
 
1229
            those keys, and they will be placed into parent_map or missing_keys
 
1230
        """
 
1231
        if not self.key_count():
 
1232
            # We use key_count() to trigger reading the root node and
 
1233
            # determining info about this BTreeGraphIndex
 
1234
            # If we don't have any keys, then everything is missing
 
1235
            missing_keys.update(keys)
 
1236
            return set()
 
1237
        if ref_list_num >= self.node_ref_lists:
 
1238
            raise ValueError('No ref list %d, index has %d ref lists'
 
1239
                % (ref_list_num, self.node_ref_lists))
 
1240
 
 
1241
        # The main trick we are trying to accomplish is that when we find a
 
1242
        # key listing its parents, we expect that the parent key is also likely
 
1243
        # to sit on the same page. Allowing us to expand parents quickly
 
1244
        # without suffering the full stack of bisecting, etc.
 
1245
        nodes, nodes_and_keys = self._walk_through_internal_nodes(keys)
 
1246
 
 
1247
        # These are parent keys which could not be immediately resolved on the
 
1248
        # page where the child was present. Note that we may already be
 
1249
        # searching for that key, and it may actually be present [or known
 
1250
        # missing] on one of the other pages we are reading.
 
1251
        # TODO:
 
1252
        #   We could try searching for them in the immediate previous or next
 
1253
        #   page. If they occur "later" we could put them in a pending lookup
 
1254
        #   set, and then for each node we read thereafter we could check to
 
1255
        #   see if they are present.
 
1256
        #   However, we don't know the impact of keeping this list of things
 
1257
        #   that I'm going to search for every node I come across from here on
 
1258
        #   out.
 
1259
        #   It doesn't handle the case when the parent key is missing on a
 
1260
        #   page that we *don't* read. So we already have to handle being
 
1261
        #   re-entrant for that.
 
1262
        #   Since most keys contain a date string, they are more likely to be
 
1263
        #   found earlier in the file than later, but we would know that right
 
1264
        #   away (key < min_key), and wouldn't keep searching it on every other
 
1265
        #   page that we read.
 
1266
        #   Mostly, it is an idea, one which should be benchmarked.
 
1267
        parents_not_on_page = set()
 
1268
 
 
1269
        for node_index, sub_keys in nodes_and_keys:
 
1270
            if not sub_keys:
 
1271
                continue
 
1272
            # sub_keys is all of the keys we are looking for that should exist
 
1273
            # on this page, if they aren't here, then they won't be found
 
1274
            node = nodes[node_index]
 
1275
            parents_to_check = set()
 
1276
            for next_sub_key in sub_keys:
 
1277
                if next_sub_key not in node:
 
1278
                    # This one is just not present in the index at all
 
1279
                    missing_keys.add(next_sub_key)
 
1280
                else:
 
1281
                    value, refs = node[next_sub_key]
 
1282
                    parent_keys = refs[ref_list_num]
 
1283
                    parent_map[next_sub_key] = parent_keys
 
1284
                    parents_to_check.update(parent_keys)
 
1285
            # Don't look for things we've already found
 
1286
            parents_to_check = parents_to_check.difference(parent_map)
 
1287
            # this can be used to test the benefit of having the check loop
 
1288
            # inlined.
 
1289
            # parents_not_on_page.update(parents_to_check)
 
1290
            # continue
 
1291
            while parents_to_check:
 
1292
                next_parents_to_check = set()
 
1293
                for key in parents_to_check:
 
1294
                    if key in node:
 
1295
                        value, refs = node[key]
 
1296
                        parent_keys = refs[ref_list_num]
 
1297
                        parent_map[key] = parent_keys
 
1298
                        next_parents_to_check.update(parent_keys)
 
1299
                    else:
 
1300
                        # This parent either is genuinely missing, or should be
 
1301
                        # found on another page. Perf test whether it is better
 
1302
                        # to check if this node should fit on this page or not.
 
1303
                        # in the 'everything-in-one-pack' scenario, this *not*
 
1304
                        # doing the check is 237ms vs 243ms.
 
1305
                        # So slightly better, but I assume the standard 'lots
 
1306
                        # of packs' is going to show a reasonable improvement
 
1307
                        # from the check, because it avoids 'going around
 
1308
                        # again' for everything that is in another index
 
1309
                        # parents_not_on_page.add(key)
 
1310
                        # Missing for some reason
 
1311
                        if key < node.min_key:
 
1312
                            # in the case of bzr.dev, 3.4k/5.3k misses are
 
1313
                            # 'earlier' misses (65%)
 
1314
                            parents_not_on_page.add(key)
 
1315
                        elif key > node.max_key:
 
1316
                            # This parent key would be present on a different
 
1317
                            # LeafNode
 
1318
                            parents_not_on_page.add(key)
 
1319
                        else:
 
1320
                            # assert key != node.min_key and key != node.max_key
 
1321
                            # If it was going to be present, it would be on
 
1322
                            # *this* page, so mark it missing.
 
1323
                            missing_keys.add(key)
 
1324
                parents_to_check = next_parents_to_check.difference(parent_map)
 
1325
                # Might want to do another .difference() from missing_keys
 
1326
        # parents_not_on_page could have been found on a different page, or be
 
1327
        # known to be missing. So cull out everything that has already been
 
1328
        # found.
 
1329
        search_keys = parents_not_on_page.difference(
 
1330
            parent_map).difference(missing_keys)
 
1331
        return search_keys
 
1332
 
1123
1333
    def iter_entries_prefix(self, keys):
1124
1334
        """Iterate over keys within the index using prefix matching.
1125
1335
 
1315
1525
        # list of (offset, length) regions of the file that should, evenually
1316
1526
        # be read in to data_ranges, either from 'bytes' or from the transport
1317
1527
        ranges = []
 
1528
        base_offset = self._base_offset
1318
1529
        for index in nodes:
1319
 
            offset = index * _PAGE_SIZE
 
1530
            offset = (index * _PAGE_SIZE)
1320
1531
            size = _PAGE_SIZE
1321
1532
            if index == 0:
1322
1533
                # Root node - special case
1326
1537
                    # The only case where we don't know the size, is for very
1327
1538
                    # small indexes. So we read the whole thing
1328
1539
                    bytes = self._transport.get_bytes(self._name)
1329
 
                    self._size = len(bytes)
 
1540
                    num_bytes = len(bytes)
 
1541
                    self._size = num_bytes - base_offset
1330
1542
                    # the whole thing should be parsed out of 'bytes'
1331
 
                    ranges.append((0, len(bytes)))
 
1543
                    ranges = [(start, min(_PAGE_SIZE, num_bytes - start))
 
1544
                        for start in xrange(base_offset, num_bytes, _PAGE_SIZE)]
1332
1545
                    break
1333
1546
            else:
1334
1547
                if offset > self._size:
1336
1549
                                         ' of the file %s > %s'
1337
1550
                                         % (offset, self._size))
1338
1551
                size = min(size, self._size - offset)
1339
 
            ranges.append((offset, size))
 
1552
            ranges.append((base_offset + offset, size))
1340
1553
        if not ranges:
1341
1554
            return
1342
1555
        elif bytes is not None:
1343
1556
            # already have the whole file
1344
 
            data_ranges = [(start, bytes[start:start+_PAGE_SIZE])
1345
 
                           for start in xrange(0, len(bytes), _PAGE_SIZE)]
 
1557
            data_ranges = [(start, bytes[start:start+size])
 
1558
                           for start, size in ranges]
1346
1559
        elif self._file is None:
1347
1560
            data_ranges = self._transport.readv(self._name, ranges)
1348
1561
        else:
1351
1564
                self._file.seek(offset)
1352
1565
                data_ranges.append((offset, self._file.read(size)))
1353
1566
        for offset, data in data_ranges:
 
1567
            offset -= base_offset
1354
1568
            if offset == 0:
1355
1569
                # extract the header
1356
1570
                offset, data = self._parse_header_from_bytes(data)
1358
1572
                    continue
1359
1573
            bytes = zlib.decompress(data)
1360
1574
            if bytes.startswith(_LEAF_FLAG):
1361
 
                node = _LeafNode(bytes, self._key_length, self.node_ref_lists)
 
1575
                node = self._leaf_factory(bytes, self._key_length,
 
1576
                                          self.node_ref_lists)
1362
1577
            elif bytes.startswith(_INTERNAL_FLAG):
1363
1578
                node = _InternalNode(bytes)
1364
1579
            else:
1383
1598
            pass
1384
1599
 
1385
1600
 
 
1601
_gcchk_factory = _LeafNode
 
1602
 
1386
1603
try:
1387
 
    from bzrlib import _btree_serializer_c as _btree_serializer
1388
 
except ImportError:
 
1604
    from bzrlib import _btree_serializer_pyx as _btree_serializer
 
1605
    _gcchk_factory = _btree_serializer._parse_into_chk
 
1606
except ImportError, e:
 
1607
    osutils.failed_to_load_extension(e)
1389
1608
    from bzrlib import _btree_serializer_py as _btree_serializer