~bzr-pqm/bzr/bzr.dev

« back to all changes in this revision

Viewing changes to bzrlib/btree_index.py

  • Committer: John Arbash Meinel
  • Date: 2008-09-02 18:51:03 UTC
  • mto: This revision was merged to the branch mainline in revision 3680.
  • Revision ID: john@arbash-meinel.com-20080902185103-camvrjyw7a9efpno
Change from using AssertionError to using DirstateCorrupt in a few places

Show diffs side-by-side

added added

removed removed

Lines of Context:
1
 
# Copyright (C) 2008, 2009, 2010 Canonical Ltd
 
1
# Copyright (C) 2008 Canonical Ltd
2
2
#
3
3
# This program is free software; you can redistribute it and/or modify
4
4
# it under the terms of the GNU General Public License as published by
12
12
#
13
13
# You should have received a copy of the GNU General Public License
14
14
# along with this program; if not, write to the Free Software
15
 
# Foundation, Inc., 51 Franklin Street, Fifth Floor, Boston, MA 02110-1301 USA
 
15
# Foundation, Inc., 59 Temple Place, Suite 330, Boston, MA  02111-1307  USA
16
16
#
17
17
 
18
18
"""B+Tree indices"""
19
19
 
20
 
import cStringIO
 
20
import array
 
21
import bisect
21
22
from bisect import bisect_right
 
23
from copy import deepcopy
22
24
import math
 
25
import sha
 
26
import struct
23
27
import tempfile
24
28
import zlib
25
29
 
27
31
    chunk_writer,
28
32
    debug,
29
33
    errors,
30
 
    fifo_cache,
31
34
    index,
32
35
    lru_cache,
33
36
    osutils,
34
 
    static_tuple,
35
37
    trace,
36
38
    )
37
39
from bzrlib.index import _OPTION_NODE_REFS, _OPTION_KEY_ELEMENTS, _OPTION_LEN
 
40
from bzrlib.osutils import basename, dirname
38
41
from bzrlib.transport import get_transport
39
42
 
40
43
 
62
65
    def __init__(self):
63
66
        """Create a _BuilderRow."""
64
67
        self.nodes = 0
65
 
        self.spool = None# tempfile.TemporaryFile(prefix='bzr-index-row-')
 
68
        self.spool = tempfile.TemporaryFile()
66
69
        self.writer = None
67
70
 
68
71
    def finish_node(self, pad=True):
69
72
        byte_lines, _, padding = self.writer.finish()
70
73
        if self.nodes == 0:
71
 
            self.spool = cStringIO.StringIO()
72
74
            # padded note:
73
75
            self.spool.write("\x00" * _RESERVED_HEADER_BYTES)
74
 
        elif self.nodes == 1:
75
 
            # We got bigger than 1 node, switch to a temp file
76
 
            spool = tempfile.TemporaryFile(prefix='bzr-index-row-')
77
 
            spool.write(self.spool.getvalue())
78
 
            self.spool = spool
79
76
        skipped_bytes = 0
80
77
        if not pad and padding:
81
78
            del byte_lines[-1]
82
79
            skipped_bytes = padding
83
80
        self.spool.writelines(byte_lines)
84
 
        remainder = (self.spool.tell() + skipped_bytes) % _PAGE_SIZE
85
 
        if remainder != 0:
86
 
            raise AssertionError("incorrect node length: %d, %d"
87
 
                                 % (self.spool.tell(), remainder))
 
81
        if (self.spool.tell() + skipped_bytes) % _PAGE_SIZE != 0:
 
82
            raise AssertionError("incorrect node length")
88
83
        self.nodes += 1
89
84
        self.writer = None
90
85
 
140
135
            key_elements=key_elements)
141
136
        self._spill_at = spill_at
142
137
        self._backing_indices = []
143
 
        # A map of {key: (node_refs, value)}
144
 
        self._nodes = {}
145
 
        # Indicate it hasn't been built yet
146
 
        self._nodes_by_key = None
147
 
        self._optimize_for_size = False
148
138
 
149
139
    def add_node(self, key, value, references=()):
150
140
        """Add a node to the index.
160
150
        :param value: The value to associate with the key. It may be any
161
151
            bytes as long as it does not contain \0 or \n.
162
152
        """
163
 
        # Ensure that 'key' is a StaticTuple
164
 
        key = static_tuple.StaticTuple.from_sequence(key).intern()
165
 
        # we don't care about absent_references
166
 
        node_refs, _ = self._check_key_ref_value(key, references, value)
167
 
        if key in self._nodes:
168
 
            raise errors.BadIndexDuplicateKey(key, self)
169
 
        self._nodes[key] = static_tuple.StaticTuple(node_refs, value)
170
 
        if self._nodes_by_key is not None and self._key_length > 1:
171
 
            self._update_nodes_by_key(key, value, node_refs)
172
 
        if len(self._nodes) < self._spill_at:
 
153
        index.GraphIndexBuilder.add_node(self, key, value, references=references)
 
154
        if len(self._keys) < self._spill_at:
173
155
            return
174
 
        self._spill_mem_keys_to_disk()
175
 
 
176
 
    def _spill_mem_keys_to_disk(self):
177
 
        """Write the in memory keys down to disk to cap memory consumption.
178
 
 
179
 
        If we already have some keys written to disk, we will combine them so
180
 
        as to preserve the sorted order.  The algorithm for combining uses
181
 
        powers of two.  So on the first spill, write all mem nodes into a
182
 
        single index. On the second spill, combine the mem nodes with the nodes
183
 
        on disk to create a 2x sized disk index and get rid of the first index.
184
 
        On the third spill, create a single new disk index, which will contain
185
 
        the mem nodes, and preserve the existing 2x sized index.  On the fourth,
186
 
        combine mem with the first and second indexes, creating a new one of
187
 
        size 4x. On the fifth create a single new one, etc.
188
 
        """
189
 
        if self._combine_backing_indices:
190
 
            (new_backing_file, size,
191
 
             backing_pos) = self._spill_mem_keys_and_combine()
192
 
        else:
193
 
            new_backing_file, size = self._spill_mem_keys_without_combining()
194
 
        # Note: The transport here isn't strictly needed, because we will use
195
 
        #       direct access to the new_backing._file object
196
 
        new_backing = BTreeGraphIndex(get_transport('.'), '<temp>', size)
197
 
        # GC will clean up the file
198
 
        new_backing._file = new_backing_file
199
 
        if self._combine_backing_indices:
200
 
            if len(self._backing_indices) == backing_pos:
201
 
                self._backing_indices.append(None)
202
 
            self._backing_indices[backing_pos] = new_backing
203
 
            for backing_pos in range(backing_pos):
204
 
                self._backing_indices[backing_pos] = None
205
 
        else:
206
 
            self._backing_indices.append(new_backing)
207
 
        self._nodes = {}
208
 
        self._nodes_by_key = None
209
 
 
210
 
    def _spill_mem_keys_without_combining(self):
211
 
        return self._write_nodes(self._iter_mem_nodes(), allow_optimize=False)
212
 
 
213
 
    def _spill_mem_keys_and_combine(self):
214
 
        iterators_to_combine = [self._iter_mem_nodes()]
 
156
        iterators_to_combine = [iter(sorted(self._iter_mem_nodes()))]
215
157
        pos = -1
216
158
        for pos, backing in enumerate(self._backing_indices):
217
159
            if backing is None:
220
162
            iterators_to_combine.append(backing.iter_all_entries())
221
163
        backing_pos = pos + 1
222
164
        new_backing_file, size = \
223
 
            self._write_nodes(self._iter_smallest(iterators_to_combine),
224
 
                              allow_optimize=False)
225
 
        return new_backing_file, size, backing_pos
 
165
            self._write_nodes(self._iter_smallest(iterators_to_combine))
 
166
        new_backing = BTreeGraphIndex(
 
167
            get_transport(dirname(new_backing_file.name)),
 
168
            basename(new_backing_file.name), size)
 
169
        # GC will clean up the file
 
170
        new_backing._file = new_backing_file
 
171
        if len(self._backing_indices) == backing_pos:
 
172
            self._backing_indices.append(None)
 
173
        self._backing_indices[backing_pos] = new_backing
 
174
        for pos in range(backing_pos):
 
175
            self._backing_indices[pos] = None
 
176
        self._keys = set()
 
177
        self._nodes = {}
 
178
        self._nodes_by_key = {}
226
179
 
227
180
    def add_nodes(self, nodes):
228
181
        """Add nodes to the index.
238
191
 
239
192
    def _iter_mem_nodes(self):
240
193
        """Iterate over the nodes held in memory."""
241
 
        nodes = self._nodes
242
194
        if self.reference_lists:
243
 
            for key in sorted(nodes):
244
 
                references, value = nodes[key]
245
 
                yield self, key, value, references
 
195
            for key, (absent, references, value) in self._nodes.iteritems():
 
196
                if not absent:
 
197
                    yield self, key, value, references
246
198
        else:
247
 
            for key in sorted(nodes):
248
 
                references, value = nodes[key]
249
 
                yield self, key, value
 
199
            for key, (absent, references, value) in self._nodes.iteritems():
 
200
                if not absent:
 
201
                    yield self, key, value
250
202
 
251
203
    def _iter_smallest(self, iterators_to_combine):
252
204
        if len(iterators_to_combine) == 1:
280
232
            except StopIteration:
281
233
                current_values[pos] = None
282
234
 
283
 
    def _add_key(self, string_key, line, rows, allow_optimize=True):
 
235
    def _add_key(self, string_key, line, rows):
284
236
        """Add a key to the current chunk.
285
237
 
286
238
        :param string_key: The key to add.
287
239
        :param line: The fully serialised key and value.
288
 
        :param allow_optimize: If set to False, prevent setting the optimize
289
 
            flag when writing out. This is used by the _spill_mem_keys_to_disk
290
 
            functionality.
291
240
        """
292
241
        if rows[-1].writer is None:
293
242
            # opening a new leaf chunk;
298
247
                    length = _PAGE_SIZE
299
248
                    if internal_row.nodes == 0:
300
249
                        length -= _RESERVED_HEADER_BYTES # padded
301
 
                    if allow_optimize:
302
 
                        optimize_for_size = self._optimize_for_size
303
 
                    else:
304
 
                        optimize_for_size = False
305
 
                    internal_row.writer = chunk_writer.ChunkWriter(length, 0,
306
 
                        optimize_for_size=optimize_for_size)
 
250
                    internal_row.writer = chunk_writer.ChunkWriter(length, 0)
307
251
                    internal_row.writer.write(_INTERNAL_FLAG)
308
252
                    internal_row.writer.write(_INTERNAL_OFFSET +
309
253
                        str(rows[pos + 1].nodes) + "\n")
311
255
            length = _PAGE_SIZE
312
256
            if rows[-1].nodes == 0:
313
257
                length -= _RESERVED_HEADER_BYTES # padded
314
 
            rows[-1].writer = chunk_writer.ChunkWriter(length,
315
 
                optimize_for_size=self._optimize_for_size)
 
258
            rows[-1].writer = chunk_writer.ChunkWriter(length)
316
259
            rows[-1].writer.write(_LEAF_FLAG)
317
260
        if rows[-1].writer.write(line):
318
261
            # this key did not fit in the node:
321
264
            new_row = True
322
265
            for row in reversed(rows[:-1]):
323
266
                # Mark the start of the next node in the node above. If it
324
 
                # doesn't fit then propagate upwards until we find one that
 
267
                # doesn't fit then propogate upwards until we find one that
325
268
                # it does fit into.
326
269
                if row.writer.write(key_line):
327
270
                    row.finish_node()
341
284
                # This will be padded, hence the -100
342
285
                new_row.writer = chunk_writer.ChunkWriter(
343
286
                    _PAGE_SIZE - _RESERVED_HEADER_BYTES,
344
 
                    reserved_bytes,
345
 
                    optimize_for_size=self._optimize_for_size)
 
287
                    reserved_bytes)
346
288
                new_row.writer.write(_INTERNAL_FLAG)
347
289
                new_row.writer.write(_INTERNAL_OFFSET +
348
290
                    str(rows[1].nodes - 1) + "\n")
349
291
                new_row.writer.write(key_line)
350
 
            self._add_key(string_key, line, rows, allow_optimize=allow_optimize)
 
292
            self._add_key(string_key, line, rows)
351
293
 
352
 
    def _write_nodes(self, node_iterator, allow_optimize=True):
 
294
    def _write_nodes(self, node_iterator):
353
295
        """Write node_iterator out as a B+Tree.
354
296
 
355
297
        :param node_iterator: An iterator of sorted nodes. Each node should
356
298
            match the output given by iter_all_entries.
357
 
        :param allow_optimize: If set to False, prevent setting the optimize
358
 
            flag when writing out. This is used by the _spill_mem_keys_to_disk
359
 
            functionality.
360
299
        :return: A file handle for a temporary file containing a B+Tree for
361
300
            the nodes.
362
301
        """
372
311
        self.row_lengths = []
373
312
        # Loop over all nodes adding them to the bottom row
374
313
        # (rows[-1]). When we finish a chunk in a row,
375
 
        # propagate the key that didn't fit (comes after the chunk) to the
 
314
        # propogate the key that didn't fit (comes after the chunk) to the
376
315
        # row above, transitively.
377
316
        for node in node_iterator:
378
317
            if key_count == 0:
379
318
                # First key triggers the first row
380
319
                rows.append(_LeafBuilderRow())
381
320
            key_count += 1
 
321
            # TODO: Flattening the node into a string key and a line should
 
322
            #       probably be put into a pyrex function. We can do a quick
 
323
            #       iter over all the entries to determine the final length,
 
324
            #       and then do a single malloc() rather than lots of
 
325
            #       intermediate mallocs as we build everything up.
 
326
            #       ATM 3 / 13s are spent flattening nodes (10s is compressing)
382
327
            string_key, line = _btree_serializer._flatten_node(node,
383
328
                                    self.reference_lists)
384
 
            self._add_key(string_key, line, rows, allow_optimize=allow_optimize)
 
329
            self._add_key(string_key, line, rows)
385
330
        for row in reversed(rows):
386
331
            pad = (type(row) != _LeafBuilderRow)
387
332
            row.finish_node(pad=pad)
 
333
        result = tempfile.NamedTemporaryFile()
388
334
        lines = [_BTSIGNATURE]
389
335
        lines.append(_OPTION_NODE_REFS + str(self.reference_lists) + '\n')
390
336
        lines.append(_OPTION_KEY_ELEMENTS + str(self._key_length) + '\n')
391
337
        lines.append(_OPTION_LEN + str(key_count) + '\n')
392
338
        row_lengths = [row.nodes for row in rows]
393
339
        lines.append(_OPTION_ROW_LENGTHS + ','.join(map(str, row_lengths)) + '\n')
394
 
        if row_lengths and row_lengths[-1] > 1:
395
 
            result = tempfile.NamedTemporaryFile(prefix='bzr-index-')
396
 
        else:
397
 
            result = cStringIO.StringIO()
398
340
        result.writelines(lines)
399
341
        position = sum(map(len, lines))
400
342
        root_row = True
411
353
            # Special case the first node as it may be prefixed
412
354
            node = row.spool.read(_PAGE_SIZE)
413
355
            result.write(node[reserved:])
414
 
            if len(node) == _PAGE_SIZE:
415
 
                result.write("\x00" * (reserved - position))
 
356
            result.write("\x00" * (reserved - position))
416
357
            position = 0 # Only the root row actually has an offset
417
358
            copied_len = osutils.pumpfile(row.spool, result)
418
359
            if copied_len != (row.nodes - 1) * _PAGE_SIZE:
419
360
                if type(row) != _LeafBuilderRow:
420
 
                    raise AssertionError("Incorrect amount of data copied"
421
 
                        " expected: %d, got: %d"
422
 
                        % ((row.nodes - 1) * _PAGE_SIZE,
423
 
                           copied_len))
 
361
                    raise AssertionError("Not enough data copied")
424
362
        result.flush()
425
363
        size = result.tell()
426
364
        result.seek(0)
437
375
    def iter_all_entries(self):
438
376
        """Iterate over all keys within the index
439
377
 
440
 
        :return: An iterable of (index, key, value, reference_lists). There is
441
 
            no defined order for the result iteration - it will be in the most
 
378
        :return: An iterable of (index, key, reference_lists, value). There is no
 
379
            defined order for the result iteration - it will be in the most
442
380
            efficient order for the index (in this case dictionary hash order).
443
381
        """
444
382
        if 'evil' in debug.debug_flags:
446
384
                "iter_all_entries scales with size of history.")
447
385
        # Doing serial rather than ordered would be faster; but this shouldn't
448
386
        # be getting called routinely anyway.
449
 
        iterators = [self._iter_mem_nodes()]
 
387
        iterators = [iter(sorted(self._iter_mem_nodes()))]
450
388
        for backing in self._backing_indices:
451
389
            if backing is not None:
452
390
                iterators.append(backing.iter_all_entries())
463
401
            efficient order for the index (keys iteration order in this case).
464
402
        """
465
403
        keys = set(keys)
466
 
        # Note: We don't use keys.intersection() here. If you read the C api,
467
 
        #       set.intersection(other) special cases when other is a set and
468
 
        #       will iterate the smaller of the two and lookup in the other.
469
 
        #       It does *not* do this for any other type (even dict, unlike
470
 
        #       some other set functions.) Since we expect keys is generally <<
471
 
        #       self._nodes, it is faster to iterate over it in a list
472
 
        #       comprehension
473
 
        nodes = self._nodes
474
 
        local_keys = [key for key in keys if key in nodes]
475
404
        if self.reference_lists:
476
 
            for key in local_keys:
477
 
                node = nodes[key]
478
 
                yield self, key, node[1], node[0]
 
405
            for key in keys.intersection(self._keys):
 
406
                node = self._nodes[key]
 
407
                if not node[0]:
 
408
                    yield self, key, node[2], node[1]
479
409
        else:
480
 
            for key in local_keys:
481
 
                node = nodes[key]
482
 
                yield self, key, node[1]
483
 
        # Find things that are in backing indices that have not been handled
484
 
        # yet.
485
 
        if not self._backing_indices:
486
 
            return # We won't find anything there either
487
 
        # Remove all of the keys that we found locally
488
 
        keys.difference_update(local_keys)
 
410
            for key in keys.intersection(self._keys):
 
411
                node = self._nodes[key]
 
412
                if not node[0]:
 
413
                    yield self, key, node[2]
 
414
        keys.difference_update(self._keys)
489
415
        for backing in self._backing_indices:
490
416
            if backing is None:
491
417
                continue
533
459
                    node = self._nodes[key]
534
460
                except KeyError:
535
461
                    continue
 
462
                if node[0]:
 
463
                    continue
536
464
                if self.reference_lists:
537
 
                    yield self, key, node[1], node[0]
 
465
                    yield self, key, node[2], node[1]
538
466
                else:
539
 
                    yield self, key, node[1]
 
467
                    yield self, key, node[2]
540
468
            return
541
469
        for key in keys:
542
470
            # sanity check
545
473
            if len(key) != self._key_length:
546
474
                raise errors.BadIndexKey(key)
547
475
            # find what it refers to:
548
 
            key_dict = self._get_nodes_by_key()
 
476
            key_dict = self._nodes_by_key
549
477
            elements = list(key)
550
478
            # find the subdict to return
551
479
            try:
567
495
                    else:
568
496
                        # yield keys
569
497
                        for value in key_dict.itervalues():
570
 
                            yield (self, ) + tuple(value)
 
498
                            yield (self, ) + value
571
499
            else:
572
500
                yield (self, ) + key_dict
573
501
 
574
 
    def _get_nodes_by_key(self):
575
 
        if self._nodes_by_key is None:
576
 
            nodes_by_key = {}
577
 
            if self.reference_lists:
578
 
                for key, (references, value) in self._nodes.iteritems():
579
 
                    key_dict = nodes_by_key
580
 
                    for subkey in key[:-1]:
581
 
                        key_dict = key_dict.setdefault(subkey, {})
582
 
                    key_dict[key[-1]] = key, value, references
583
 
            else:
584
 
                for key, (references, value) in self._nodes.iteritems():
585
 
                    key_dict = nodes_by_key
586
 
                    for subkey in key[:-1]:
587
 
                        key_dict = key_dict.setdefault(subkey, {})
588
 
                    key_dict[key[-1]] = key, value
589
 
            self._nodes_by_key = nodes_by_key
590
 
        return self._nodes_by_key
591
 
 
592
502
    def key_count(self):
593
503
        """Return an estimate of the number of keys in this index.
594
504
 
595
505
        For InMemoryGraphIndex the estimate is exact.
596
506
        """
597
 
        return len(self._nodes) + sum(backing.key_count() for backing in
 
507
        return len(self._keys) + sum(backing.key_count() for backing in
598
508
            self._backing_indices if backing is not None)
599
509
 
600
510
    def validate(self):
604
514
class _LeafNode(object):
605
515
    """A leaf node for a serialised B+Tree index."""
606
516
 
607
 
    __slots__ = ('keys', 'min_key', 'max_key')
608
 
 
609
517
    def __init__(self, bytes, key_length, ref_list_length):
610
518
        """Parse bytes to create a leaf node object."""
611
519
        # splitlines mangles the \r delimiters.. don't use it.
612
 
        key_list = _btree_serializer._parse_leaf_lines(bytes,
613
 
            key_length, ref_list_length)
614
 
        if key_list:
615
 
            self.min_key = key_list[0][0]
616
 
            self.max_key = key_list[-1][0]
617
 
        else:
618
 
            self.min_key = self.max_key = None
619
 
        self.keys = dict(key_list)
 
520
        self.keys = dict(_btree_serializer._parse_leaf_lines(bytes,
 
521
            key_length, ref_list_length))
620
522
 
621
523
 
622
524
class _InternalNode(object):
623
525
    """An internal node for a serialised B+Tree index."""
624
526
 
625
 
    __slots__ = ('keys', 'offset')
626
 
 
627
527
    def __init__(self, bytes):
628
528
        """Parse bytes to create an internal node object."""
629
529
        # splitlines mangles the \r delimiters.. don't use it.
632
532
    def _parse_lines(self, lines):
633
533
        nodes = []
634
534
        self.offset = int(lines[1][7:])
635
 
        as_st = static_tuple.StaticTuple.from_sequence
636
535
        for line in lines[2:]:
637
536
            if line == '':
638
537
                break
639
 
            nodes.append(as_st(map(intern, line.split('\0'))).intern())
 
538
            nodes.append(tuple(line.split('\0')))
640
539
        return nodes
641
540
 
642
541
 
647
546
    memory except when very large walks are done.
648
547
    """
649
548
 
650
 
    def __init__(self, transport, name, size, unlimited_cache=False,
651
 
                 offset=0):
 
549
    def __init__(self, transport, name, size):
652
550
        """Create a B+Tree index object on the index name.
653
551
 
654
552
        :param transport: The transport to read data for the index from.
658
556
            the initial read (to read the root node header) can be done
659
557
            without over-reading even on empty indices, and on small indices
660
558
            allows single-IO to read the entire index.
661
 
        :param unlimited_cache: If set to True, then instead of using an
662
 
            LRUCache with size _NODE_CACHE_SIZE, we will use a dict and always
663
 
            cache all leaf nodes.
664
 
        :param offset: The start of the btree index data isn't byte 0 of the
665
 
            file. Instead it starts at some point later.
666
559
        """
667
560
        self._transport = transport
668
561
        self._name = name
669
562
        self._size = size
670
563
        self._file = None
671
 
        self._recommended_pages = self._compute_recommended_pages()
 
564
        self._page_size = transport.recommended_page_size()
672
565
        self._root_node = None
673
 
        self._base_offset = offset
674
566
        # Default max size is 100,000 leave values
675
567
        self._leaf_value_cache = None # lru_cache.LRUCache(100*1000)
676
 
        if unlimited_cache:
677
 
            self._leaf_node_cache = {}
678
 
            self._internal_node_cache = {}
679
 
        else:
680
 
            self._leaf_node_cache = lru_cache.LRUCache(_NODE_CACHE_SIZE)
681
 
            # We use a FIFO here just to prevent possible blowout. However, a
682
 
            # 300k record btree has only 3k leaf nodes, and only 20 internal
683
 
            # nodes. A value of 100 scales to ~100*100*100 = 1M records.
684
 
            self._internal_node_cache = fifo_cache.FIFOCache(100)
 
568
        self._leaf_node_cache = lru_cache.LRUCache(_NODE_CACHE_SIZE)
 
569
        self._internal_node_cache = lru_cache.LRUCache()
685
570
        self._key_count = None
686
571
        self._row_lengths = None
687
572
        self._row_offsets = None # Start of each row, [-1] is the end
697
582
    def __ne__(self, other):
698
583
        return not self.__eq__(other)
699
584
 
700
 
    def _get_and_cache_nodes(self, nodes):
 
585
    def _get_root_node(self):
 
586
        if self._root_node is None:
 
587
            # We may not have a root node yet
 
588
            nodes = list(self._read_nodes([0]))
 
589
            if len(nodes):
 
590
                self._root_node = nodes[0][1]
 
591
        return self._root_node
 
592
 
 
593
    def _cache_nodes(self, nodes, cache):
701
594
        """Read nodes and cache them in the lru.
702
595
 
703
596
        The nodes list supplied is sorted and then read from disk, each node
710
603
 
711
604
        :return: A dict of {node_pos: node}
712
605
        """
 
606
        if len(nodes) > cache._max_cache:
 
607
            trace.mutter('Requesting %s > %s nodes, not all will be cached',
 
608
                         len(nodes), cache._max_cache)
713
609
        found = {}
714
 
        start_of_leaves = None
715
610
        for node_pos, node in self._read_nodes(sorted(nodes)):
716
611
            if node_pos == 0: # Special case
717
612
                self._root_node = node
718
613
            else:
719
 
                if start_of_leaves is None:
720
 
                    start_of_leaves = self._row_offsets[-2]
721
 
                if node_pos < start_of_leaves:
722
 
                    self._internal_node_cache[node_pos] = node
723
 
                else:
724
 
                    self._leaf_node_cache[node_pos] = node
 
614
                cache.add(node_pos, node)
725
615
            found[node_pos] = node
726
616
        return found
727
617
 
728
 
    def _compute_recommended_pages(self):
729
 
        """Convert transport's recommended_page_size into btree pages.
730
 
 
731
 
        recommended_page_size is in bytes, we want to know how many _PAGE_SIZE
732
 
        pages fit in that length.
733
 
        """
734
 
        recommended_read = self._transport.recommended_page_size()
735
 
        recommended_pages = int(math.ceil(recommended_read /
736
 
                                          float(_PAGE_SIZE)))
737
 
        return recommended_pages
738
 
 
739
 
    def _compute_total_pages_in_index(self):
740
 
        """How many pages are in the index.
741
 
 
742
 
        If we have read the header we will use the value stored there.
743
 
        Otherwise it will be computed based on the length of the index.
744
 
        """
745
 
        if self._size is None:
746
 
            raise AssertionError('_compute_total_pages_in_index should not be'
747
 
                                 ' called when self._size is None')
748
 
        if self._root_node is not None:
749
 
            # This is the number of pages as defined by the header
750
 
            return self._row_offsets[-1]
751
 
        # This is the number of pages as defined by the size of the index. They
752
 
        # should be indentical.
753
 
        total_pages = int(math.ceil(self._size / float(_PAGE_SIZE)))
754
 
        return total_pages
755
 
 
756
 
    def _expand_offsets(self, offsets):
757
 
        """Find extra pages to download.
758
 
 
759
 
        The idea is that we always want to make big-enough requests (like 64kB
760
 
        for http), so that we don't waste round trips. So given the entries
761
 
        that we already have cached and the new pages being downloaded figure
762
 
        out what other pages we might want to read.
763
 
 
764
 
        See also doc/developers/btree_index_prefetch.txt for more details.
765
 
 
766
 
        :param offsets: The offsets to be read
767
 
        :return: A list of offsets to download
768
 
        """
769
 
        if 'index' in debug.debug_flags:
770
 
            trace.mutter('expanding: %s\toffsets: %s', self._name, offsets)
771
 
 
772
 
        if len(offsets) >= self._recommended_pages:
773
 
            # Don't add more, we are already requesting more than enough
774
 
            if 'index' in debug.debug_flags:
775
 
                trace.mutter('  not expanding large request (%s >= %s)',
776
 
                             len(offsets), self._recommended_pages)
777
 
            return offsets
778
 
        if self._size is None:
779
 
            # Don't try anything, because we don't know where the file ends
780
 
            if 'index' in debug.debug_flags:
781
 
                trace.mutter('  not expanding without knowing index size')
782
 
            return offsets
783
 
        total_pages = self._compute_total_pages_in_index()
784
 
        cached_offsets = self._get_offsets_to_cached_pages()
785
 
        # If reading recommended_pages would read the rest of the index, just
786
 
        # do so.
787
 
        if total_pages - len(cached_offsets) <= self._recommended_pages:
788
 
            # Read whatever is left
789
 
            if cached_offsets:
790
 
                expanded = [x for x in xrange(total_pages)
791
 
                               if x not in cached_offsets]
792
 
            else:
793
 
                expanded = range(total_pages)
794
 
            if 'index' in debug.debug_flags:
795
 
                trace.mutter('  reading all unread pages: %s', expanded)
796
 
            return expanded
797
 
 
798
 
        if self._root_node is None:
799
 
            # ATM on the first read of the root node of a large index, we don't
800
 
            # bother pre-reading any other pages. This is because the
801
 
            # likelyhood of actually reading interesting pages is very low.
802
 
            # See doc/developers/btree_index_prefetch.txt for a discussion, and
803
 
            # a possible implementation when we are guessing that the second
804
 
            # layer index is small
805
 
            final_offsets = offsets
806
 
        else:
807
 
            tree_depth = len(self._row_lengths)
808
 
            if len(cached_offsets) < tree_depth and len(offsets) == 1:
809
 
                # We haven't read enough to justify expansion
810
 
                # If we are only going to read the root node, and 1 leaf node,
811
 
                # then it isn't worth expanding our request. Once we've read at
812
 
                # least 2 nodes, then we are probably doing a search, and we
813
 
                # start expanding our requests.
814
 
                if 'index' in debug.debug_flags:
815
 
                    trace.mutter('  not expanding on first reads')
816
 
                return offsets
817
 
            final_offsets = self._expand_to_neighbors(offsets, cached_offsets,
818
 
                                                      total_pages)
819
 
 
820
 
        final_offsets = sorted(final_offsets)
821
 
        if 'index' in debug.debug_flags:
822
 
            trace.mutter('expanded:  %s', final_offsets)
823
 
        return final_offsets
824
 
 
825
 
    def _expand_to_neighbors(self, offsets, cached_offsets, total_pages):
826
 
        """Expand requests to neighbors until we have enough pages.
827
 
 
828
 
        This is called from _expand_offsets after policy has determined that we
829
 
        want to expand.
830
 
        We only want to expand requests within a given layer. We cheat a little
831
 
        bit and assume all requests will be in the same layer. This is true
832
 
        given the current design, but if it changes this algorithm may perform
833
 
        oddly.
834
 
 
835
 
        :param offsets: requested offsets
836
 
        :param cached_offsets: offsets for pages we currently have cached
837
 
        :return: A set() of offsets after expansion
838
 
        """
839
 
        final_offsets = set(offsets)
840
 
        first = end = None
841
 
        new_tips = set(final_offsets)
842
 
        while len(final_offsets) < self._recommended_pages and new_tips:
843
 
            next_tips = set()
844
 
            for pos in new_tips:
845
 
                if first is None:
846
 
                    first, end = self._find_layer_first_and_end(pos)
847
 
                previous = pos - 1
848
 
                if (previous > 0
849
 
                    and previous not in cached_offsets
850
 
                    and previous not in final_offsets
851
 
                    and previous >= first):
852
 
                    next_tips.add(previous)
853
 
                after = pos + 1
854
 
                if (after < total_pages
855
 
                    and after not in cached_offsets
856
 
                    and after not in final_offsets
857
 
                    and after < end):
858
 
                    next_tips.add(after)
859
 
                # This would keep us from going bigger than
860
 
                # recommended_pages by only expanding the first offsets.
861
 
                # However, if we are making a 'wide' request, it is
862
 
                # reasonable to expand all points equally.
863
 
                # if len(final_offsets) > recommended_pages:
864
 
                #     break
865
 
            final_offsets.update(next_tips)
866
 
            new_tips = next_tips
867
 
        return final_offsets
868
 
 
869
 
    def clear_cache(self):
870
 
        """Clear out any cached/memoized values.
871
 
 
872
 
        This can be called at any time, but generally it is used when we have
873
 
        extracted some information, but don't expect to be requesting any more
874
 
        from this index.
875
 
        """
876
 
        # Note that we don't touch self._root_node or self._internal_node_cache
877
 
        # We don't expect either of those to be big, and it can save
878
 
        # round-trips in the future. We may re-evaluate this if InternalNode
879
 
        # memory starts to be an issue.
880
 
        self._leaf_node_cache.clear()
881
 
 
882
 
    def external_references(self, ref_list_num):
883
 
        if self._root_node is None:
884
 
            self._get_root_node()
885
 
        if ref_list_num + 1 > self.node_ref_lists:
886
 
            raise ValueError('No ref list %d, index has %d ref lists'
887
 
                % (ref_list_num, self.node_ref_lists))
888
 
        keys = set()
889
 
        refs = set()
890
 
        for node in self.iter_all_entries():
891
 
            keys.add(node[1])
892
 
            refs.update(node[3][ref_list_num])
893
 
        return refs - keys
894
 
 
895
 
    def _find_layer_first_and_end(self, offset):
896
 
        """Find the start/stop nodes for the layer corresponding to offset.
897
 
 
898
 
        :return: (first, end)
899
 
            first is the first node in this layer
900
 
            end is the first node of the next layer
901
 
        """
902
 
        first = end = 0
903
 
        for roffset in self._row_offsets:
904
 
            first = end
905
 
            end = roffset
906
 
            if offset < roffset:
907
 
                break
908
 
        return first, end
909
 
 
910
 
    def _get_offsets_to_cached_pages(self):
911
 
        """Determine what nodes we already have cached."""
912
 
        cached_offsets = set(self._internal_node_cache.keys())
913
 
        cached_offsets.update(self._leaf_node_cache.keys())
914
 
        if self._root_node is not None:
915
 
            cached_offsets.add(0)
916
 
        return cached_offsets
917
 
 
918
 
    def _get_root_node(self):
919
 
        if self._root_node is None:
920
 
            # We may not have a root node yet
921
 
            self._get_internal_nodes([0])
922
 
        return self._root_node
923
 
 
924
618
    def _get_nodes(self, cache, node_indexes):
925
619
        found = {}
926
620
        needed = []
932
626
                found[idx] = cache[idx]
933
627
            except KeyError:
934
628
                needed.append(idx)
935
 
        if not needed:
936
 
            return found
937
 
        needed = self._expand_offsets(needed)
938
 
        found.update(self._get_and_cache_nodes(needed))
 
629
        found.update(self._cache_nodes(needed, cache))
939
630
        return found
940
631
 
941
632
    def _get_internal_nodes(self, node_indexes):
945
636
        """
946
637
        return self._get_nodes(self._internal_node_cache, node_indexes)
947
638
 
948
 
    def _cache_leaf_values(self, nodes):
949
 
        """Cache directly from key => value, skipping the btree."""
 
639
    def _get_leaf_nodes(self, node_indexes):
 
640
        """Get a bunch of nodes, from cache or disk."""
 
641
        found = self._get_nodes(self._leaf_node_cache, node_indexes)
950
642
        if self._leaf_value_cache is not None:
951
 
            for node in nodes.itervalues():
 
643
            for node in found.itervalues():
952
644
                for key, value in node.keys.iteritems():
953
645
                    if key in self._leaf_value_cache:
954
646
                        # Don't add the rest of the keys, we've seen this node
955
647
                        # before.
956
648
                        break
957
649
                    self._leaf_value_cache[key] = value
958
 
 
959
 
    def _get_leaf_nodes(self, node_indexes):
960
 
        """Get a bunch of nodes, from cache or disk."""
961
 
        found = self._get_nodes(self._leaf_node_cache, node_indexes)
962
 
        self._cache_leaf_values(found)
963
650
        return found
964
651
 
965
652
    def iter_all_entries(self):
976
663
                "iter_all_entries scales with size of history.")
977
664
        if not self.key_count():
978
665
            return
979
 
        if self._row_offsets[-1] == 1:
980
 
            # There is only the root node, and we read that via key_count()
981
 
            if self.node_ref_lists:
982
 
                for key, (value, refs) in sorted(self._root_node.keys.items()):
983
 
                    yield (self, key, value, refs)
984
 
            else:
985
 
                for key, (value, refs) in sorted(self._root_node.keys.items()):
986
 
                    yield (self, key, value)
987
 
            return
988
666
        start_of_leaves = self._row_offsets[-2]
989
667
        end_of_leaves = self._row_offsets[-1]
990
 
        needed_offsets = range(start_of_leaves, end_of_leaves)
991
 
        if needed_offsets == [0]:
992
 
            # Special case when we only have a root node, as we have already
993
 
            # read everything
994
 
            nodes = [(0, self._root_node)]
995
 
        else:
996
 
            nodes = self._read_nodes(needed_offsets)
 
668
        needed_nodes = range(start_of_leaves, end_of_leaves)
997
669
        # We iterate strictly in-order so that we can use this function
998
670
        # for spilling index builds to disk.
999
671
        if self.node_ref_lists:
1000
 
            for _, node in nodes:
 
672
            for _, node in self._read_nodes(needed_nodes):
1001
673
                for key, (value, refs) in sorted(node.keys.items()):
1002
674
                    yield (self, key, value, refs)
1003
675
        else:
1004
 
            for _, node in nodes:
 
676
            for _, node in self._read_nodes(needed_nodes):
1005
677
                for key, (value, refs) in sorted(node.keys.items()):
1006
678
                    yield (self, key, value)
1007
679
 
1087
759
            output.append(cur_out)
1088
760
        return output
1089
761
 
1090
 
    def _walk_through_internal_nodes(self, keys):
1091
 
        """Take the given set of keys, and find the corresponding LeafNodes.
1092
 
 
1093
 
        :param keys: An unsorted iterable of keys to search for
1094
 
        :return: (nodes, index_and_keys)
1095
 
            nodes is a dict mapping {index: LeafNode}
1096
 
            keys_at_index is a list of tuples of [(index, [keys for Leaf])]
1097
 
        """
1098
 
        # 6 seconds spent in miss_torture using the sorted() line.
1099
 
        # Even with out of order disk IO it seems faster not to sort it when
1100
 
        # large queries are being made.
1101
 
        keys_at_index = [(0, sorted(keys))]
1102
 
 
1103
 
        for row_pos, next_row_start in enumerate(self._row_offsets[1:-1]):
1104
 
            node_indexes = [idx for idx, s_keys in keys_at_index]
1105
 
            nodes = self._get_internal_nodes(node_indexes)
1106
 
 
1107
 
            next_nodes_and_keys = []
1108
 
            for node_index, sub_keys in keys_at_index:
1109
 
                node = nodes[node_index]
1110
 
                positions = self._multi_bisect_right(sub_keys, node.keys)
1111
 
                node_offset = next_row_start + node.offset
1112
 
                next_nodes_and_keys.extend([(node_offset + pos, s_keys)
1113
 
                                           for pos, s_keys in positions])
1114
 
            keys_at_index = next_nodes_and_keys
1115
 
        # We should now be at the _LeafNodes
1116
 
        node_indexes = [idx for idx, s_keys in keys_at_index]
1117
 
 
1118
 
        # TODO: We may *not* want to always read all the nodes in one
1119
 
        #       big go. Consider setting a max size on this.
1120
 
        nodes = self._get_leaf_nodes(node_indexes)
1121
 
        return nodes, keys_at_index
1122
 
 
1123
762
    def iter_entries(self, keys):
1124
763
        """Iterate over keys within the index.
1125
764
 
1163
802
        needed_keys = keys
1164
803
        if not needed_keys:
1165
804
            return
1166
 
        nodes, nodes_and_keys = self._walk_through_internal_nodes(needed_keys)
 
805
        # 6 seconds spent in miss_torture using the sorted() line.
 
806
        # Even with out of order disk IO it seems faster not to sort it when
 
807
        # large queries are being made.
 
808
        needed_keys = sorted(needed_keys)
 
809
 
 
810
        nodes_and_keys = [(0, needed_keys)]
 
811
 
 
812
        for row_pos, next_row_start in enumerate(self._row_offsets[1:-1]):
 
813
            node_indexes = [idx for idx, s_keys in nodes_and_keys]
 
814
            nodes = self._get_internal_nodes(node_indexes)
 
815
 
 
816
            next_nodes_and_keys = []
 
817
            for node_index, sub_keys in nodes_and_keys:
 
818
                node = nodes[node_index]
 
819
                positions = self._multi_bisect_right(sub_keys, node.keys)
 
820
                node_offset = next_row_start + node.offset
 
821
                next_nodes_and_keys.extend([(node_offset + pos, s_keys)
 
822
                                           for pos, s_keys in positions])
 
823
            nodes_and_keys = next_nodes_and_keys
 
824
        # We should now be at the _LeafNodes
 
825
        node_indexes = [idx for idx, s_keys in nodes_and_keys]
 
826
 
 
827
        # TODO: We may *not* want to always read all the nodes in one
 
828
        #       big go. Consider setting a max size on this.
 
829
 
 
830
        nodes = self._get_leaf_nodes(node_indexes)
1167
831
        for node_index, sub_keys in nodes_and_keys:
1168
832
            if not sub_keys:
1169
833
                continue
1176
840
                    else:
1177
841
                        yield (self, next_sub_key, value)
1178
842
 
1179
 
    def _find_ancestors(self, keys, ref_list_num, parent_map, missing_keys):
1180
 
        """Find the parent_map information for the set of keys.
1181
 
 
1182
 
        This populates the parent_map dict and missing_keys set based on the
1183
 
        queried keys. It also can fill out an arbitrary number of parents that
1184
 
        it finds while searching for the supplied keys.
1185
 
 
1186
 
        It is unlikely that you want to call this directly. See
1187
 
        "CombinedGraphIndex.find_ancestry()" for a more appropriate API.
1188
 
 
1189
 
        :param keys: A keys whose ancestry we want to return
1190
 
            Every key will either end up in 'parent_map' or 'missing_keys'.
1191
 
        :param ref_list_num: This index in the ref_lists is the parents we
1192
 
            care about.
1193
 
        :param parent_map: {key: parent_keys} for keys that are present in this
1194
 
            index. This may contain more entries than were in 'keys', that are
1195
 
            reachable ancestors of the keys requested.
1196
 
        :param missing_keys: keys which are known to be missing in this index.
1197
 
            This may include parents that were not directly requested, but we
1198
 
            were able to determine that they are not present in this index.
1199
 
        :return: search_keys    parents that were found but not queried to know
1200
 
            if they are missing or present. Callers can re-query this index for
1201
 
            those keys, and they will be placed into parent_map or missing_keys
1202
 
        """
1203
 
        if not self.key_count():
1204
 
            # We use key_count() to trigger reading the root node and
1205
 
            # determining info about this BTreeGraphIndex
1206
 
            # If we don't have any keys, then everything is missing
1207
 
            missing_keys.update(keys)
1208
 
            return set()
1209
 
        if ref_list_num >= self.node_ref_lists:
1210
 
            raise ValueError('No ref list %d, index has %d ref lists'
1211
 
                % (ref_list_num, self.node_ref_lists))
1212
 
 
1213
 
        # The main trick we are trying to accomplish is that when we find a
1214
 
        # key listing its parents, we expect that the parent key is also likely
1215
 
        # to sit on the same page. Allowing us to expand parents quickly
1216
 
        # without suffering the full stack of bisecting, etc.
1217
 
        nodes, nodes_and_keys = self._walk_through_internal_nodes(keys)
1218
 
 
1219
 
        # These are parent keys which could not be immediately resolved on the
1220
 
        # page where the child was present. Note that we may already be
1221
 
        # searching for that key, and it may actually be present [or known
1222
 
        # missing] on one of the other pages we are reading.
1223
 
        # TODO:
1224
 
        #   We could try searching for them in the immediate previous or next
1225
 
        #   page. If they occur "later" we could put them in a pending lookup
1226
 
        #   set, and then for each node we read thereafter we could check to
1227
 
        #   see if they are present.
1228
 
        #   However, we don't know the impact of keeping this list of things
1229
 
        #   that I'm going to search for every node I come across from here on
1230
 
        #   out.
1231
 
        #   It doesn't handle the case when the parent key is missing on a
1232
 
        #   page that we *don't* read. So we already have to handle being
1233
 
        #   re-entrant for that.
1234
 
        #   Since most keys contain a date string, they are more likely to be
1235
 
        #   found earlier in the file than later, but we would know that right
1236
 
        #   away (key < min_key), and wouldn't keep searching it on every other
1237
 
        #   page that we read.
1238
 
        #   Mostly, it is an idea, one which should be benchmarked.
1239
 
        parents_not_on_page = set()
1240
 
 
1241
 
        for node_index, sub_keys in nodes_and_keys:
1242
 
            if not sub_keys:
1243
 
                continue
1244
 
            # sub_keys is all of the keys we are looking for that should exist
1245
 
            # on this page, if they aren't here, then they won't be found
1246
 
            node = nodes[node_index]
1247
 
            node_keys = node.keys
1248
 
            parents_to_check = set()
1249
 
            for next_sub_key in sub_keys:
1250
 
                if next_sub_key not in node_keys:
1251
 
                    # This one is just not present in the index at all
1252
 
                    missing_keys.add(next_sub_key)
1253
 
                else:
1254
 
                    value, refs = node_keys[next_sub_key]
1255
 
                    parent_keys = refs[ref_list_num]
1256
 
                    parent_map[next_sub_key] = parent_keys
1257
 
                    parents_to_check.update(parent_keys)
1258
 
            # Don't look for things we've already found
1259
 
            parents_to_check = parents_to_check.difference(parent_map)
1260
 
            # this can be used to test the benefit of having the check loop
1261
 
            # inlined.
1262
 
            # parents_not_on_page.update(parents_to_check)
1263
 
            # continue
1264
 
            while parents_to_check:
1265
 
                next_parents_to_check = set()
1266
 
                for key in parents_to_check:
1267
 
                    if key in node_keys:
1268
 
                        value, refs = node_keys[key]
1269
 
                        parent_keys = refs[ref_list_num]
1270
 
                        parent_map[key] = parent_keys
1271
 
                        next_parents_to_check.update(parent_keys)
1272
 
                    else:
1273
 
                        # This parent either is genuinely missing, or should be
1274
 
                        # found on another page. Perf test whether it is better
1275
 
                        # to check if this node should fit on this page or not.
1276
 
                        # in the 'everything-in-one-pack' scenario, this *not*
1277
 
                        # doing the check is 237ms vs 243ms.
1278
 
                        # So slightly better, but I assume the standard 'lots
1279
 
                        # of packs' is going to show a reasonable improvement
1280
 
                        # from the check, because it avoids 'going around
1281
 
                        # again' for everything that is in another index
1282
 
                        # parents_not_on_page.add(key)
1283
 
                        # Missing for some reason
1284
 
                        if key < node.min_key:
1285
 
                            # in the case of bzr.dev, 3.4k/5.3k misses are
1286
 
                            # 'earlier' misses (65%)
1287
 
                            parents_not_on_page.add(key)
1288
 
                        elif key > node.max_key:
1289
 
                            # This parent key would be present on a different
1290
 
                            # LeafNode
1291
 
                            parents_not_on_page.add(key)
1292
 
                        else:
1293
 
                            # assert key != node.min_key and key != node.max_key
1294
 
                            # If it was going to be present, it would be on
1295
 
                            # *this* page, so mark it missing.
1296
 
                            missing_keys.add(key)
1297
 
                parents_to_check = next_parents_to_check.difference(parent_map)
1298
 
                # Might want to do another .difference() from missing_keys
1299
 
        # parents_not_on_page could have been found on a different page, or be
1300
 
        # known to be missing. So cull out everything that has already been
1301
 
        # found.
1302
 
        search_keys = parents_not_on_page.difference(
1303
 
            parent_map).difference(missing_keys)
1304
 
        return search_keys
1305
 
 
1306
843
    def iter_entries_prefix(self, keys):
1307
844
        """Iterate over keys within the index using prefix matching.
1308
845
 
1425
962
            self._get_root_node()
1426
963
        return self._key_count
1427
964
 
1428
 
    def _compute_row_offsets(self):
1429
 
        """Fill out the _row_offsets attribute based on _row_lengths."""
1430
 
        offsets = []
1431
 
        row_offset = 0
1432
 
        for row in self._row_lengths:
1433
 
            offsets.append(row_offset)
1434
 
            row_offset += row
1435
 
        offsets.append(row_offset)
1436
 
        self._row_offsets = offsets
1437
 
 
1438
965
    def _parse_header_from_bytes(self, bytes):
1439
966
        """Parse the header from a region of bytes.
1440
967
 
1476
1003
                if len(length)])
1477
1004
        except ValueError:
1478
1005
            raise errors.BadIndexOptions(self)
1479
 
        self._compute_row_offsets()
 
1006
        offsets = []
 
1007
        row_offset = 0
 
1008
        for row in self._row_lengths:
 
1009
            offsets.append(row_offset)
 
1010
            row_offset += row
 
1011
        offsets.append(row_offset)
 
1012
        self._row_offsets = offsets
1480
1013
 
1481
1014
        # calculate the bytes we have processed
1482
1015
        header_end = (len(signature) + sum(map(len, lines[0:4])) + 4)
1486
1019
        """Read some nodes from disk into the LRU cache.
1487
1020
 
1488
1021
        This performs a readv to get the node data into memory, and parses each
1489
 
        node, then yields it to the caller. The nodes are requested in the
 
1022
        node, the yields it to the caller. The nodes are requested in the
1490
1023
        supplied order. If possible doing sort() on the list before requesting
1491
1024
        a read may improve performance.
1492
1025
 
1493
1026
        :param nodes: The nodes to read. 0 - first node, 1 - second node etc.
1494
1027
        :return: None
1495
1028
        """
1496
 
        # may be the byte string of the whole file
1497
 
        bytes = None
1498
 
        # list of (offset, length) regions of the file that should, evenually
1499
 
        # be read in to data_ranges, either from 'bytes' or from the transport
1500
1029
        ranges = []
1501
 
        base_offset = self._base_offset
1502
1030
        for index in nodes:
1503
 
            offset = (index * _PAGE_SIZE)
 
1031
            offset = index * _PAGE_SIZE
1504
1032
            size = _PAGE_SIZE
1505
1033
            if index == 0:
1506
1034
                # Root node - special case
1507
1035
                if self._size:
1508
1036
                    size = min(_PAGE_SIZE, self._size)
1509
1037
                else:
1510
 
                    # The only case where we don't know the size, is for very
1511
 
                    # small indexes. So we read the whole thing
1512
 
                    bytes = self._transport.get_bytes(self._name)
1513
 
                    num_bytes = len(bytes)
1514
 
                    self._size = num_bytes - base_offset
1515
 
                    # the whole thing should be parsed out of 'bytes'
1516
 
                    ranges = [(start, min(_PAGE_SIZE, num_bytes - start))
1517
 
                        for start in xrange(base_offset, num_bytes, _PAGE_SIZE)]
1518
 
                    break
 
1038
                    stream = self._transport.get(self._name)
 
1039
                    start = stream.read(_PAGE_SIZE)
 
1040
                    # Avoid doing this again
 
1041
                    self._size = len(start)
 
1042
                    size = min(_PAGE_SIZE, self._size)
1519
1043
            else:
1520
 
                if offset > self._size:
1521
 
                    raise AssertionError('tried to read past the end'
1522
 
                                         ' of the file %s > %s'
1523
 
                                         % (offset, self._size))
1524
1044
                size = min(size, self._size - offset)
1525
 
            ranges.append((base_offset + offset, size))
 
1045
            ranges.append((offset, size))
1526
1046
        if not ranges:
1527
1047
            return
1528
 
        elif bytes is not None:
1529
 
            # already have the whole file
1530
 
            data_ranges = [(start, bytes[start:start+size])
1531
 
                           for start, size in ranges]
1532
 
        elif self._file is None:
 
1048
        if self._file is None:
1533
1049
            data_ranges = self._transport.readv(self._name, ranges)
1534
1050
        else:
1535
1051
            data_ranges = []
1537
1053
                self._file.seek(offset)
1538
1054
                data_ranges.append((offset, self._file.read(size)))
1539
1055
        for offset, data in data_ranges:
1540
 
            offset -= base_offset
1541
1056
            if offset == 0:
1542
1057
                # extract the header
1543
1058
                offset, data = self._parse_header_from_bytes(data)
1571
1086
 
1572
1087
 
1573
1088
try:
1574
 
    from bzrlib import _btree_serializer_pyx as _btree_serializer
1575
 
except ImportError, e:
1576
 
    osutils.failed_to_load_extension(e)
 
1089
    from bzrlib import _btree_serializer_c as _btree_serializer
 
1090
except ImportError:
1577
1091
    from bzrlib import _btree_serializer_py as _btree_serializer