← Back to branch summary

~bzr-pqm/bzr/bzr.dev

« back to all changes in this revision

Viewing changes to bzrlib/btree_index.py

  • Committer: Jelmer Vernooij
  • Date: 2010-08-23 20:37:18 UTC
  • mto: This revision was merged to the branch mainline in revision 5389.
  • Revision ID: jelmer@samba.org-20100823203718-1fj7rrjsiaxedkp7
Provide bzrlib.bzrdir.format_registry.

Show diffs side-by-side

added added

removed removed

Lines of Context:
bzrlib/btree_index.py
1
 
# Copyright (C) 2008 Canonical Ltd
 
1
# Copyright (C) 2008, 2009, 2010 Canonical Ltd
2
2
#
3
3
# This program is free software; you can redistribute it and/or modify
4
4
# it under the terms of the GNU General Public License as published by
17
17
 
18
18
"""B+Tree indices"""
19
19
 
20
 
import array
21
 
import bisect
 
20
import cStringIO
22
21
from bisect import bisect_right
23
 
from copy import deepcopy
24
22
import math
25
 
import struct
26
23
import tempfile
27
24
import zlib
28
25
 
34
31
    index,
35
32
    lru_cache,
36
33
    osutils,
 
34
    static_tuple,
37
35
    trace,
 
36
    transport,
38
37
    )
39
38
from bzrlib.index import _OPTION_NODE_REFS, _OPTION_KEY_ELEMENTS, _OPTION_LEN
40
 
from bzrlib.transport import get_transport
41
39
 
42
40
 
43
41
_BTSIGNATURE = "B+Tree Graph Index 2\n"
64
62
    def __init__(self):
65
63
        """Create a _BuilderRow."""
66
64
        self.nodes = 0
67
 
        self.spool = tempfile.TemporaryFile()
 
65
        self.spool = None# tempfile.TemporaryFile(prefix='bzr-index-row-')
68
66
        self.writer = None
69
67
 
70
68
    def finish_node(self, pad=True):
71
69
        byte_lines, _, padding = self.writer.finish()
72
70
        if self.nodes == 0:
 
71
            self.spool = cStringIO.StringIO()
73
72
            # padded note:
74
73
            self.spool.write("\x00" * _RESERVED_HEADER_BYTES)
 
74
        elif self.nodes == 1:
 
75
            # We got bigger than 1 node, switch to a temp file
 
76
            spool = tempfile.TemporaryFile(prefix='bzr-index-row-')
 
77
            spool.write(self.spool.getvalue())
 
78
            self.spool = spool
75
79
        skipped_bytes = 0
76
80
        if not pad and padding:
77
81
            del byte_lines[-1]
156
160
        :param value: The value to associate with the key. It may be any
157
161
            bytes as long as it does not contain \0 or \n.
158
162
        """
 
163
        # Ensure that 'key' is a StaticTuple
 
164
        key = static_tuple.StaticTuple.from_sequence(key).intern()
159
165
        # we don't care about absent_references
160
166
        node_refs, _ = self._check_key_ref_value(key, references, value)
161
167
        if key in self._nodes:
162
168
            raise errors.BadIndexDuplicateKey(key, self)
163
 
        self._nodes[key] = (node_refs, value)
164
 
        self._keys.add(key)
 
169
        self._nodes[key] = static_tuple.StaticTuple(node_refs, value)
165
170
        if self._nodes_by_key is not None and self._key_length > 1:
166
171
            self._update_nodes_by_key(key, value, node_refs)
167
 
        if len(self._keys) < self._spill_at:
 
172
        if len(self._nodes) < self._spill_at:
168
173
            return
169
174
        self._spill_mem_keys_to_disk()
170
175
 
186
191
             backing_pos) = self._spill_mem_keys_and_combine()
187
192
        else:
188
193
            new_backing_file, size = self._spill_mem_keys_without_combining()
189
 
        dir_path, base_name = osutils.split(new_backing_file.name)
190
194
        # Note: The transport here isn't strictly needed, because we will use
191
195
        #       direct access to the new_backing._file object
192
 
        new_backing = BTreeGraphIndex(get_transport(dir_path),
193
 
                                      base_name, size)
 
196
        new_backing = BTreeGraphIndex(transport.get_transport('.'),
 
197
                                      '<temp>', size)
194
198
        # GC will clean up the file
195
199
        new_backing._file = new_backing_file
196
200
        if self._combine_backing_indices:
201
205
                self._backing_indices[backing_pos] = None
202
206
        else:
203
207
            self._backing_indices.append(new_backing)
204
 
        self._keys = set()
205
208
        self._nodes = {}
206
209
        self._nodes_by_key = None
207
210
 
319
322
            new_row = True
320
323
            for row in reversed(rows[:-1]):
321
324
                # 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
 
325
                # doesn't fit then propagate upwards until we find one that
323
326
                # it does fit into.
324
327
                if row.writer.write(key_line):
325
328
                    row.finish_node()
370
373
        self.row_lengths = []
371
374
        # Loop over all nodes adding them to the bottom row
372
375
        # (rows[-1]). When we finish a chunk in a row,
373
 
        # propogate the key that didn't fit (comes after the chunk) to the
 
376
        # propagate the key that didn't fit (comes after the chunk) to the
374
377
        # row above, transitively.
375
378
        for node in node_iterator:
376
379
            if key_count == 0:
383
386
        for row in reversed(rows):
384
387
            pad = (type(row) != _LeafBuilderRow)
385
388
            row.finish_node(pad=pad)
386
 
        result = tempfile.NamedTemporaryFile(prefix='bzr-index-')
387
389
        lines = [_BTSIGNATURE]
388
390
        lines.append(_OPTION_NODE_REFS + str(self.reference_lists) + '\n')
389
391
        lines.append(_OPTION_KEY_ELEMENTS + str(self._key_length) + '\n')
390
392
        lines.append(_OPTION_LEN + str(key_count) + '\n')
391
393
        row_lengths = [row.nodes for row in rows]
392
394
        lines.append(_OPTION_ROW_LENGTHS + ','.join(map(str, row_lengths)) + '\n')
 
395
        if row_lengths and row_lengths[-1] > 1:
 
396
            result = tempfile.NamedTemporaryFile(prefix='bzr-index-')
 
397
        else:
 
398
            result = cStringIO.StringIO()
393
399
        result.writelines(lines)
394
400
        position = sum(map(len, lines))
395
401
        root_row = True
406
412
            # Special case the first node as it may be prefixed
407
413
            node = row.spool.read(_PAGE_SIZE)
408
414
            result.write(node[reserved:])
409
 
            result.write("\x00" * (reserved - position))
 
415
            if len(node) == _PAGE_SIZE:
 
416
                result.write("\x00" * (reserved - position))
410
417
            position = 0 # Only the root row actually has an offset
411
418
            copied_len = osutils.pumpfile(row.spool, result)
412
419
            if copied_len != (row.nodes - 1) * _PAGE_SIZE:
431
438
    def iter_all_entries(self):
432
439
        """Iterate over all keys within the index
433
440
 
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
 
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
436
443
            efficient order for the index (in this case dictionary hash order).
437
444
        """
438
445
        if 'evil' in debug.debug_flags:
457
464
            efficient order for the index (keys iteration order in this case).
458
465
        """
459
466
        keys = set(keys)
460
 
        local_keys = keys.intersection(self._keys)
 
467
        # Note: We don't use keys.intersection() here. If you read the C api,
 
468
        #       set.intersection(other) special cases when other is a set and
 
469
        #       will iterate the smaller of the two and lookup in the other.
 
470
        #       It does *not* do this for any other type (even dict, unlike
 
471
        #       some other set functions.) Since we expect keys is generally <<
 
472
        #       self._nodes, it is faster to iterate over it in a list
 
473
        #       comprehension
 
474
        nodes = self._nodes
 
475
        local_keys = [key for key in keys if key in nodes]
461
476
        if self.reference_lists:
462
477
            for key in local_keys:
463
 
                node = self._nodes[key]
 
478
                node = nodes[key]
464
479
                yield self, key, node[1], node[0]
465
480
        else:
466
481
            for key in local_keys:
467
 
                node = self._nodes[key]
 
482
                node = nodes[key]
468
483
                yield self, key, node[1]
469
484
        # Find things that are in backing indices that have not been handled
470
485
        # yet.
553
568
                    else:
554
569
                        # yield keys
555
570
                        for value in key_dict.itervalues():
556
 
                            yield (self, ) + value
 
571
                            yield (self, ) + tuple(value)
557
572
            else:
558
573
                yield (self, ) + key_dict
559
574
 
580
595
 
581
596
        For InMemoryGraphIndex the estimate is exact.
582
597
        """
583
 
        return len(self._keys) + sum(backing.key_count() for backing in
 
598
        return len(self._nodes) + sum(backing.key_count() for backing in
584
599
            self._backing_indices if backing is not None)
585
600
 
586
601
    def validate(self):
590
605
class _LeafNode(object):
591
606
    """A leaf node for a serialised B+Tree index."""
592
607
 
 
608
    __slots__ = ('keys', 'min_key', 'max_key')
 
609
 
593
610
    def __init__(self, bytes, key_length, ref_list_length):
594
611
        """Parse bytes to create a leaf node object."""
595
612
        # 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))
 
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
        self.keys = dict(key_list)
598
621
 
599
622
 
600
623
class _InternalNode(object):
601
624
    """An internal node for a serialised B+Tree index."""
602
625
 
 
626
    __slots__ = ('keys', 'offset')
 
627
 
603
628
    def __init__(self, bytes):
604
629
        """Parse bytes to create an internal node object."""
605
630
        # splitlines mangles the \r delimiters.. don't use it.
608
633
    def _parse_lines(self, lines):
609
634
        nodes = []
610
635
        self.offset = int(lines[1][7:])
 
636
        as_st = static_tuple.StaticTuple.from_sequence
611
637
        for line in lines[2:]:
612
638
            if line == '':
613
639
                break
614
 
            nodes.append(tuple(line.split('\0')))
 
640
            nodes.append(as_st(map(intern, line.split('\0'))).intern())
615
641
        return nodes
616
642
 
617
643
 
622
648
    memory except when very large walks are done.
623
649
    """
624
650
 
625
 
    def __init__(self, transport, name, size):
 
651
    def __init__(self, transport, name, size, unlimited_cache=False,
 
652
                 offset=0):
626
653
        """Create a B+Tree index object on the index name.
627
654
 
628
655
        :param transport: The transport to read data for the index from.
632
659
            the initial read (to read the root node header) can be done
633
660
            without over-reading even on empty indices, and on small indices
634
661
            allows single-IO to read the entire index.
 
662
        :param unlimited_cache: If set to True, then instead of using an
 
663
            LRUCache with size _NODE_CACHE_SIZE, we will use a dict and always
 
664
            cache all leaf nodes.
 
665
        :param offset: The start of the btree index data isn't byte 0 of the
 
666
            file. Instead it starts at some point later.
635
667
        """
636
668
        self._transport = transport
637
669
        self._name = name
639
671
        self._file = None
640
672
        self._recommended_pages = self._compute_recommended_pages()
641
673
        self._root_node = None
 
674
        self._base_offset = offset
642
675
        # Default max size is 100,000 leave values
643
676
        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)
 
677
        if unlimited_cache:
 
678
            self._leaf_node_cache = {}
 
679
            self._internal_node_cache = {}
 
680
        else:
 
681
            self._leaf_node_cache = lru_cache.LRUCache(_NODE_CACHE_SIZE)
 
682
            # We use a FIFO here just to prevent possible blowout. However, a
 
683
            # 300k record btree has only 3k leaf nodes, and only 20 internal
 
684
            # nodes. A value of 100 scales to ~100*100*100 = 1M records.
 
685
            self._internal_node_cache = fifo_cache.FIFOCache(100)
650
686
        self._key_count = None
651
687
        self._row_lengths = None
652
688
        self._row_offsets = None # Start of each row, [-1] is the end
684
720
                if start_of_leaves is None:
685
721
                    start_of_leaves = self._row_offsets[-2]
686
722
                if node_pos < start_of_leaves:
687
 
                    self._internal_node_cache.add(node_pos, node)
 
723
                    self._internal_node_cache[node_pos] = node
688
724
                else:
689
 
                    self._leaf_node_cache.add(node_pos, node)
 
725
                    self._leaf_node_cache[node_pos] = node
690
726
            found[node_pos] = node
691
727
        return found
692
728
 
831
867
            new_tips = next_tips
832
868
        return final_offsets
833
869
 
 
870
    def clear_cache(self):
 
871
        """Clear out any cached/memoized values.
 
872
 
 
873
        This can be called at any time, but generally it is used when we have
 
874
        extracted some information, but don't expect to be requesting any more
 
875
        from this index.
 
876
        """
 
877
        # Note that we don't touch self._root_node or self._internal_node_cache
 
878
        # We don't expect either of those to be big, and it can save
 
879
        # round-trips in the future. We may re-evaluate this if InternalNode
 
880
        # memory starts to be an issue.
 
881
        self._leaf_node_cache.clear()
 
882
 
834
883
    def external_references(self, ref_list_num):
835
884
        if self._root_node is None:
836
885
            self._get_root_node()
1039
1088
            output.append(cur_out)
1040
1089
        return output
1041
1090
 
 
1091
    def _walk_through_internal_nodes(self, keys):
 
1092
        """Take the given set of keys, and find the corresponding LeafNodes.
 
1093
 
 
1094
        :param keys: An unsorted iterable of keys to search for
 
1095
        :return: (nodes, index_and_keys)
 
1096
            nodes is a dict mapping {index: LeafNode}
 
1097
            keys_at_index is a list of tuples of [(index, [keys for Leaf])]
 
1098
        """
 
1099
        # 6 seconds spent in miss_torture using the sorted() line.
 
1100
        # Even with out of order disk IO it seems faster not to sort it when
 
1101
        # large queries are being made.
 
1102
        keys_at_index = [(0, sorted(keys))]
 
1103
 
 
1104
        for row_pos, next_row_start in enumerate(self._row_offsets[1:-1]):
 
1105
            node_indexes = [idx for idx, s_keys in keys_at_index]
 
1106
            nodes = self._get_internal_nodes(node_indexes)
 
1107
 
 
1108
            next_nodes_and_keys = []
 
1109
            for node_index, sub_keys in keys_at_index:
 
1110
                node = nodes[node_index]
 
1111
                positions = self._multi_bisect_right(sub_keys, node.keys)
 
1112
                node_offset = next_row_start + node.offset
 
1113
                next_nodes_and_keys.extend([(node_offset + pos, s_keys)
 
1114
                                           for pos, s_keys in positions])
 
1115
            keys_at_index = next_nodes_and_keys
 
1116
        # We should now be at the _LeafNodes
 
1117
        node_indexes = [idx for idx, s_keys in keys_at_index]
 
1118
 
 
1119
        # TODO: We may *not* want to always read all the nodes in one
 
1120
        #       big go. Consider setting a max size on this.
 
1121
        nodes = self._get_leaf_nodes(node_indexes)
 
1122
        return nodes, keys_at_index
 
1123
 
1042
1124
    def iter_entries(self, keys):
1043
1125
        """Iterate over keys within the index.
1044
1126
 
1082
1164
        needed_keys = keys
1083
1165
        if not needed_keys:
1084
1166
            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)
 
1167
        nodes, nodes_and_keys = self._walk_through_internal_nodes(needed_keys)
1111
1168
        for node_index, sub_keys in nodes_and_keys:
1112
1169
            if not sub_keys:
1113
1170
                continue
1120
1177
                    else:
1121
1178
                        yield (self, next_sub_key, value)
1122
1179
 
 
1180
    def _find_ancestors(self, keys, ref_list_num, parent_map, missing_keys):
 
1181
        """Find the parent_map information for the set of keys.
 
1182
 
 
1183
        This populates the parent_map dict and missing_keys set based on the
 
1184
        queried keys. It also can fill out an arbitrary number of parents that
 
1185
        it finds while searching for the supplied keys.
 
1186
 
 
1187
        It is unlikely that you want to call this directly. See
 
1188
        "CombinedGraphIndex.find_ancestry()" for a more appropriate API.
 
1189
 
 
1190
        :param keys: A keys whose ancestry we want to return
 
1191
            Every key will either end up in 'parent_map' or 'missing_keys'.
 
1192
        :param ref_list_num: This index in the ref_lists is the parents we
 
1193
            care about.
 
1194
        :param parent_map: {key: parent_keys} for keys that are present in this
 
1195
            index. This may contain more entries than were in 'keys', that are
 
1196
            reachable ancestors of the keys requested.
 
1197
        :param missing_keys: keys which are known to be missing in this index.
 
1198
            This may include parents that were not directly requested, but we
 
1199
            were able to determine that they are not present in this index.
 
1200
        :return: search_keys    parents that were found but not queried to know
 
1201
            if they are missing or present. Callers can re-query this index for
 
1202
            those keys, and they will be placed into parent_map or missing_keys
 
1203
        """
 
1204
        if not self.key_count():
 
1205
            # We use key_count() to trigger reading the root node and
 
1206
            # determining info about this BTreeGraphIndex
 
1207
            # If we don't have any keys, then everything is missing
 
1208
            missing_keys.update(keys)
 
1209
            return set()
 
1210
        if ref_list_num >= self.node_ref_lists:
 
1211
            raise ValueError('No ref list %d, index has %d ref lists'
 
1212
                % (ref_list_num, self.node_ref_lists))
 
1213
 
 
1214
        # The main trick we are trying to accomplish is that when we find a
 
1215
        # key listing its parents, we expect that the parent key is also likely
 
1216
        # to sit on the same page. Allowing us to expand parents quickly
 
1217
        # without suffering the full stack of bisecting, etc.
 
1218
        nodes, nodes_and_keys = self._walk_through_internal_nodes(keys)
 
1219
 
 
1220
        # These are parent keys which could not be immediately resolved on the
 
1221
        # page where the child was present. Note that we may already be
 
1222
        # searching for that key, and it may actually be present [or known
 
1223
        # missing] on one of the other pages we are reading.
 
1224
        # TODO:
 
1225
        #   We could try searching for them in the immediate previous or next
 
1226
        #   page. If they occur "later" we could put them in a pending lookup
 
1227
        #   set, and then for each node we read thereafter we could check to
 
1228
        #   see if they are present.
 
1229
        #   However, we don't know the impact of keeping this list of things
 
1230
        #   that I'm going to search for every node I come across from here on
 
1231
        #   out.
 
1232
        #   It doesn't handle the case when the parent key is missing on a
 
1233
        #   page that we *don't* read. So we already have to handle being
 
1234
        #   re-entrant for that.
 
1235
        #   Since most keys contain a date string, they are more likely to be
 
1236
        #   found earlier in the file than later, but we would know that right
 
1237
        #   away (key < min_key), and wouldn't keep searching it on every other
 
1238
        #   page that we read.
 
1239
        #   Mostly, it is an idea, one which should be benchmarked.
 
1240
        parents_not_on_page = set()
 
1241
 
 
1242
        for node_index, sub_keys in nodes_and_keys:
 
1243
            if not sub_keys:
 
1244
                continue
 
1245
            # sub_keys is all of the keys we are looking for that should exist
 
1246
            # on this page, if they aren't here, then they won't be found
 
1247
            node = nodes[node_index]
 
1248
            node_keys = node.keys
 
1249
            parents_to_check = set()
 
1250
            for next_sub_key in sub_keys:
 
1251
                if next_sub_key not in node_keys:
 
1252
                    # This one is just not present in the index at all
 
1253
                    missing_keys.add(next_sub_key)
 
1254
                else:
 
1255
                    value, refs = node_keys[next_sub_key]
 
1256
                    parent_keys = refs[ref_list_num]
 
1257
                    parent_map[next_sub_key] = parent_keys
 
1258
                    parents_to_check.update(parent_keys)
 
1259
            # Don't look for things we've already found
 
1260
            parents_to_check = parents_to_check.difference(parent_map)
 
1261
            # this can be used to test the benefit of having the check loop
 
1262
            # inlined.
 
1263
            # parents_not_on_page.update(parents_to_check)
 
1264
            # continue
 
1265
            while parents_to_check:
 
1266
                next_parents_to_check = set()
 
1267
                for key in parents_to_check:
 
1268
                    if key in node_keys:
 
1269
                        value, refs = node_keys[key]
 
1270
                        parent_keys = refs[ref_list_num]
 
1271
                        parent_map[key] = parent_keys
 
1272
                        next_parents_to_check.update(parent_keys)
 
1273
                    else:
 
1274
                        # This parent either is genuinely missing, or should be
 
1275
                        # found on another page. Perf test whether it is better
 
1276
                        # to check if this node should fit on this page or not.
 
1277
                        # in the 'everything-in-one-pack' scenario, this *not*
 
1278
                        # doing the check is 237ms vs 243ms.
 
1279
                        # So slightly better, but I assume the standard 'lots
 
1280
                        # of packs' is going to show a reasonable improvement
 
1281
                        # from the check, because it avoids 'going around
 
1282
                        # again' for everything that is in another index
 
1283
                        # parents_not_on_page.add(key)
 
1284
                        # Missing for some reason
 
1285
                        if key < node.min_key:
 
1286
                            # in the case of bzr.dev, 3.4k/5.3k misses are
 
1287
                            # 'earlier' misses (65%)
 
1288
                            parents_not_on_page.add(key)
 
1289
                        elif key > node.max_key:
 
1290
                            # This parent key would be present on a different
 
1291
                            # LeafNode
 
1292
                            parents_not_on_page.add(key)
 
1293
                        else:
 
1294
                            # assert key != node.min_key and key != node.max_key
 
1295
                            # If it was going to be present, it would be on
 
1296
                            # *this* page, so mark it missing.
 
1297
                            missing_keys.add(key)
 
1298
                parents_to_check = next_parents_to_check.difference(parent_map)
 
1299
                # Might want to do another .difference() from missing_keys
 
1300
        # parents_not_on_page could have been found on a different page, or be
 
1301
        # known to be missing. So cull out everything that has already been
 
1302
        # found.
 
1303
        search_keys = parents_not_on_page.difference(
 
1304
            parent_map).difference(missing_keys)
 
1305
        return search_keys
 
1306
 
1123
1307
    def iter_entries_prefix(self, keys):
1124
1308
        """Iterate over keys within the index using prefix matching.
1125
1309
 
1315
1499
        # list of (offset, length) regions of the file that should, evenually
1316
1500
        # be read in to data_ranges, either from 'bytes' or from the transport
1317
1501
        ranges = []
 
1502
        base_offset = self._base_offset
1318
1503
        for index in nodes:
1319
 
            offset = index * _PAGE_SIZE
 
1504
            offset = (index * _PAGE_SIZE)
1320
1505
            size = _PAGE_SIZE
1321
1506
            if index == 0:
1322
1507
                # Root node - special case
1326
1511
                    # The only case where we don't know the size, is for very
1327
1512
                    # small indexes. So we read the whole thing
1328
1513
                    bytes = self._transport.get_bytes(self._name)
1329
 
                    self._size = len(bytes)
 
1514
                    num_bytes = len(bytes)
 
1515
                    self._size = num_bytes - base_offset
1330
1516
                    # the whole thing should be parsed out of 'bytes'
1331
 
                    ranges.append((0, len(bytes)))
 
1517
                    ranges = [(start, min(_PAGE_SIZE, num_bytes - start))
 
1518
                        for start in xrange(base_offset, num_bytes, _PAGE_SIZE)]
1332
1519
                    break
1333
1520
            else:
1334
1521
                if offset > self._size:
1336
1523
                                         ' of the file %s > %s'
1337
1524
                                         % (offset, self._size))
1338
1525
                size = min(size, self._size - offset)
1339
 
            ranges.append((offset, size))
 
1526
            ranges.append((base_offset + offset, size))
1340
1527
        if not ranges:
1341
1528
            return
1342
1529
        elif bytes is not None:
1343
1530
            # already have the whole file
1344
 
            data_ranges = [(start, bytes[start:start+_PAGE_SIZE])
1345
 
                           for start in xrange(0, len(bytes), _PAGE_SIZE)]
 
1531
            data_ranges = [(start, bytes[start:start+size])
 
1532
                           for start, size in ranges]
1346
1533
        elif self._file is None:
1347
1534
            data_ranges = self._transport.readv(self._name, ranges)
1348
1535
        else:
1351
1538
                self._file.seek(offset)
1352
1539
                data_ranges.append((offset, self._file.read(size)))
1353
1540
        for offset, data in data_ranges:
 
1541
            offset -= base_offset
1354
1542
            if offset == 0:
1355
1543
                # extract the header
1356
1544
                offset, data = self._parse_header_from_bytes(data)
1384
1572
 
1385
1573
 
1386
1574
try:
1387
 
    from bzrlib import _btree_serializer_c as _btree_serializer
1388
 
except ImportError:
 
1575
    from bzrlib import _btree_serializer_pyx as _btree_serializer
 
1576
except ImportError, e:
 
1577
    osutils.failed_to_load_extension(e)
1389
1578
    from bzrlib import _btree_serializer_py as _btree_serializer