1
# Copyright (C) 2008 Canonical Ltd
3
# This program is free software; you can redistribute it and/or modify
4
# it under the terms of the GNU General Public License as published by
5
# the Free Software Foundation; either version 2 of the License, or
6
# (at your option) any later version.
8
# This program is distributed in the hope that it will be useful,
9
# but WITHOUT ANY WARRANTY; without even the implied warranty of
10
# MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
11
# GNU General Public License for more details.
13
# You should have received a copy of the GNU General Public License
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
20
from bisect import bisect_right
35
from bzrlib.index import _OPTION_NODE_REFS, _OPTION_KEY_ELEMENTS, _OPTION_LEN
36
from bzrlib.transport import get_transport
39
_BTSIGNATURE = "B+Tree Graph Index 2\n"
40
_OPTION_ROW_LENGTHS = "row_lengths="
41
_LEAF_FLAG = "type=leaf\n"
42
_INTERNAL_FLAG = "type=internal\n"
43
_INTERNAL_OFFSET = "offset="
45
_RESERVED_HEADER_BYTES = 120
48
# 4K per page: 4MB - 1000 entries
49
_NODE_CACHE_SIZE = 1000
52
class _BuilderRow(object):
53
"""The stored state accumulated while writing out a row in the index.
55
:ivar spool: A temporary file used to accumulate nodes for this row
57
:ivar nodes: The count of nodes emitted so far.
61
"""Create a _BuilderRow."""
63
self.spool = tempfile.TemporaryFile()
66
def finish_node(self, pad=True):
67
byte_lines, _, padding = self.writer.finish()
70
self.spool.write("\x00" * _RESERVED_HEADER_BYTES)
72
if not pad and padding:
74
skipped_bytes = padding
75
self.spool.writelines(byte_lines)
76
remainder = (self.spool.tell() + skipped_bytes) % _PAGE_SIZE
78
raise AssertionError("incorrect node length: %d, %d"
79
% (self.spool.tell(), remainder))
84
class _InternalBuilderRow(_BuilderRow):
85
"""The stored state accumulated while writing out internal rows."""
87
def finish_node(self, pad=True):
89
raise AssertionError("Must pad internal nodes only.")
90
_BuilderRow.finish_node(self)
93
class _LeafBuilderRow(_BuilderRow):
94
"""The stored state accumulated while writing out a leaf rows."""
97
class BTreeBuilder(index.GraphIndexBuilder):
98
"""A Builder for B+Tree based Graph indices.
100
The resulting graph has the structure:
102
_SIGNATURE OPTIONS NODES
103
_SIGNATURE := 'B+Tree Graph Index 1' NEWLINE
104
OPTIONS := REF_LISTS KEY_ELEMENTS LENGTH
105
REF_LISTS := 'node_ref_lists=' DIGITS NEWLINE
106
KEY_ELEMENTS := 'key_elements=' DIGITS NEWLINE
107
LENGTH := 'len=' DIGITS NEWLINE
108
ROW_LENGTHS := 'row_lengths' DIGITS (COMMA DIGITS)*
109
NODES := NODE_COMPRESSED*
110
NODE_COMPRESSED:= COMPRESSED_BYTES{4096}
111
NODE_RAW := INTERNAL | LEAF
112
INTERNAL := INTERNAL_FLAG POINTERS
113
LEAF := LEAF_FLAG ROWS
114
KEY_ELEMENT := Not-whitespace-utf8
115
KEY := KEY_ELEMENT (NULL KEY_ELEMENT)*
117
ROW := KEY NULL ABSENT? NULL REFERENCES NULL VALUE NEWLINE
119
REFERENCES := REFERENCE_LIST (TAB REFERENCE_LIST){node_ref_lists - 1}
120
REFERENCE_LIST := (REFERENCE (CR REFERENCE)*)?
122
VALUE := no-newline-no-null-bytes
125
def __init__(self, reference_lists=0, key_elements=1, spill_at=100000):
126
"""See GraphIndexBuilder.__init__.
128
:param spill_at: Optional parameter controlling the maximum number
129
of nodes that BTreeBuilder will hold in memory.
131
index.GraphIndexBuilder.__init__(self, reference_lists=reference_lists,
132
key_elements=key_elements)
133
self._spill_at = spill_at
134
self._backing_indices = []
135
# A map of {key: (node_refs, value)}
137
# Indicate it hasn't been built yet
138
self._nodes_by_key = None
139
self._optimize_for_size = False
141
def add_node(self, key, value, references=()):
142
"""Add a node to the index.
144
If adding the node causes the builder to reach its spill_at threshold,
145
disk spilling will be triggered.
147
:param key: The key. keys are non-empty tuples containing
148
as many whitespace-free utf8 bytestrings as the key length
149
defined for this index.
150
:param references: An iterable of iterables of keys. Each is a
151
reference to another key.
152
:param value: The value to associate with the key. It may be any
153
bytes as long as it does not contain \0 or \n.
155
# we don't care about absent_references
156
node_refs, _ = self._check_key_ref_value(key, references, value)
157
if key in self._nodes:
158
raise errors.BadIndexDuplicateKey(key, self)
159
self._nodes[key] = (node_refs, value)
161
if self._nodes_by_key is not None and self._key_length > 1:
162
self._update_nodes_by_key(key, value, node_refs)
163
if len(self._keys) < self._spill_at:
165
self._spill_mem_keys_to_disk()
167
def _spill_mem_keys_to_disk(self):
168
"""Write the in memory keys down to disk to cap memory consumption.
170
If we already have some keys written to disk, we will combine them so
171
as to preserve the sorted order. The algorithm for combining uses
172
powers of two. So on the first spill, write all mem nodes into a
173
single index. On the second spill, combine the mem nodes with the nodes
174
on disk to create a 2x sized disk index and get rid of the first index.
175
On the third spill, create a single new disk index, which will contain
176
the mem nodes, and preserve the existing 2x sized index. On the fourth,
177
combine mem with the first and second indexes, creating a new one of
178
size 4x. On the fifth create a single new one, etc.
180
if self._combine_backing_indices:
181
(new_backing_file, size,
182
backing_pos) = self._spill_mem_keys_and_combine()
184
new_backing_file, size = self._spill_mem_keys_without_combining()
185
dir_path, base_name = osutils.split(new_backing_file.name)
186
# Note: The transport here isn't strictly needed, because we will use
187
# direct access to the new_backing._file object
188
new_backing = BTreeGraphIndex(get_transport(dir_path),
190
# GC will clean up the file
191
new_backing._file = new_backing_file
192
if self._combine_backing_indices:
193
if len(self._backing_indices) == backing_pos:
194
self._backing_indices.append(None)
195
self._backing_indices[backing_pos] = new_backing
196
for backing_pos in range(backing_pos):
197
self._backing_indices[backing_pos] = None
199
self._backing_indices.append(new_backing)
202
self._nodes_by_key = None
204
def _spill_mem_keys_without_combining(self):
205
return self._write_nodes(self._iter_mem_nodes(), allow_optimize=False)
207
def _spill_mem_keys_and_combine(self):
208
iterators_to_combine = [self._iter_mem_nodes()]
210
for pos, backing in enumerate(self._backing_indices):
214
iterators_to_combine.append(backing.iter_all_entries())
215
backing_pos = pos + 1
216
new_backing_file, size = \
217
self._write_nodes(self._iter_smallest(iterators_to_combine),
218
allow_optimize=False)
219
return new_backing_file, size, backing_pos
221
def add_nodes(self, nodes):
222
"""Add nodes to the index.
224
:param nodes: An iterable of (key, node_refs, value) entries to add.
226
if self.reference_lists:
227
for (key, value, node_refs) in nodes:
228
self.add_node(key, value, node_refs)
230
for (key, value) in nodes:
231
self.add_node(key, value)
233
def _iter_mem_nodes(self):
234
"""Iterate over the nodes held in memory."""
236
if self.reference_lists:
237
for key in sorted(nodes):
238
references, value = nodes[key]
239
yield self, key, value, references
241
for key in sorted(nodes):
242
references, value = nodes[key]
243
yield self, key, value
245
def _iter_smallest(self, iterators_to_combine):
246
if len(iterators_to_combine) == 1:
247
for value in iterators_to_combine[0]:
251
for iterator in iterators_to_combine:
253
current_values.append(iterator.next())
254
except StopIteration:
255
current_values.append(None)
258
# Decorate candidates with the value to allow 2.4's min to be used.
259
candidates = [(item[1][1], item) for item
260
in enumerate(current_values) if item[1] is not None]
261
if not len(candidates):
263
selected = min(candidates)
264
# undecorate back to (pos, node)
265
selected = selected[1]
266
if last == selected[1][1]:
267
raise errors.BadIndexDuplicateKey(last, self)
268
last = selected[1][1]
269
# Yield, with self as the index
270
yield (self,) + selected[1][1:]
273
current_values[pos] = iterators_to_combine[pos].next()
274
except StopIteration:
275
current_values[pos] = None
277
def _add_key(self, string_key, line, rows, allow_optimize=True):
278
"""Add a key to the current chunk.
280
:param string_key: The key to add.
281
:param line: The fully serialised key and value.
282
:param allow_optimize: If set to False, prevent setting the optimize
283
flag when writing out. This is used by the _spill_mem_keys_to_disk
286
if rows[-1].writer is None:
287
# opening a new leaf chunk;
288
for pos, internal_row in enumerate(rows[:-1]):
289
# flesh out any internal nodes that are needed to
290
# preserve the height of the tree
291
if internal_row.writer is None:
293
if internal_row.nodes == 0:
294
length -= _RESERVED_HEADER_BYTES # padded
296
optimize_for_size = self._optimize_for_size
298
optimize_for_size = False
299
internal_row.writer = chunk_writer.ChunkWriter(length, 0,
300
optimize_for_size=optimize_for_size)
301
internal_row.writer.write(_INTERNAL_FLAG)
302
internal_row.writer.write(_INTERNAL_OFFSET +
303
str(rows[pos + 1].nodes) + "\n")
306
if rows[-1].nodes == 0:
307
length -= _RESERVED_HEADER_BYTES # padded
308
rows[-1].writer = chunk_writer.ChunkWriter(length,
309
optimize_for_size=self._optimize_for_size)
310
rows[-1].writer.write(_LEAF_FLAG)
311
if rows[-1].writer.write(line):
312
# this key did not fit in the node:
313
rows[-1].finish_node()
314
key_line = string_key + "\n"
316
for row in reversed(rows[:-1]):
317
# Mark the start of the next node in the node above. If it
318
# doesn't fit then propagate upwards until we find one that
320
if row.writer.write(key_line):
323
# We've found a node that can handle the pointer.
326
# If we reached the current root without being able to mark the
327
# division point, then we need a new root:
330
if 'index' in debug.debug_flags:
331
trace.mutter('Inserting new global row.')
332
new_row = _InternalBuilderRow()
334
rows.insert(0, new_row)
335
# This will be padded, hence the -100
336
new_row.writer = chunk_writer.ChunkWriter(
337
_PAGE_SIZE - _RESERVED_HEADER_BYTES,
339
optimize_for_size=self._optimize_for_size)
340
new_row.writer.write(_INTERNAL_FLAG)
341
new_row.writer.write(_INTERNAL_OFFSET +
342
str(rows[1].nodes - 1) + "\n")
343
new_row.writer.write(key_line)
344
self._add_key(string_key, line, rows, allow_optimize=allow_optimize)
346
def _write_nodes(self, node_iterator, allow_optimize=True):
347
"""Write node_iterator out as a B+Tree.
349
:param node_iterator: An iterator of sorted nodes. Each node should
350
match the output given by iter_all_entries.
351
:param allow_optimize: If set to False, prevent setting the optimize
352
flag when writing out. This is used by the _spill_mem_keys_to_disk
354
:return: A file handle for a temporary file containing a B+Tree for
357
# The index rows - rows[0] is the root, rows[1] is the layer under it
360
# forward sorted by key. In future we may consider topological sorting,
361
# at the cost of table scans for direct lookup, or a second index for
364
# A stack with the number of nodes of each size. 0 is the root node
365
# and must always be 1 (if there are any nodes in the tree).
366
self.row_lengths = []
367
# Loop over all nodes adding them to the bottom row
368
# (rows[-1]). When we finish a chunk in a row,
369
# propagate the key that didn't fit (comes after the chunk) to the
370
# row above, transitively.
371
for node in node_iterator:
373
# First key triggers the first row
374
rows.append(_LeafBuilderRow())
376
string_key, line = _btree_serializer._flatten_node(node,
377
self.reference_lists)
378
self._add_key(string_key, line, rows, allow_optimize=allow_optimize)
379
for row in reversed(rows):
380
pad = (type(row) != _LeafBuilderRow)
381
row.finish_node(pad=pad)
382
result = tempfile.NamedTemporaryFile(prefix='bzr-index-')
383
lines = [_BTSIGNATURE]
384
lines.append(_OPTION_NODE_REFS + str(self.reference_lists) + '\n')
385
lines.append(_OPTION_KEY_ELEMENTS + str(self._key_length) + '\n')
386
lines.append(_OPTION_LEN + str(key_count) + '\n')
387
row_lengths = [row.nodes for row in rows]
388
lines.append(_OPTION_ROW_LENGTHS + ','.join(map(str, row_lengths)) + '\n')
389
result.writelines(lines)
390
position = sum(map(len, lines))
392
if position > _RESERVED_HEADER_BYTES:
393
raise AssertionError("Could not fit the header in the"
394
" reserved space: %d > %d"
395
% (position, _RESERVED_HEADER_BYTES))
396
# write the rows out:
398
reserved = _RESERVED_HEADER_BYTES # reserved space for first node
401
# copy nodes to the finalised file.
402
# Special case the first node as it may be prefixed
403
node = row.spool.read(_PAGE_SIZE)
404
result.write(node[reserved:])
405
result.write("\x00" * (reserved - position))
406
position = 0 # Only the root row actually has an offset
407
copied_len = osutils.pumpfile(row.spool, result)
408
if copied_len != (row.nodes - 1) * _PAGE_SIZE:
409
if type(row) != _LeafBuilderRow:
410
raise AssertionError("Incorrect amount of data copied"
411
" expected: %d, got: %d"
412
% ((row.nodes - 1) * _PAGE_SIZE,
420
"""Finalise the index.
422
:return: A file handle for a temporary file containing the nodes added
425
return self._write_nodes(self.iter_all_entries())[0]
427
def iter_all_entries(self):
428
"""Iterate over all keys within the index
430
:return: An iterable of (index, key, value, reference_lists). There is
431
no defined order for the result iteration - it will be in the most
432
efficient order for the index (in this case dictionary hash order).
434
if 'evil' in debug.debug_flags:
435
trace.mutter_callsite(3,
436
"iter_all_entries scales with size of history.")
437
# Doing serial rather than ordered would be faster; but this shouldn't
438
# be getting called routinely anyway.
439
iterators = [self._iter_mem_nodes()]
440
for backing in self._backing_indices:
441
if backing is not None:
442
iterators.append(backing.iter_all_entries())
443
if len(iterators) == 1:
445
return self._iter_smallest(iterators)
447
def iter_entries(self, keys):
448
"""Iterate over keys within the index.
450
:param keys: An iterable providing the keys to be retrieved.
451
:return: An iterable of (index, key, value, reference_lists). There is no
452
defined order for the result iteration - it will be in the most
453
efficient order for the index (keys iteration order in this case).
456
local_keys = keys.intersection(self._keys)
457
if self.reference_lists:
458
for key in local_keys:
459
node = self._nodes[key]
460
yield self, key, node[1], node[0]
462
for key in local_keys:
463
node = self._nodes[key]
464
yield self, key, node[1]
465
# Find things that are in backing indices that have not been handled
467
if not self._backing_indices:
468
return # We won't find anything there either
469
# Remove all of the keys that we found locally
470
keys.difference_update(local_keys)
471
for backing in self._backing_indices:
476
for node in backing.iter_entries(keys):
478
yield (self,) + node[1:]
480
def iter_entries_prefix(self, keys):
481
"""Iterate over keys within the index using prefix matching.
483
Prefix matching is applied within the tuple of a key, not to within
484
the bytestring of each key element. e.g. if you have the keys ('foo',
485
'bar'), ('foobar', 'gam') and do a prefix search for ('foo', None) then
486
only the former key is returned.
488
:param keys: An iterable providing the key prefixes to be retrieved.
489
Each key prefix takes the form of a tuple the length of a key, but
490
with the last N elements 'None' rather than a regular bytestring.
491
The first element cannot be 'None'.
492
:return: An iterable as per iter_all_entries, but restricted to the
493
keys with a matching prefix to those supplied. No additional keys
494
will be returned, and every match that is in the index will be
497
# XXX: To much duplication with the GraphIndex class; consider finding
498
# a good place to pull out the actual common logic.
502
for backing in self._backing_indices:
505
for node in backing.iter_entries_prefix(keys):
506
yield (self,) + node[1:]
507
if self._key_length == 1:
511
raise errors.BadIndexKey(key)
512
if len(key) != self._key_length:
513
raise errors.BadIndexKey(key)
515
node = self._nodes[key]
518
if self.reference_lists:
519
yield self, key, node[1], node[0]
521
yield self, key, node[1]
526
raise errors.BadIndexKey(key)
527
if len(key) != self._key_length:
528
raise errors.BadIndexKey(key)
529
# find what it refers to:
530
key_dict = self._get_nodes_by_key()
532
# find the subdict to return
534
while len(elements) and elements[0] is not None:
535
key_dict = key_dict[elements[0]]
538
# a non-existant lookup.
543
key_dict = dicts.pop(-1)
544
# can't be empty or would not exist
545
item, value = key_dict.iteritems().next()
546
if type(value) == dict:
548
dicts.extend(key_dict.itervalues())
551
for value in key_dict.itervalues():
552
yield (self, ) + value
554
yield (self, ) + key_dict
556
def _get_nodes_by_key(self):
557
if self._nodes_by_key is None:
559
if self.reference_lists:
560
for key, (references, value) in self._nodes.iteritems():
561
key_dict = nodes_by_key
562
for subkey in key[:-1]:
563
key_dict = key_dict.setdefault(subkey, {})
564
key_dict[key[-1]] = key, value, references
566
for key, (references, value) in self._nodes.iteritems():
567
key_dict = nodes_by_key
568
for subkey in key[:-1]:
569
key_dict = key_dict.setdefault(subkey, {})
570
key_dict[key[-1]] = key, value
571
self._nodes_by_key = nodes_by_key
572
return self._nodes_by_key
575
"""Return an estimate of the number of keys in this index.
577
For InMemoryGraphIndex the estimate is exact.
579
return len(self._keys) + sum(backing.key_count() for backing in
580
self._backing_indices if backing is not None)
583
"""In memory index's have no known corruption at the moment."""
586
class _LeafNode(object):
587
"""A leaf node for a serialised B+Tree index."""
589
__slots__ = ('keys', 'min_key', 'max_key')
591
def __init__(self, bytes, key_length, ref_list_length):
592
"""Parse bytes to create a leaf node object."""
593
# splitlines mangles the \r delimiters.. don't use it.
594
key_list = _btree_serializer._parse_leaf_lines(bytes,
595
key_length, ref_list_length)
597
self.min_key = key_list[0][0]
598
self.max_key = key_list[-1][0]
600
self.min_key = self.max_key = None
601
self.keys = dict(key_list)
604
class _InternalNode(object):
605
"""An internal node for a serialised B+Tree index."""
607
__slots__ = ('keys', 'offset')
609
def __init__(self, bytes):
610
"""Parse bytes to create an internal node object."""
611
# splitlines mangles the \r delimiters.. don't use it.
612
self.keys = self._parse_lines(bytes.split('\n'))
614
def _parse_lines(self, lines):
616
self.offset = int(lines[1][7:])
617
for line in lines[2:]:
620
nodes.append(tuple(map(intern, line.split('\0'))))
624
class BTreeGraphIndex(object):
625
"""Access to nodes via the standard GraphIndex interface for B+Tree's.
627
Individual nodes are held in a LRU cache. This holds the root node in
628
memory except when very large walks are done.
631
def __init__(self, transport, name, size, unlimited_cache=False):
632
"""Create a B+Tree index object on the index name.
634
:param transport: The transport to read data for the index from.
635
:param name: The file name of the index on transport.
636
:param size: Optional size of the index in bytes. This allows
637
compatibility with the GraphIndex API, as well as ensuring that
638
the initial read (to read the root node header) can be done
639
without over-reading even on empty indices, and on small indices
640
allows single-IO to read the entire index.
641
:param unlimited_cache: If set to True, then instead of using an
642
LRUCache with size _NODE_CACHE_SIZE, we will use a dict and always
643
cache all leaf nodes.
645
self._transport = transport
649
self._recommended_pages = self._compute_recommended_pages()
650
self._root_node = None
651
# Default max size is 100,000 leave values
652
self._leaf_value_cache = None # lru_cache.LRUCache(100*1000)
654
self._leaf_node_cache = {}
655
self._internal_node_cache = {}
657
self._leaf_node_cache = lru_cache.LRUCache(_NODE_CACHE_SIZE)
658
# We use a FIFO here just to prevent possible blowout. However, a
659
# 300k record btree has only 3k leaf nodes, and only 20 internal
660
# nodes. A value of 100 scales to ~100*100*100 = 1M records.
661
self._internal_node_cache = fifo_cache.FIFOCache(100)
662
self._key_count = None
663
self._row_lengths = None
664
self._row_offsets = None # Start of each row, [-1] is the end
666
def __eq__(self, other):
667
"""Equal when self and other were created with the same parameters."""
669
type(self) == type(other) and
670
self._transport == other._transport and
671
self._name == other._name and
672
self._size == other._size)
674
def __ne__(self, other):
675
return not self.__eq__(other)
677
def _get_and_cache_nodes(self, nodes):
678
"""Read nodes and cache them in the lru.
680
The nodes list supplied is sorted and then read from disk, each node
681
being inserted it into the _node_cache.
683
Note: Asking for more nodes than the _node_cache can contain will
684
result in some of the results being immediately discarded, to prevent
685
this an assertion is raised if more nodes are asked for than are
688
:return: A dict of {node_pos: node}
691
start_of_leaves = None
692
for node_pos, node in self._read_nodes(sorted(nodes)):
693
if node_pos == 0: # Special case
694
self._root_node = node
696
if start_of_leaves is None:
697
start_of_leaves = self._row_offsets[-2]
698
if node_pos < start_of_leaves:
699
self._internal_node_cache[node_pos] = node
701
self._leaf_node_cache[node_pos] = node
702
found[node_pos] = node
705
def _compute_recommended_pages(self):
706
"""Convert transport's recommended_page_size into btree pages.
708
recommended_page_size is in bytes, we want to know how many _PAGE_SIZE
709
pages fit in that length.
711
recommended_read = self._transport.recommended_page_size()
712
recommended_pages = int(math.ceil(recommended_read /
714
return recommended_pages
716
def _compute_total_pages_in_index(self):
717
"""How many pages are in the index.
719
If we have read the header we will use the value stored there.
720
Otherwise it will be computed based on the length of the index.
722
if self._size is None:
723
raise AssertionError('_compute_total_pages_in_index should not be'
724
' called when self._size is None')
725
if self._root_node is not None:
726
# This is the number of pages as defined by the header
727
return self._row_offsets[-1]
728
# This is the number of pages as defined by the size of the index. They
729
# should be indentical.
730
total_pages = int(math.ceil(self._size / float(_PAGE_SIZE)))
733
def _expand_offsets(self, offsets):
734
"""Find extra pages to download.
736
The idea is that we always want to make big-enough requests (like 64kB
737
for http), so that we don't waste round trips. So given the entries
738
that we already have cached and the new pages being downloaded figure
739
out what other pages we might want to read.
741
See also doc/developers/btree_index_prefetch.txt for more details.
743
:param offsets: The offsets to be read
744
:return: A list of offsets to download
746
if 'index' in debug.debug_flags:
747
trace.mutter('expanding: %s\toffsets: %s', self._name, offsets)
749
if len(offsets) >= self._recommended_pages:
750
# Don't add more, we are already requesting more than enough
751
if 'index' in debug.debug_flags:
752
trace.mutter(' not expanding large request (%s >= %s)',
753
len(offsets), self._recommended_pages)
755
if self._size is None:
756
# Don't try anything, because we don't know where the file ends
757
if 'index' in debug.debug_flags:
758
trace.mutter(' not expanding without knowing index size')
760
total_pages = self._compute_total_pages_in_index()
761
cached_offsets = self._get_offsets_to_cached_pages()
762
# If reading recommended_pages would read the rest of the index, just
764
if total_pages - len(cached_offsets) <= self._recommended_pages:
765
# Read whatever is left
767
expanded = [x for x in xrange(total_pages)
768
if x not in cached_offsets]
770
expanded = range(total_pages)
771
if 'index' in debug.debug_flags:
772
trace.mutter(' reading all unread pages: %s', expanded)
775
if self._root_node is None:
776
# ATM on the first read of the root node of a large index, we don't
777
# bother pre-reading any other pages. This is because the
778
# likelyhood of actually reading interesting pages is very low.
779
# See doc/developers/btree_index_prefetch.txt for a discussion, and
780
# a possible implementation when we are guessing that the second
781
# layer index is small
782
final_offsets = offsets
784
tree_depth = len(self._row_lengths)
785
if len(cached_offsets) < tree_depth and len(offsets) == 1:
786
# We haven't read enough to justify expansion
787
# If we are only going to read the root node, and 1 leaf node,
788
# then it isn't worth expanding our request. Once we've read at
789
# least 2 nodes, then we are probably doing a search, and we
790
# start expanding our requests.
791
if 'index' in debug.debug_flags:
792
trace.mutter(' not expanding on first reads')
794
final_offsets = self._expand_to_neighbors(offsets, cached_offsets,
797
final_offsets = sorted(final_offsets)
798
if 'index' in debug.debug_flags:
799
trace.mutter('expanded: %s', final_offsets)
802
def _expand_to_neighbors(self, offsets, cached_offsets, total_pages):
803
"""Expand requests to neighbors until we have enough pages.
805
This is called from _expand_offsets after policy has determined that we
807
We only want to expand requests within a given layer. We cheat a little
808
bit and assume all requests will be in the same layer. This is true
809
given the current design, but if it changes this algorithm may perform
812
:param offsets: requested offsets
813
:param cached_offsets: offsets for pages we currently have cached
814
:return: A set() of offsets after expansion
816
final_offsets = set(offsets)
818
new_tips = set(final_offsets)
819
while len(final_offsets) < self._recommended_pages and new_tips:
823
first, end = self._find_layer_first_and_end(pos)
826
and previous not in cached_offsets
827
and previous not in final_offsets
828
and previous >= first):
829
next_tips.add(previous)
831
if (after < total_pages
832
and after not in cached_offsets
833
and after not in final_offsets
836
# This would keep us from going bigger than
837
# recommended_pages by only expanding the first offsets.
838
# However, if we are making a 'wide' request, it is
839
# reasonable to expand all points equally.
840
# if len(final_offsets) > recommended_pages:
842
final_offsets.update(next_tips)
846
def external_references(self, ref_list_num):
847
if self._root_node is None:
848
self._get_root_node()
849
if ref_list_num + 1 > self.node_ref_lists:
850
raise ValueError('No ref list %d, index has %d ref lists'
851
% (ref_list_num, self.node_ref_lists))
854
for node in self.iter_all_entries():
856
refs.update(node[3][ref_list_num])
859
def _find_layer_first_and_end(self, offset):
860
"""Find the start/stop nodes for the layer corresponding to offset.
862
:return: (first, end)
863
first is the first node in this layer
864
end is the first node of the next layer
867
for roffset in self._row_offsets:
874
def _get_offsets_to_cached_pages(self):
875
"""Determine what nodes we already have cached."""
876
cached_offsets = set(self._internal_node_cache.keys())
877
cached_offsets.update(self._leaf_node_cache.keys())
878
if self._root_node is not None:
879
cached_offsets.add(0)
880
return cached_offsets
882
def _get_root_node(self):
883
if self._root_node is None:
884
# We may not have a root node yet
885
self._get_internal_nodes([0])
886
return self._root_node
888
def _get_nodes(self, cache, node_indexes):
891
for idx in node_indexes:
892
if idx == 0 and self._root_node is not None:
893
found[0] = self._root_node
896
found[idx] = cache[idx]
901
needed = self._expand_offsets(needed)
902
found.update(self._get_and_cache_nodes(needed))
905
def _get_internal_nodes(self, node_indexes):
906
"""Get a node, from cache or disk.
908
After getting it, the node will be cached.
910
return self._get_nodes(self._internal_node_cache, node_indexes)
912
def _cache_leaf_values(self, nodes):
913
"""Cache directly from key => value, skipping the btree."""
914
if self._leaf_value_cache is not None:
915
for node in nodes.itervalues():
916
for key, value in node.keys.iteritems():
917
if key in self._leaf_value_cache:
918
# Don't add the rest of the keys, we've seen this node
921
self._leaf_value_cache[key] = value
923
def _get_leaf_nodes(self, node_indexes):
924
"""Get a bunch of nodes, from cache or disk."""
925
found = self._get_nodes(self._leaf_node_cache, node_indexes)
926
self._cache_leaf_values(found)
929
def iter_all_entries(self):
930
"""Iterate over all keys within the index.
932
:return: An iterable of (index, key, value) or (index, key, value, reference_lists).
933
The former tuple is used when there are no reference lists in the
934
index, making the API compatible with simple key:value index types.
935
There is no defined order for the result iteration - it will be in
936
the most efficient order for the index.
938
if 'evil' in debug.debug_flags:
939
trace.mutter_callsite(3,
940
"iter_all_entries scales with size of history.")
941
if not self.key_count():
943
if self._row_offsets[-1] == 1:
944
# There is only the root node, and we read that via key_count()
945
if self.node_ref_lists:
946
for key, (value, refs) in sorted(self._root_node.keys.items()):
947
yield (self, key, value, refs)
949
for key, (value, refs) in sorted(self._root_node.keys.items()):
950
yield (self, key, value)
952
start_of_leaves = self._row_offsets[-2]
953
end_of_leaves = self._row_offsets[-1]
954
needed_offsets = range(start_of_leaves, end_of_leaves)
955
if needed_offsets == [0]:
956
# Special case when we only have a root node, as we have already
958
nodes = [(0, self._root_node)]
960
nodes = self._read_nodes(needed_offsets)
961
# We iterate strictly in-order so that we can use this function
962
# for spilling index builds to disk.
963
if self.node_ref_lists:
964
for _, node in nodes:
965
for key, (value, refs) in sorted(node.keys.items()):
966
yield (self, key, value, refs)
968
for _, node in nodes:
969
for key, (value, refs) in sorted(node.keys.items()):
970
yield (self, key, value)
973
def _multi_bisect_right(in_keys, fixed_keys):
974
"""Find the positions where each 'in_key' would fit in fixed_keys.
976
This is equivalent to doing "bisect_right" on each in_key into
979
:param in_keys: A sorted list of keys to match with fixed_keys
980
:param fixed_keys: A sorted list of keys to match against
981
:return: A list of (integer position, [key list]) tuples.
986
# no pointers in the fixed_keys list, which means everything must
988
return [(0, in_keys)]
990
# TODO: Iterating both lists will generally take M + N steps
991
# Bisecting each key will generally take M * log2 N steps.
992
# If we had an efficient way to compare, we could pick the method
993
# based on which has the fewer number of steps.
994
# There is also the argument that bisect_right is a compiled
995
# function, so there is even more to be gained.
996
# iter_steps = len(in_keys) + len(fixed_keys)
997
# bisect_steps = len(in_keys) * math.log(len(fixed_keys), 2)
998
if len(in_keys) == 1: # Bisect will always be faster for M = 1
999
return [(bisect_right(fixed_keys, in_keys[0]), in_keys)]
1000
# elif bisect_steps < iter_steps:
1002
# for key in in_keys:
1003
# offsets.setdefault(bisect_right(fixed_keys, key),
1005
# return [(o, offsets[o]) for o in sorted(offsets)]
1006
in_keys_iter = iter(in_keys)
1007
fixed_keys_iter = enumerate(fixed_keys)
1008
cur_in_key = in_keys_iter.next()
1009
cur_fixed_offset, cur_fixed_key = fixed_keys_iter.next()
1011
class InputDone(Exception): pass
1012
class FixedDone(Exception): pass
1017
# TODO: Another possibility is that rather than iterating on each side,
1018
# we could use a combination of bisecting and iterating. For
1019
# example, while cur_in_key < fixed_key, bisect to find its
1020
# point, then iterate all matching keys, then bisect (restricted
1021
# to only the remainder) for the next one, etc.
1024
if cur_in_key < cur_fixed_key:
1026
cur_out = (cur_fixed_offset, cur_keys)
1027
output.append(cur_out)
1028
while cur_in_key < cur_fixed_key:
1029
cur_keys.append(cur_in_key)
1031
cur_in_key = in_keys_iter.next()
1032
except StopIteration:
1034
# At this point cur_in_key must be >= cur_fixed_key
1035
# step the cur_fixed_key until we pass the cur key, or walk off
1037
while cur_in_key >= cur_fixed_key:
1039
cur_fixed_offset, cur_fixed_key = fixed_keys_iter.next()
1040
except StopIteration:
1043
# We consumed all of the input, nothing more to do
1046
# There was some input left, but we consumed all of fixed, so we
1047
# have to add one more for the tail
1048
cur_keys = [cur_in_key]
1049
cur_keys.extend(in_keys_iter)
1050
cur_out = (len(fixed_keys), cur_keys)
1051
output.append(cur_out)
1054
def _walk_through_internal_nodes(self, keys):
1055
"""Take the given set of keys, and find the corresponding LeafNodes.
1057
:param keys: An unsorted iterable of keys to search for
1058
:return: (nodes, index_and_keys)
1059
nodes is a dict mapping {index: LeafNode}
1060
keys_at_index is a list of tuples of [(index, [keys for Leaf])]
1062
# 6 seconds spent in miss_torture using the sorted() line.
1063
# Even with out of order disk IO it seems faster not to sort it when
1064
# large queries are being made.
1065
keys_at_index = [(0, sorted(keys))]
1067
for row_pos, next_row_start in enumerate(self._row_offsets[1:-1]):
1068
node_indexes = [idx for idx, s_keys in keys_at_index]
1069
nodes = self._get_internal_nodes(node_indexes)
1071
next_nodes_and_keys = []
1072
for node_index, sub_keys in keys_at_index:
1073
node = nodes[node_index]
1074
positions = self._multi_bisect_right(sub_keys, node.keys)
1075
node_offset = next_row_start + node.offset
1076
next_nodes_and_keys.extend([(node_offset + pos, s_keys)
1077
for pos, s_keys in positions])
1078
keys_at_index = next_nodes_and_keys
1079
# We should now be at the _LeafNodes
1080
node_indexes = [idx for idx, s_keys in keys_at_index]
1082
# TODO: We may *not* want to always read all the nodes in one
1083
# big go. Consider setting a max size on this.
1084
nodes = self._get_leaf_nodes(node_indexes)
1085
return nodes, keys_at_index
1087
def iter_entries(self, keys):
1088
"""Iterate over keys within the index.
1090
:param keys: An iterable providing the keys to be retrieved.
1091
:return: An iterable as per iter_all_entries, but restricted to the
1092
keys supplied. No additional keys will be returned, and every
1093
key supplied that is in the index will be returned.
1095
# 6 seconds spent in miss_torture using the sorted() line.
1096
# Even with out of order disk IO it seems faster not to sort it when
1097
# large queries are being made.
1098
# However, now that we are doing multi-way bisecting, we need the keys
1099
# in sorted order anyway. We could change the multi-way code to not
1100
# require sorted order. (For example, it bisects for the first node,
1101
# does an in-order search until a key comes before the current point,
1102
# which it then bisects for, etc.)
1103
keys = frozenset(keys)
1107
if not self.key_count():
1111
if self._leaf_value_cache is None:
1115
value = self._leaf_value_cache.get(key, None)
1116
if value is not None:
1117
# This key is known not to be here, skip it
1119
if self.node_ref_lists:
1120
yield (self, key, value, refs)
1122
yield (self, key, value)
1124
needed_keys.append(key)
1130
nodes, nodes_and_keys = self._walk_through_internal_nodes(needed_keys)
1131
for node_index, sub_keys in nodes_and_keys:
1134
node = nodes[node_index]
1135
for next_sub_key in sub_keys:
1136
if next_sub_key in node.keys:
1137
value, refs = node.keys[next_sub_key]
1138
if self.node_ref_lists:
1139
yield (self, next_sub_key, value, refs)
1141
yield (self, next_sub_key, value)
1143
def _find_ancestors(self, keys, ref_list_num, parent_map, missing_keys):
1144
"""Find the parent_map information for the set of keys.
1146
This populates the parent_map dict and missing_keys set based on the
1147
queried keys. It also can fill out an arbitrary number of parents that
1148
it finds while searching for the supplied keys.
1150
It is unlikely that you want to call this directly. See
1151
"CombinedGraphIndex.find_ancestry()" for a more appropriate API.
1153
:param keys: A keys whose ancestry we want to return
1154
Every key will either end up in 'parent_map' or 'missing_keys'.
1155
:param ref_list_num: This index in the ref_lists is the parents we
1157
:param parent_map: {key: parent_keys} for keys that are present in this
1158
index. This may contain more entries than were in 'keys', that are
1159
reachable ancestors of the keys requested.
1160
:param missing_keys: keys which are known to be missing in this index.
1161
This may include parents that were not directly requested, but we
1162
were able to determine that they are not present in this index.
1163
:return: search_keys parents that were found but not queried to know
1164
if they are missing or present. Callers can re-query this index for
1165
those keys, and they will be placed into parent_map or missing_keys
1167
if not self.key_count():
1168
# We use key_count() to trigger reading the root node and
1169
# determining info about this BTreeGraphIndex
1170
# If we don't have any keys, then everything is missing
1171
missing_keys.update(keys)
1173
if ref_list_num >= self.node_ref_lists:
1174
raise ValueError('No ref list %d, index has %d ref lists'
1175
% (ref_list_num, self.node_ref_lists))
1177
# The main trick we are trying to accomplish is that when we find a
1178
# key listing its parents, we expect that the parent key is also likely
1179
# to sit on the same page. Allowing us to expand parents quickly
1180
# without suffering the full stack of bisecting, etc.
1181
nodes, nodes_and_keys = self._walk_through_internal_nodes(keys)
1183
# These are parent keys which could not be immediately resolved on the
1184
# page where the child was present. Note that we may already be
1185
# searching for that key, and it may actually be present [or known
1186
# missing] on one of the other pages we are reading.
1188
# We could try searching for them in the immediate previous or next
1189
# page. If they occur "later" we could put them in a pending lookup
1190
# set, and then for each node we read thereafter we could check to
1191
# see if they are present.
1192
# However, we don't know the impact of keeping this list of things
1193
# that I'm going to search for every node I come across from here on
1195
# It doesn't handle the case when the parent key is missing on a
1196
# page that we *don't* read. So we already have to handle being
1197
# re-entrant for that.
1198
# Since most keys contain a date string, they are more likely to be
1199
# found earlier in the file than later, but we would know that right
1200
# away (key < min_key), and wouldn't keep searching it on every other
1201
# page that we read.
1202
# Mostly, it is an idea, one which should be benchmarked.
1203
parents_not_on_page = set()
1205
for node_index, sub_keys in nodes_and_keys:
1208
# sub_keys is all of the keys we are looking for that should exist
1209
# on this page, if they aren't here, then they won't be found
1210
node = nodes[node_index]
1211
node_keys = node.keys
1212
parents_to_check = set()
1213
for next_sub_key in sub_keys:
1214
if next_sub_key not in node_keys:
1215
# This one is just not present in the index at all
1216
missing_keys.add(next_sub_key)
1218
value, refs = node_keys[next_sub_key]
1219
parent_keys = refs[ref_list_num]
1220
parent_map[next_sub_key] = parent_keys
1221
parents_to_check.update(parent_keys)
1222
# Don't look for things we've already found
1223
parents_to_check = parents_to_check.difference(parent_map)
1224
# this can be used to test the benefit of having the check loop
1226
# parents_not_on_page.update(parents_to_check)
1228
while parents_to_check:
1229
next_parents_to_check = set()
1230
for key in parents_to_check:
1231
if key in node_keys:
1232
value, refs = node_keys[key]
1233
parent_keys = refs[ref_list_num]
1234
parent_map[key] = parent_keys
1235
next_parents_to_check.update(parent_keys)
1237
# This parent either is genuinely missing, or should be
1238
# found on another page. Perf test whether it is better
1239
# to check if this node should fit on this page or not.
1240
# in the 'everything-in-one-pack' scenario, this *not*
1241
# doing the check is 237ms vs 243ms.
1242
# So slightly better, but I assume the standard 'lots
1243
# of packs' is going to show a reasonable improvement
1244
# from the check, because it avoids 'going around
1245
# again' for everything that is in another index
1246
# parents_not_on_page.add(key)
1247
# Missing for some reason
1248
if key < node.min_key:
1249
# in the case of bzr.dev, 3.4k/5.3k misses are
1250
# 'earlier' misses (65%)
1251
parents_not_on_page.add(key)
1252
elif key > node.max_key:
1253
# This parent key would be present on a different
1255
parents_not_on_page.add(key)
1257
# assert key != node.min_key and key != node.max_key
1258
# If it was going to be present, it would be on
1259
# *this* page, so mark it missing.
1260
missing_keys.add(key)
1261
parents_to_check = next_parents_to_check.difference(parent_map)
1262
# Might want to do another .difference() from missing_keys
1263
# parents_not_on_page could have been found on a different page, or be
1264
# known to be missing. So cull out everything that has already been
1266
search_keys = parents_not_on_page.difference(
1267
parent_map).difference(missing_keys)
1270
def iter_entries_prefix(self, keys):
1271
"""Iterate over keys within the index using prefix matching.
1273
Prefix matching is applied within the tuple of a key, not to within
1274
the bytestring of each key element. e.g. if you have the keys ('foo',
1275
'bar'), ('foobar', 'gam') and do a prefix search for ('foo', None) then
1276
only the former key is returned.
1278
WARNING: Note that this method currently causes a full index parse
1279
unconditionally (which is reasonably appropriate as it is a means for
1280
thunking many small indices into one larger one and still supplies
1281
iter_all_entries at the thunk layer).
1283
:param keys: An iterable providing the key prefixes to be retrieved.
1284
Each key prefix takes the form of a tuple the length of a key, but
1285
with the last N elements 'None' rather than a regular bytestring.
1286
The first element cannot be 'None'.
1287
:return: An iterable as per iter_all_entries, but restricted to the
1288
keys with a matching prefix to those supplied. No additional keys
1289
will be returned, and every match that is in the index will be
1292
keys = sorted(set(keys))
1295
# Load if needed to check key lengths
1296
if self._key_count is None:
1297
self._get_root_node()
1298
# TODO: only access nodes that can satisfy the prefixes we are looking
1299
# for. For now, to meet API usage (as this function is not used by
1300
# current bzrlib) just suck the entire index and iterate in memory.
1302
if self.node_ref_lists:
1303
if self._key_length == 1:
1304
for _1, key, value, refs in self.iter_all_entries():
1305
nodes[key] = value, refs
1308
for _1, key, value, refs in self.iter_all_entries():
1309
key_value = key, value, refs
1310
# For a key of (foo, bar, baz) create
1311
# _nodes_by_key[foo][bar][baz] = key_value
1312
key_dict = nodes_by_key
1313
for subkey in key[:-1]:
1314
key_dict = key_dict.setdefault(subkey, {})
1315
key_dict[key[-1]] = key_value
1317
if self._key_length == 1:
1318
for _1, key, value in self.iter_all_entries():
1322
for _1, key, value in self.iter_all_entries():
1323
key_value = key, value
1324
# For a key of (foo, bar, baz) create
1325
# _nodes_by_key[foo][bar][baz] = key_value
1326
key_dict = nodes_by_key
1327
for subkey in key[:-1]:
1328
key_dict = key_dict.setdefault(subkey, {})
1329
key_dict[key[-1]] = key_value
1330
if self._key_length == 1:
1334
raise errors.BadIndexKey(key)
1335
if len(key) != self._key_length:
1336
raise errors.BadIndexKey(key)
1338
if self.node_ref_lists:
1339
value, node_refs = nodes[key]
1340
yield self, key, value, node_refs
1342
yield self, key, nodes[key]
1349
raise errors.BadIndexKey(key)
1350
if len(key) != self._key_length:
1351
raise errors.BadIndexKey(key)
1352
# find what it refers to:
1353
key_dict = nodes_by_key
1354
elements = list(key)
1355
# find the subdict whose contents should be returned.
1357
while len(elements) and elements[0] is not None:
1358
key_dict = key_dict[elements[0]]
1361
# a non-existant lookup.
1366
key_dict = dicts.pop(-1)
1367
# can't be empty or would not exist
1368
item, value = key_dict.iteritems().next()
1369
if type(value) == dict:
1371
dicts.extend(key_dict.itervalues())
1374
for value in key_dict.itervalues():
1375
# each value is the key:value:node refs tuple
1377
yield (self, ) + value
1379
# the last thing looked up was a terminal element
1380
yield (self, ) + key_dict
1382
def key_count(self):
1383
"""Return an estimate of the number of keys in this index.
1385
For BTreeGraphIndex the estimate is exact as it is contained in the
1388
if self._key_count is None:
1389
self._get_root_node()
1390
return self._key_count
1392
def _compute_row_offsets(self):
1393
"""Fill out the _row_offsets attribute based on _row_lengths."""
1396
for row in self._row_lengths:
1397
offsets.append(row_offset)
1399
offsets.append(row_offset)
1400
self._row_offsets = offsets
1402
def _parse_header_from_bytes(self, bytes):
1403
"""Parse the header from a region of bytes.
1405
:param bytes: The data to parse.
1406
:return: An offset, data tuple such as readv yields, for the unparsed
1407
data. (which may be of length 0).
1409
signature = bytes[0:len(self._signature())]
1410
if not signature == self._signature():
1411
raise errors.BadIndexFormatSignature(self._name, BTreeGraphIndex)
1412
lines = bytes[len(self._signature()):].splitlines()
1413
options_line = lines[0]
1414
if not options_line.startswith(_OPTION_NODE_REFS):
1415
raise errors.BadIndexOptions(self)
1417
self.node_ref_lists = int(options_line[len(_OPTION_NODE_REFS):])
1419
raise errors.BadIndexOptions(self)
1420
options_line = lines[1]
1421
if not options_line.startswith(_OPTION_KEY_ELEMENTS):
1422
raise errors.BadIndexOptions(self)
1424
self._key_length = int(options_line[len(_OPTION_KEY_ELEMENTS):])
1426
raise errors.BadIndexOptions(self)
1427
options_line = lines[2]
1428
if not options_line.startswith(_OPTION_LEN):
1429
raise errors.BadIndexOptions(self)
1431
self._key_count = int(options_line[len(_OPTION_LEN):])
1433
raise errors.BadIndexOptions(self)
1434
options_line = lines[3]
1435
if not options_line.startswith(_OPTION_ROW_LENGTHS):
1436
raise errors.BadIndexOptions(self)
1438
self._row_lengths = map(int, [length for length in
1439
options_line[len(_OPTION_ROW_LENGTHS):].split(',')
1442
raise errors.BadIndexOptions(self)
1443
self._compute_row_offsets()
1445
# calculate the bytes we have processed
1446
header_end = (len(signature) + sum(map(len, lines[0:4])) + 4)
1447
return header_end, bytes[header_end:]
1449
def _read_nodes(self, nodes):
1450
"""Read some nodes from disk into the LRU cache.
1452
This performs a readv to get the node data into memory, and parses each
1453
node, then yields it to the caller. The nodes are requested in the
1454
supplied order. If possible doing sort() on the list before requesting
1455
a read may improve performance.
1457
:param nodes: The nodes to read. 0 - first node, 1 - second node etc.
1460
# may be the byte string of the whole file
1462
# list of (offset, length) regions of the file that should, evenually
1463
# be read in to data_ranges, either from 'bytes' or from the transport
1466
offset = index * _PAGE_SIZE
1469
# Root node - special case
1471
size = min(_PAGE_SIZE, self._size)
1473
# The only case where we don't know the size, is for very
1474
# small indexes. So we read the whole thing
1475
bytes = self._transport.get_bytes(self._name)
1476
self._size = len(bytes)
1477
# the whole thing should be parsed out of 'bytes'
1478
ranges.append((0, len(bytes)))
1481
if offset > self._size:
1482
raise AssertionError('tried to read past the end'
1483
' of the file %s > %s'
1484
% (offset, self._size))
1485
size = min(size, self._size - offset)
1486
ranges.append((offset, size))
1489
elif bytes is not None:
1490
# already have the whole file
1491
data_ranges = [(start, bytes[start:start+_PAGE_SIZE])
1492
for start in xrange(0, len(bytes), _PAGE_SIZE)]
1493
elif self._file is None:
1494
data_ranges = self._transport.readv(self._name, ranges)
1497
for offset, size in ranges:
1498
self._file.seek(offset)
1499
data_ranges.append((offset, self._file.read(size)))
1500
for offset, data in data_ranges:
1502
# extract the header
1503
offset, data = self._parse_header_from_bytes(data)
1506
bytes = zlib.decompress(data)
1507
if bytes.startswith(_LEAF_FLAG):
1508
node = _LeafNode(bytes, self._key_length, self.node_ref_lists)
1509
elif bytes.startswith(_INTERNAL_FLAG):
1510
node = _InternalNode(bytes)
1512
raise AssertionError("Unknown node type for %r" % bytes)
1513
yield offset / _PAGE_SIZE, node
1515
def _signature(self):
1516
"""The file signature for this index type."""
1520
"""Validate that everything in the index can be accessed."""
1521
# just read and parse every node.
1522
self._get_root_node()
1523
if len(self._row_lengths) > 1:
1524
start_node = self._row_offsets[1]
1526
# We shouldn't be reading anything anyway
1528
node_end = self._row_offsets[-1]
1529
for node in self._read_nodes(range(start_node, node_end)):
1534
from bzrlib import _btree_serializer_pyx as _btree_serializer
1536
from bzrlib import _btree_serializer_py as _btree_serializer
added
removed
bzrlib/btree_index.py
