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
21
from bisect import bisect_right
36
from bzrlib.index import _OPTION_NODE_REFS, _OPTION_KEY_ELEMENTS, _OPTION_LEN
37
from bzrlib.transport import get_transport
40
_BTSIGNATURE = "B+Tree Graph Index 2\n"
41
_OPTION_ROW_LENGTHS = "row_lengths="
42
_LEAF_FLAG = "type=leaf\n"
43
_INTERNAL_FLAG = "type=internal\n"
44
_INTERNAL_OFFSET = "offset="
46
_RESERVED_HEADER_BYTES = 120
49
# 4K per page: 4MB - 1000 entries
50
_NODE_CACHE_SIZE = 1000
53
class _BuilderRow(object):
54
"""The stored state accumulated while writing out a row in the index.
56
:ivar spool: A temporary file used to accumulate nodes for this row
58
:ivar nodes: The count of nodes emitted so far.
62
"""Create a _BuilderRow."""
64
self.spool = None# tempfile.TemporaryFile(prefix='bzr-index-row-')
67
def finish_node(self, pad=True):
68
byte_lines, _, padding = self.writer.finish()
70
self.spool = cStringIO.StringIO()
72
self.spool.write("\x00" * _RESERVED_HEADER_BYTES)
74
# We got bigger than 1 node, switch to a temp file
75
spool = tempfile.TemporaryFile(prefix='bzr-index-row-')
76
spool.write(self.spool.getvalue())
79
if not pad and padding:
81
skipped_bytes = padding
82
self.spool.writelines(byte_lines)
83
remainder = (self.spool.tell() + skipped_bytes) % _PAGE_SIZE
85
raise AssertionError("incorrect node length: %d, %d"
86
% (self.spool.tell(), remainder))
91
class _InternalBuilderRow(_BuilderRow):
92
"""The stored state accumulated while writing out internal rows."""
94
def finish_node(self, pad=True):
96
raise AssertionError("Must pad internal nodes only.")
97
_BuilderRow.finish_node(self)
100
class _LeafBuilderRow(_BuilderRow):
101
"""The stored state accumulated while writing out a leaf rows."""
104
class BTreeBuilder(index.GraphIndexBuilder):
105
"""A Builder for B+Tree based Graph indices.
107
The resulting graph has the structure:
109
_SIGNATURE OPTIONS NODES
110
_SIGNATURE := 'B+Tree Graph Index 1' NEWLINE
111
OPTIONS := REF_LISTS KEY_ELEMENTS LENGTH
112
REF_LISTS := 'node_ref_lists=' DIGITS NEWLINE
113
KEY_ELEMENTS := 'key_elements=' DIGITS NEWLINE
114
LENGTH := 'len=' DIGITS NEWLINE
115
ROW_LENGTHS := 'row_lengths' DIGITS (COMMA DIGITS)*
116
NODES := NODE_COMPRESSED*
117
NODE_COMPRESSED:= COMPRESSED_BYTES{4096}
118
NODE_RAW := INTERNAL | LEAF
119
INTERNAL := INTERNAL_FLAG POINTERS
120
LEAF := LEAF_FLAG ROWS
121
KEY_ELEMENT := Not-whitespace-utf8
122
KEY := KEY_ELEMENT (NULL KEY_ELEMENT)*
124
ROW := KEY NULL ABSENT? NULL REFERENCES NULL VALUE NEWLINE
126
REFERENCES := REFERENCE_LIST (TAB REFERENCE_LIST){node_ref_lists - 1}
127
REFERENCE_LIST := (REFERENCE (CR REFERENCE)*)?
129
VALUE := no-newline-no-null-bytes
132
def __init__(self, reference_lists=0, key_elements=1, spill_at=100000):
133
"""See GraphIndexBuilder.__init__.
135
:param spill_at: Optional parameter controlling the maximum number
136
of nodes that BTreeBuilder will hold in memory.
138
index.GraphIndexBuilder.__init__(self, reference_lists=reference_lists,
139
key_elements=key_elements)
140
self._spill_at = spill_at
141
self._backing_indices = []
142
# A map of {key: (node_refs, value)}
144
# Indicate it hasn't been built yet
145
self._nodes_by_key = None
146
self._optimize_for_size = False
148
def add_node(self, key, value, references=()):
149
"""Add a node to the index.
151
If adding the node causes the builder to reach its spill_at threshold,
152
disk spilling will be triggered.
154
:param key: The key. keys are non-empty tuples containing
155
as many whitespace-free utf8 bytestrings as the key length
156
defined for this index.
157
:param references: An iterable of iterables of keys. Each is a
158
reference to another key.
159
:param value: The value to associate with the key. It may be any
160
bytes as long as it does not contain \0 or \n.
162
# we don't care about absent_references
163
node_refs, _ = self._check_key_ref_value(key, references, value)
164
if key in self._nodes:
165
raise errors.BadIndexDuplicateKey(key, self)
167
self._nodes[key] = (node_refs, value)
169
if self._nodes_by_key is not None and self._key_length > 1:
170
self._update_nodes_by_key(key, value, node_refs)
171
if len(self._keys) < self._spill_at:
173
self._spill_mem_keys_to_disk()
175
def _spill_mem_keys_to_disk(self):
176
"""Write the in memory keys down to disk to cap memory consumption.
178
If we already have some keys written to disk, we will combine them so
179
as to preserve the sorted order. The algorithm for combining uses
180
powers of two. So on the first spill, write all mem nodes into a
181
single index. On the second spill, combine the mem nodes with the nodes
182
on disk to create a 2x sized disk index and get rid of the first index.
183
On the third spill, create a single new disk index, which will contain
184
the mem nodes, and preserve the existing 2x sized index. On the fourth,
185
combine mem with the first and second indexes, creating a new one of
186
size 4x. On the fifth create a single new one, etc.
188
if self._combine_backing_indices:
189
(new_backing_file, size,
190
backing_pos) = self._spill_mem_keys_and_combine()
192
new_backing_file, size = self._spill_mem_keys_without_combining()
193
# Note: The transport here isn't strictly needed, because we will use
194
# direct access to the new_backing._file object
195
new_backing = BTreeGraphIndex(get_transport('.'), '<temp>', size)
196
# GC will clean up the file
197
new_backing._file = new_backing_file
198
if self._combine_backing_indices:
199
if len(self._backing_indices) == backing_pos:
200
self._backing_indices.append(None)
201
self._backing_indices[backing_pos] = new_backing
202
for backing_pos in range(backing_pos):
203
self._backing_indices[backing_pos] = None
205
self._backing_indices.append(new_backing)
208
self._nodes_by_key = None
210
def _spill_mem_keys_without_combining(self):
211
return self._write_nodes(self._iter_mem_nodes(), allow_optimize=False)
213
def _spill_mem_keys_and_combine(self):
214
iterators_to_combine = [self._iter_mem_nodes()]
216
for pos, backing in enumerate(self._backing_indices):
220
iterators_to_combine.append(backing.iter_all_entries())
221
backing_pos = pos + 1
222
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
227
def add_nodes(self, nodes):
228
"""Add nodes to the index.
230
:param nodes: An iterable of (key, node_refs, value) entries to add.
232
if self.reference_lists:
233
for (key, value, node_refs) in nodes:
234
self.add_node(key, value, node_refs)
236
for (key, value) in nodes:
237
self.add_node(key, value)
239
def _iter_mem_nodes(self):
240
"""Iterate over the nodes held in memory."""
242
if self.reference_lists:
243
for key in sorted(nodes):
244
references, value = nodes[key]
245
yield self, key, value, references
247
for key in sorted(nodes):
248
references, value = nodes[key]
249
yield self, key, value
251
def _iter_smallest(self, iterators_to_combine):
252
if len(iterators_to_combine) == 1:
253
for value in iterators_to_combine[0]:
257
for iterator in iterators_to_combine:
259
current_values.append(iterator.next())
260
except StopIteration:
261
current_values.append(None)
264
# Decorate candidates with the value to allow 2.4's min to be used.
265
candidates = [(item[1][1], item) for item
266
in enumerate(current_values) if item[1] is not None]
267
if not len(candidates):
269
selected = min(candidates)
270
# undecorate back to (pos, node)
271
selected = selected[1]
272
if last == selected[1][1]:
273
raise errors.BadIndexDuplicateKey(last, self)
274
last = selected[1][1]
275
# Yield, with self as the index
276
yield (self,) + selected[1][1:]
279
current_values[pos] = iterators_to_combine[pos].next()
280
except StopIteration:
281
current_values[pos] = None
283
def _add_key(self, string_key, line, rows, allow_optimize=True):
284
"""Add a key to the current chunk.
286
:param string_key: The key to add.
287
: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
292
if rows[-1].writer is None:
293
# opening a new leaf chunk;
294
for pos, internal_row in enumerate(rows[:-1]):
295
# flesh out any internal nodes that are needed to
296
# preserve the height of the tree
297
if internal_row.writer is None:
299
if internal_row.nodes == 0:
300
length -= _RESERVED_HEADER_BYTES # padded
302
optimize_for_size = self._optimize_for_size
304
optimize_for_size = False
305
internal_row.writer = chunk_writer.ChunkWriter(length, 0,
306
optimize_for_size=optimize_for_size)
307
internal_row.writer.write(_INTERNAL_FLAG)
308
internal_row.writer.write(_INTERNAL_OFFSET +
309
str(rows[pos + 1].nodes) + "\n")
312
if rows[-1].nodes == 0:
313
length -= _RESERVED_HEADER_BYTES # padded
314
rows[-1].writer = chunk_writer.ChunkWriter(length,
315
optimize_for_size=self._optimize_for_size)
316
rows[-1].writer.write(_LEAF_FLAG)
317
if rows[-1].writer.write(line):
318
# this key did not fit in the node:
319
rows[-1].finish_node()
320
key_line = string_key + "\n"
322
for row in reversed(rows[:-1]):
323
# 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
326
if row.writer.write(key_line):
329
# We've found a node that can handle the pointer.
332
# If we reached the current root without being able to mark the
333
# division point, then we need a new root:
336
if 'index' in debug.debug_flags:
337
trace.mutter('Inserting new global row.')
338
new_row = _InternalBuilderRow()
340
rows.insert(0, new_row)
341
# This will be padded, hence the -100
342
new_row.writer = chunk_writer.ChunkWriter(
343
_PAGE_SIZE - _RESERVED_HEADER_BYTES,
345
optimize_for_size=self._optimize_for_size)
346
new_row.writer.write(_INTERNAL_FLAG)
347
new_row.writer.write(_INTERNAL_OFFSET +
348
str(rows[1].nodes - 1) + "\n")
349
new_row.writer.write(key_line)
350
self._add_key(string_key, line, rows, allow_optimize=allow_optimize)
352
def _write_nodes(self, node_iterator, allow_optimize=True):
353
"""Write node_iterator out as a B+Tree.
355
:param node_iterator: An iterator of sorted nodes. Each node should
356
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
360
:return: A file handle for a temporary file containing a B+Tree for
363
# The index rows - rows[0] is the root, rows[1] is the layer under it
366
# forward sorted by key. In future we may consider topological sorting,
367
# at the cost of table scans for direct lookup, or a second index for
370
# A stack with the number of nodes of each size. 0 is the root node
371
# and must always be 1 (if there are any nodes in the tree).
372
self.row_lengths = []
373
# Loop over all nodes adding them to the bottom row
374
# (rows[-1]). When we finish a chunk in a row,
375
# propagate the key that didn't fit (comes after the chunk) to the
376
# row above, transitively.
377
for node in node_iterator:
379
# First key triggers the first row
380
rows.append(_LeafBuilderRow())
382
string_key, line = _btree_serializer._flatten_node(node,
383
self.reference_lists)
384
self._add_key(string_key, line, rows, allow_optimize=allow_optimize)
385
for row in reversed(rows):
386
pad = (type(row) != _LeafBuilderRow)
387
row.finish_node(pad=pad)
388
lines = [_BTSIGNATURE]
389
lines.append(_OPTION_NODE_REFS + str(self.reference_lists) + '\n')
390
lines.append(_OPTION_KEY_ELEMENTS + str(self._key_length) + '\n')
391
lines.append(_OPTION_LEN + str(key_count) + '\n')
392
row_lengths = [row.nodes for row in rows]
393
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-')
397
result = cStringIO.StringIO()
398
result.writelines(lines)
399
position = sum(map(len, lines))
401
if position > _RESERVED_HEADER_BYTES:
402
raise AssertionError("Could not fit the header in the"
403
" reserved space: %d > %d"
404
% (position, _RESERVED_HEADER_BYTES))
405
# write the rows out:
407
reserved = _RESERVED_HEADER_BYTES # reserved space for first node
410
# copy nodes to the finalised file.
411
# Special case the first node as it may be prefixed
412
node = row.spool.read(_PAGE_SIZE)
413
result.write(node[reserved:])
414
result.write("\x00" * (reserved - position))
415
position = 0 # Only the root row actually has an offset
416
copied_len = osutils.pumpfile(row.spool, result)
417
if copied_len != (row.nodes - 1) * _PAGE_SIZE:
418
if type(row) != _LeafBuilderRow:
419
raise AssertionError("Incorrect amount of data copied"
420
" expected: %d, got: %d"
421
% ((row.nodes - 1) * _PAGE_SIZE,
429
"""Finalise the index.
431
:return: A file handle for a temporary file containing the nodes added
434
return self._write_nodes(self.iter_all_entries())[0]
436
def iter_all_entries(self):
437
"""Iterate over all keys within the index
439
:return: An iterable of (index, key, value, reference_lists). There is
440
no defined order for the result iteration - it will be in the most
441
efficient order for the index (in this case dictionary hash order).
443
if 'evil' in debug.debug_flags:
444
trace.mutter_callsite(3,
445
"iter_all_entries scales with size of history.")
446
# Doing serial rather than ordered would be faster; but this shouldn't
447
# be getting called routinely anyway.
448
iterators = [self._iter_mem_nodes()]
449
for backing in self._backing_indices:
450
if backing is not None:
451
iterators.append(backing.iter_all_entries())
452
if len(iterators) == 1:
454
return self._iter_smallest(iterators)
456
def iter_entries(self, keys):
457
"""Iterate over keys within the index.
459
:param keys: An iterable providing the keys to be retrieved.
460
:return: An iterable of (index, key, value, reference_lists). There is no
461
defined order for the result iteration - it will be in the most
462
efficient order for the index (keys iteration order in this case).
465
local_keys = keys.intersection(self._keys)
466
if self.reference_lists:
467
for key in local_keys:
468
node = self._nodes[key]
469
yield self, key, node[1], node[0]
471
for key in local_keys:
472
node = self._nodes[key]
473
yield self, key, node[1]
474
# Find things that are in backing indices that have not been handled
476
if not self._backing_indices:
477
return # We won't find anything there either
478
# Remove all of the keys that we found locally
479
keys.difference_update(local_keys)
480
for backing in self._backing_indices:
485
for node in backing.iter_entries(keys):
487
yield (self,) + node[1:]
489
def iter_entries_prefix(self, keys):
490
"""Iterate over keys within the index using prefix matching.
492
Prefix matching is applied within the tuple of a key, not to within
493
the bytestring of each key element. e.g. if you have the keys ('foo',
494
'bar'), ('foobar', 'gam') and do a prefix search for ('foo', None) then
495
only the former key is returned.
497
:param keys: An iterable providing the key prefixes to be retrieved.
498
Each key prefix takes the form of a tuple the length of a key, but
499
with the last N elements 'None' rather than a regular bytestring.
500
The first element cannot be 'None'.
501
:return: An iterable as per iter_all_entries, but restricted to the
502
keys with a matching prefix to those supplied. No additional keys
503
will be returned, and every match that is in the index will be
506
# XXX: To much duplication with the GraphIndex class; consider finding
507
# a good place to pull out the actual common logic.
511
for backing in self._backing_indices:
514
for node in backing.iter_entries_prefix(keys):
515
yield (self,) + node[1:]
516
if self._key_length == 1:
520
raise errors.BadIndexKey(key)
521
if len(key) != self._key_length:
522
raise errors.BadIndexKey(key)
524
node = self._nodes[key]
527
if self.reference_lists:
528
yield self, key, node[1], node[0]
530
yield self, key, node[1]
535
raise errors.BadIndexKey(key)
536
if len(key) != self._key_length:
537
raise errors.BadIndexKey(key)
538
# find what it refers to:
539
key_dict = self._get_nodes_by_key()
541
# find the subdict to return
543
while len(elements) and elements[0] is not None:
544
key_dict = key_dict[elements[0]]
547
# a non-existant lookup.
552
key_dict = dicts.pop(-1)
553
# can't be empty or would not exist
554
item, value = key_dict.iteritems().next()
555
if type(value) == dict:
557
dicts.extend(key_dict.itervalues())
560
for value in key_dict.itervalues():
561
yield (self, ) + value
563
yield (self, ) + key_dict
565
def _get_nodes_by_key(self):
566
if self._nodes_by_key is None:
568
if self.reference_lists:
569
for key, (references, value) in self._nodes.iteritems():
570
key_dict = nodes_by_key
571
for subkey in key[:-1]:
572
key_dict = key_dict.setdefault(subkey, {})
573
key_dict[key[-1]] = key, value, references
575
for key, (references, value) in self._nodes.iteritems():
576
key_dict = nodes_by_key
577
for subkey in key[:-1]:
578
key_dict = key_dict.setdefault(subkey, {})
579
key_dict[key[-1]] = key, value
580
self._nodes_by_key = nodes_by_key
581
return self._nodes_by_key
584
"""Return an estimate of the number of keys in this index.
586
For InMemoryGraphIndex the estimate is exact.
588
return len(self._keys) + sum(backing.key_count() for backing in
589
self._backing_indices if backing is not None)
592
"""In memory index's have no known corruption at the moment."""
595
class _LeafNode(object):
596
"""A leaf node for a serialised B+Tree index."""
598
__slots__ = ('keys', 'min_key', 'max_key')
600
def __init__(self, bytes, key_length, ref_list_length):
601
"""Parse bytes to create a leaf node object."""
602
# splitlines mangles the \r delimiters.. don't use it.
603
key_list = _btree_serializer._parse_leaf_lines(bytes,
604
key_length, ref_list_length)
606
self.min_key = key_list[0][0]
607
self.max_key = key_list[-1][0]
609
self.min_key = self.max_key = None
610
self.keys = dict(key_list)
613
class _InternalNode(object):
614
"""An internal node for a serialised B+Tree index."""
616
__slots__ = ('keys', 'offset')
618
def __init__(self, bytes):
619
"""Parse bytes to create an internal node object."""
620
# splitlines mangles the \r delimiters.. don't use it.
621
self.keys = self._parse_lines(bytes.split('\n'))
623
def _parse_lines(self, lines):
625
self.offset = int(lines[1][7:])
626
for line in lines[2:]:
629
# TODO: Switch to StaticTuple here.
630
nodes.append(tuple(map(intern, line.split('\0'))))
634
class BTreeGraphIndex(object):
635
"""Access to nodes via the standard GraphIndex interface for B+Tree's.
637
Individual nodes are held in a LRU cache. This holds the root node in
638
memory except when very large walks are done.
641
def __init__(self, transport, name, size, unlimited_cache=False):
642
"""Create a B+Tree index object on the index name.
644
:param transport: The transport to read data for the index from.
645
:param name: The file name of the index on transport.
646
:param size: Optional size of the index in bytes. This allows
647
compatibility with the GraphIndex API, as well as ensuring that
648
the initial read (to read the root node header) can be done
649
without over-reading even on empty indices, and on small indices
650
allows single-IO to read the entire index.
651
:param unlimited_cache: If set to True, then instead of using an
652
LRUCache with size _NODE_CACHE_SIZE, we will use a dict and always
653
cache all leaf nodes.
655
self._transport = transport
659
self._recommended_pages = self._compute_recommended_pages()
660
self._root_node = None
661
# Default max size is 100,000 leave values
662
self._leaf_value_cache = None # lru_cache.LRUCache(100*1000)
664
self._leaf_node_cache = {}
665
self._internal_node_cache = {}
667
self._leaf_node_cache = lru_cache.LRUCache(_NODE_CACHE_SIZE)
668
# We use a FIFO here just to prevent possible blowout. However, a
669
# 300k record btree has only 3k leaf nodes, and only 20 internal
670
# nodes. A value of 100 scales to ~100*100*100 = 1M records.
671
self._internal_node_cache = fifo_cache.FIFOCache(100)
672
self._key_count = None
673
self._row_lengths = None
674
self._row_offsets = None # Start of each row, [-1] is the end
676
def __eq__(self, other):
677
"""Equal when self and other were created with the same parameters."""
679
type(self) == type(other) and
680
self._transport == other._transport and
681
self._name == other._name and
682
self._size == other._size)
684
def __ne__(self, other):
685
return not self.__eq__(other)
687
def _get_and_cache_nodes(self, nodes):
688
"""Read nodes and cache them in the lru.
690
The nodes list supplied is sorted and then read from disk, each node
691
being inserted it into the _node_cache.
693
Note: Asking for more nodes than the _node_cache can contain will
694
result in some of the results being immediately discarded, to prevent
695
this an assertion is raised if more nodes are asked for than are
698
:return: A dict of {node_pos: node}
701
start_of_leaves = None
702
for node_pos, node in self._read_nodes(sorted(nodes)):
703
if node_pos == 0: # Special case
704
self._root_node = node
706
if start_of_leaves is None:
707
start_of_leaves = self._row_offsets[-2]
708
if node_pos < start_of_leaves:
709
self._internal_node_cache[node_pos] = node
711
self._leaf_node_cache[node_pos] = node
712
found[node_pos] = node
715
def _compute_recommended_pages(self):
716
"""Convert transport's recommended_page_size into btree pages.
718
recommended_page_size is in bytes, we want to know how many _PAGE_SIZE
719
pages fit in that length.
721
recommended_read = self._transport.recommended_page_size()
722
recommended_pages = int(math.ceil(recommended_read /
724
return recommended_pages
726
def _compute_total_pages_in_index(self):
727
"""How many pages are in the index.
729
If we have read the header we will use the value stored there.
730
Otherwise it will be computed based on the length of the index.
732
if self._size is None:
733
raise AssertionError('_compute_total_pages_in_index should not be'
734
' called when self._size is None')
735
if self._root_node is not None:
736
# This is the number of pages as defined by the header
737
return self._row_offsets[-1]
738
# This is the number of pages as defined by the size of the index. They
739
# should be indentical.
740
total_pages = int(math.ceil(self._size / float(_PAGE_SIZE)))
743
def _expand_offsets(self, offsets):
744
"""Find extra pages to download.
746
The idea is that we always want to make big-enough requests (like 64kB
747
for http), so that we don't waste round trips. So given the entries
748
that we already have cached and the new pages being downloaded figure
749
out what other pages we might want to read.
751
See also doc/developers/btree_index_prefetch.txt for more details.
753
:param offsets: The offsets to be read
754
:return: A list of offsets to download
756
if 'index' in debug.debug_flags:
757
trace.mutter('expanding: %s\toffsets: %s', self._name, offsets)
759
if len(offsets) >= self._recommended_pages:
760
# Don't add more, we are already requesting more than enough
761
if 'index' in debug.debug_flags:
762
trace.mutter(' not expanding large request (%s >= %s)',
763
len(offsets), self._recommended_pages)
765
if self._size is None:
766
# Don't try anything, because we don't know where the file ends
767
if 'index' in debug.debug_flags:
768
trace.mutter(' not expanding without knowing index size')
770
total_pages = self._compute_total_pages_in_index()
771
cached_offsets = self._get_offsets_to_cached_pages()
772
# If reading recommended_pages would read the rest of the index, just
774
if total_pages - len(cached_offsets) <= self._recommended_pages:
775
# Read whatever is left
777
expanded = [x for x in xrange(total_pages)
778
if x not in cached_offsets]
780
expanded = range(total_pages)
781
if 'index' in debug.debug_flags:
782
trace.mutter(' reading all unread pages: %s', expanded)
785
if self._root_node is None:
786
# ATM on the first read of the root node of a large index, we don't
787
# bother pre-reading any other pages. This is because the
788
# likelyhood of actually reading interesting pages is very low.
789
# See doc/developers/btree_index_prefetch.txt for a discussion, and
790
# a possible implementation when we are guessing that the second
791
# layer index is small
792
final_offsets = offsets
794
tree_depth = len(self._row_lengths)
795
if len(cached_offsets) < tree_depth and len(offsets) == 1:
796
# We haven't read enough to justify expansion
797
# If we are only going to read the root node, and 1 leaf node,
798
# then it isn't worth expanding our request. Once we've read at
799
# least 2 nodes, then we are probably doing a search, and we
800
# start expanding our requests.
801
if 'index' in debug.debug_flags:
802
trace.mutter(' not expanding on first reads')
804
final_offsets = self._expand_to_neighbors(offsets, cached_offsets,
807
final_offsets = sorted(final_offsets)
808
if 'index' in debug.debug_flags:
809
trace.mutter('expanded: %s', final_offsets)
812
def _expand_to_neighbors(self, offsets, cached_offsets, total_pages):
813
"""Expand requests to neighbors until we have enough pages.
815
This is called from _expand_offsets after policy has determined that we
817
We only want to expand requests within a given layer. We cheat a little
818
bit and assume all requests will be in the same layer. This is true
819
given the current design, but if it changes this algorithm may perform
822
:param offsets: requested offsets
823
:param cached_offsets: offsets for pages we currently have cached
824
:return: A set() of offsets after expansion
826
final_offsets = set(offsets)
828
new_tips = set(final_offsets)
829
while len(final_offsets) < self._recommended_pages and new_tips:
833
first, end = self._find_layer_first_and_end(pos)
836
and previous not in cached_offsets
837
and previous not in final_offsets
838
and previous >= first):
839
next_tips.add(previous)
841
if (after < total_pages
842
and after not in cached_offsets
843
and after not in final_offsets
846
# This would keep us from going bigger than
847
# recommended_pages by only expanding the first offsets.
848
# However, if we are making a 'wide' request, it is
849
# reasonable to expand all points equally.
850
# if len(final_offsets) > recommended_pages:
852
final_offsets.update(next_tips)
856
def clear_cache(self):
857
"""Clear out any cached/memoized values.
859
This can be called at any time, but generally it is used when we have
860
extracted some information, but don't expect to be requesting any more
863
# Note that we don't touch self._root_node or self._internal_node_cache
864
# We don't expect either of those to be big, and it can save
865
# round-trips in the future. We may re-evaluate this if InternalNode
866
# memory starts to be an issue.
867
self._leaf_node_cache.clear()
869
def external_references(self, ref_list_num):
870
if self._root_node is None:
871
self._get_root_node()
872
if ref_list_num + 1 > self.node_ref_lists:
873
raise ValueError('No ref list %d, index has %d ref lists'
874
% (ref_list_num, self.node_ref_lists))
877
for node in self.iter_all_entries():
879
refs.update(node[3][ref_list_num])
882
def _find_layer_first_and_end(self, offset):
883
"""Find the start/stop nodes for the layer corresponding to offset.
885
:return: (first, end)
886
first is the first node in this layer
887
end is the first node of the next layer
890
for roffset in self._row_offsets:
897
def _get_offsets_to_cached_pages(self):
898
"""Determine what nodes we already have cached."""
899
cached_offsets = set(self._internal_node_cache.keys())
900
cached_offsets.update(self._leaf_node_cache.keys())
901
if self._root_node is not None:
902
cached_offsets.add(0)
903
return cached_offsets
905
def _get_root_node(self):
906
if self._root_node is None:
907
# We may not have a root node yet
908
self._get_internal_nodes([0])
909
return self._root_node
911
def _get_nodes(self, cache, node_indexes):
914
for idx in node_indexes:
915
if idx == 0 and self._root_node is not None:
916
found[0] = self._root_node
919
found[idx] = cache[idx]
924
needed = self._expand_offsets(needed)
925
found.update(self._get_and_cache_nodes(needed))
928
def _get_internal_nodes(self, node_indexes):
929
"""Get a node, from cache or disk.
931
After getting it, the node will be cached.
933
return self._get_nodes(self._internal_node_cache, node_indexes)
935
def _cache_leaf_values(self, nodes):
936
"""Cache directly from key => value, skipping the btree."""
937
if self._leaf_value_cache is not None:
938
for node in nodes.itervalues():
939
for key, value in node.keys.iteritems():
940
if key in self._leaf_value_cache:
941
# Don't add the rest of the keys, we've seen this node
944
self._leaf_value_cache[key] = value
946
def _get_leaf_nodes(self, node_indexes):
947
"""Get a bunch of nodes, from cache or disk."""
948
found = self._get_nodes(self._leaf_node_cache, node_indexes)
949
self._cache_leaf_values(found)
952
def iter_all_entries(self):
953
"""Iterate over all keys within the index.
955
:return: An iterable of (index, key, value) or (index, key, value, reference_lists).
956
The former tuple is used when there are no reference lists in the
957
index, making the API compatible with simple key:value index types.
958
There is no defined order for the result iteration - it will be in
959
the most efficient order for the index.
961
if 'evil' in debug.debug_flags:
962
trace.mutter_callsite(3,
963
"iter_all_entries scales with size of history.")
964
if not self.key_count():
966
if self._row_offsets[-1] == 1:
967
# There is only the root node, and we read that via key_count()
968
if self.node_ref_lists:
969
for key, (value, refs) in sorted(self._root_node.keys.items()):
970
yield (self, key, value, refs)
972
for key, (value, refs) in sorted(self._root_node.keys.items()):
973
yield (self, key, value)
975
start_of_leaves = self._row_offsets[-2]
976
end_of_leaves = self._row_offsets[-1]
977
needed_offsets = range(start_of_leaves, end_of_leaves)
978
if needed_offsets == [0]:
979
# Special case when we only have a root node, as we have already
981
nodes = [(0, self._root_node)]
983
nodes = self._read_nodes(needed_offsets)
984
# We iterate strictly in-order so that we can use this function
985
# for spilling index builds to disk.
986
if self.node_ref_lists:
987
for _, node in nodes:
988
for key, (value, refs) in sorted(node.keys.items()):
989
yield (self, key, value, refs)
991
for _, node in nodes:
992
for key, (value, refs) in sorted(node.keys.items()):
993
yield (self, key, value)
996
def _multi_bisect_right(in_keys, fixed_keys):
997
"""Find the positions where each 'in_key' would fit in fixed_keys.
999
This is equivalent to doing "bisect_right" on each in_key into
1002
:param in_keys: A sorted list of keys to match with fixed_keys
1003
:param fixed_keys: A sorted list of keys to match against
1004
:return: A list of (integer position, [key list]) tuples.
1009
# no pointers in the fixed_keys list, which means everything must
1011
return [(0, in_keys)]
1013
# TODO: Iterating both lists will generally take M + N steps
1014
# Bisecting each key will generally take M * log2 N steps.
1015
# If we had an efficient way to compare, we could pick the method
1016
# based on which has the fewer number of steps.
1017
# There is also the argument that bisect_right is a compiled
1018
# function, so there is even more to be gained.
1019
# iter_steps = len(in_keys) + len(fixed_keys)
1020
# bisect_steps = len(in_keys) * math.log(len(fixed_keys), 2)
1021
if len(in_keys) == 1: # Bisect will always be faster for M = 1
1022
return [(bisect_right(fixed_keys, in_keys[0]), in_keys)]
1023
# elif bisect_steps < iter_steps:
1025
# for key in in_keys:
1026
# offsets.setdefault(bisect_right(fixed_keys, key),
1028
# return [(o, offsets[o]) for o in sorted(offsets)]
1029
in_keys_iter = iter(in_keys)
1030
fixed_keys_iter = enumerate(fixed_keys)
1031
cur_in_key = in_keys_iter.next()
1032
cur_fixed_offset, cur_fixed_key = fixed_keys_iter.next()
1034
class InputDone(Exception): pass
1035
class FixedDone(Exception): pass
1040
# TODO: Another possibility is that rather than iterating on each side,
1041
# we could use a combination of bisecting and iterating. For
1042
# example, while cur_in_key < fixed_key, bisect to find its
1043
# point, then iterate all matching keys, then bisect (restricted
1044
# to only the remainder) for the next one, etc.
1047
if cur_in_key < cur_fixed_key:
1049
cur_out = (cur_fixed_offset, cur_keys)
1050
output.append(cur_out)
1051
while cur_in_key < cur_fixed_key:
1052
cur_keys.append(cur_in_key)
1054
cur_in_key = in_keys_iter.next()
1055
except StopIteration:
1057
# At this point cur_in_key must be >= cur_fixed_key
1058
# step the cur_fixed_key until we pass the cur key, or walk off
1060
while cur_in_key >= cur_fixed_key:
1062
cur_fixed_offset, cur_fixed_key = fixed_keys_iter.next()
1063
except StopIteration:
1066
# We consumed all of the input, nothing more to do
1069
# There was some input left, but we consumed all of fixed, so we
1070
# have to add one more for the tail
1071
cur_keys = [cur_in_key]
1072
cur_keys.extend(in_keys_iter)
1073
cur_out = (len(fixed_keys), cur_keys)
1074
output.append(cur_out)
1077
def _walk_through_internal_nodes(self, keys):
1078
"""Take the given set of keys, and find the corresponding LeafNodes.
1080
:param keys: An unsorted iterable of keys to search for
1081
:return: (nodes, index_and_keys)
1082
nodes is a dict mapping {index: LeafNode}
1083
keys_at_index is a list of tuples of [(index, [keys for Leaf])]
1085
# 6 seconds spent in miss_torture using the sorted() line.
1086
# Even with out of order disk IO it seems faster not to sort it when
1087
# large queries are being made.
1088
keys_at_index = [(0, sorted(keys))]
1090
for row_pos, next_row_start in enumerate(self._row_offsets[1:-1]):
1091
node_indexes = [idx for idx, s_keys in keys_at_index]
1092
nodes = self._get_internal_nodes(node_indexes)
1094
next_nodes_and_keys = []
1095
for node_index, sub_keys in keys_at_index:
1096
node = nodes[node_index]
1097
positions = self._multi_bisect_right(sub_keys, node.keys)
1098
node_offset = next_row_start + node.offset
1099
next_nodes_and_keys.extend([(node_offset + pos, s_keys)
1100
for pos, s_keys in positions])
1101
keys_at_index = next_nodes_and_keys
1102
# We should now be at the _LeafNodes
1103
node_indexes = [idx for idx, s_keys in keys_at_index]
1105
# TODO: We may *not* want to always read all the nodes in one
1106
# big go. Consider setting a max size on this.
1107
nodes = self._get_leaf_nodes(node_indexes)
1108
return nodes, keys_at_index
1110
def iter_entries(self, keys):
1111
"""Iterate over keys within the index.
1113
:param keys: An iterable providing the keys to be retrieved.
1114
:return: An iterable as per iter_all_entries, but restricted to the
1115
keys supplied. No additional keys will be returned, and every
1116
key supplied that is in the index will be returned.
1118
# 6 seconds spent in miss_torture using the sorted() line.
1119
# Even with out of order disk IO it seems faster not to sort it when
1120
# large queries are being made.
1121
# However, now that we are doing multi-way bisecting, we need the keys
1122
# in sorted order anyway. We could change the multi-way code to not
1123
# require sorted order. (For example, it bisects for the first node,
1124
# does an in-order search until a key comes before the current point,
1125
# which it then bisects for, etc.)
1126
keys = frozenset(keys)
1130
if not self.key_count():
1134
if self._leaf_value_cache is None:
1138
value = self._leaf_value_cache.get(key, None)
1139
if value is not None:
1140
# This key is known not to be here, skip it
1142
if self.node_ref_lists:
1143
yield (self, key, value, refs)
1145
yield (self, key, value)
1147
needed_keys.append(key)
1153
nodes, nodes_and_keys = self._walk_through_internal_nodes(needed_keys)
1154
for node_index, sub_keys in nodes_and_keys:
1157
node = nodes[node_index]
1158
for next_sub_key in sub_keys:
1159
if next_sub_key in node.keys:
1160
value, refs = node.keys[next_sub_key]
1161
if self.node_ref_lists:
1162
yield (self, next_sub_key, value, refs)
1164
yield (self, next_sub_key, value)
1166
def _find_ancestors(self, keys, ref_list_num, parent_map, missing_keys):
1167
"""Find the parent_map information for the set of keys.
1169
This populates the parent_map dict and missing_keys set based on the
1170
queried keys. It also can fill out an arbitrary number of parents that
1171
it finds while searching for the supplied keys.
1173
It is unlikely that you want to call this directly. See
1174
"CombinedGraphIndex.find_ancestry()" for a more appropriate API.
1176
:param keys: A keys whose ancestry we want to return
1177
Every key will either end up in 'parent_map' or 'missing_keys'.
1178
:param ref_list_num: This index in the ref_lists is the parents we
1180
:param parent_map: {key: parent_keys} for keys that are present in this
1181
index. This may contain more entries than were in 'keys', that are
1182
reachable ancestors of the keys requested.
1183
:param missing_keys: keys which are known to be missing in this index.
1184
This may include parents that were not directly requested, but we
1185
were able to determine that they are not present in this index.
1186
:return: search_keys parents that were found but not queried to know
1187
if they are missing or present. Callers can re-query this index for
1188
those keys, and they will be placed into parent_map or missing_keys
1190
if not self.key_count():
1191
# We use key_count() to trigger reading the root node and
1192
# determining info about this BTreeGraphIndex
1193
# If we don't have any keys, then everything is missing
1194
missing_keys.update(keys)
1196
if ref_list_num >= self.node_ref_lists:
1197
raise ValueError('No ref list %d, index has %d ref lists'
1198
% (ref_list_num, self.node_ref_lists))
1200
# The main trick we are trying to accomplish is that when we find a
1201
# key listing its parents, we expect that the parent key is also likely
1202
# to sit on the same page. Allowing us to expand parents quickly
1203
# without suffering the full stack of bisecting, etc.
1204
nodes, nodes_and_keys = self._walk_through_internal_nodes(keys)
1206
# These are parent keys which could not be immediately resolved on the
1207
# page where the child was present. Note that we may already be
1208
# searching for that key, and it may actually be present [or known
1209
# missing] on one of the other pages we are reading.
1211
# We could try searching for them in the immediate previous or next
1212
# page. If they occur "later" we could put them in a pending lookup
1213
# set, and then for each node we read thereafter we could check to
1214
# see if they are present.
1215
# However, we don't know the impact of keeping this list of things
1216
# that I'm going to search for every node I come across from here on
1218
# It doesn't handle the case when the parent key is missing on a
1219
# page that we *don't* read. So we already have to handle being
1220
# re-entrant for that.
1221
# Since most keys contain a date string, they are more likely to be
1222
# found earlier in the file than later, but we would know that right
1223
# away (key < min_key), and wouldn't keep searching it on every other
1224
# page that we read.
1225
# Mostly, it is an idea, one which should be benchmarked.
1226
parents_not_on_page = set()
1228
for node_index, sub_keys in nodes_and_keys:
1231
# sub_keys is all of the keys we are looking for that should exist
1232
# on this page, if they aren't here, then they won't be found
1233
node = nodes[node_index]
1234
node_keys = node.keys
1235
parents_to_check = set()
1236
for next_sub_key in sub_keys:
1237
if next_sub_key not in node_keys:
1238
# This one is just not present in the index at all
1239
missing_keys.add(next_sub_key)
1241
value, refs = node_keys[next_sub_key]
1242
parent_keys = refs[ref_list_num]
1243
parent_map[next_sub_key] = parent_keys
1244
parents_to_check.update(parent_keys)
1245
# Don't look for things we've already found
1246
parents_to_check = parents_to_check.difference(parent_map)
1247
# this can be used to test the benefit of having the check loop
1249
# parents_not_on_page.update(parents_to_check)
1251
while parents_to_check:
1252
next_parents_to_check = set()
1253
for key in parents_to_check:
1254
if key in node_keys:
1255
value, refs = node_keys[key]
1256
parent_keys = refs[ref_list_num]
1257
parent_map[key] = parent_keys
1258
next_parents_to_check.update(parent_keys)
1260
# This parent either is genuinely missing, or should be
1261
# found on another page. Perf test whether it is better
1262
# to check if this node should fit on this page or not.
1263
# in the 'everything-in-one-pack' scenario, this *not*
1264
# doing the check is 237ms vs 243ms.
1265
# So slightly better, but I assume the standard 'lots
1266
# of packs' is going to show a reasonable improvement
1267
# from the check, because it avoids 'going around
1268
# again' for everything that is in another index
1269
# parents_not_on_page.add(key)
1270
# Missing for some reason
1271
if key < node.min_key:
1272
# in the case of bzr.dev, 3.4k/5.3k misses are
1273
# 'earlier' misses (65%)
1274
parents_not_on_page.add(key)
1275
elif key > node.max_key:
1276
# This parent key would be present on a different
1278
parents_not_on_page.add(key)
1280
# assert key != node.min_key and key != node.max_key
1281
# If it was going to be present, it would be on
1282
# *this* page, so mark it missing.
1283
missing_keys.add(key)
1284
parents_to_check = next_parents_to_check.difference(parent_map)
1285
# Might want to do another .difference() from missing_keys
1286
# parents_not_on_page could have been found on a different page, or be
1287
# known to be missing. So cull out everything that has already been
1289
search_keys = parents_not_on_page.difference(
1290
parent_map).difference(missing_keys)
1293
def iter_entries_prefix(self, keys):
1294
"""Iterate over keys within the index using prefix matching.
1296
Prefix matching is applied within the tuple of a key, not to within
1297
the bytestring of each key element. e.g. if you have the keys ('foo',
1298
'bar'), ('foobar', 'gam') and do a prefix search for ('foo', None) then
1299
only the former key is returned.
1301
WARNING: Note that this method currently causes a full index parse
1302
unconditionally (which is reasonably appropriate as it is a means for
1303
thunking many small indices into one larger one and still supplies
1304
iter_all_entries at the thunk layer).
1306
:param keys: An iterable providing the key prefixes to be retrieved.
1307
Each key prefix takes the form of a tuple the length of a key, but
1308
with the last N elements 'None' rather than a regular bytestring.
1309
The first element cannot be 'None'.
1310
:return: An iterable as per iter_all_entries, but restricted to the
1311
keys with a matching prefix to those supplied. No additional keys
1312
will be returned, and every match that is in the index will be
1315
keys = sorted(set(keys))
1318
# Load if needed to check key lengths
1319
if self._key_count is None:
1320
self._get_root_node()
1321
# TODO: only access nodes that can satisfy the prefixes we are looking
1322
# for. For now, to meet API usage (as this function is not used by
1323
# current bzrlib) just suck the entire index and iterate in memory.
1325
if self.node_ref_lists:
1326
if self._key_length == 1:
1327
for _1, key, value, refs in self.iter_all_entries():
1328
nodes[key] = value, refs
1331
for _1, key, value, refs in self.iter_all_entries():
1332
key_value = key, value, refs
1333
# For a key of (foo, bar, baz) create
1334
# _nodes_by_key[foo][bar][baz] = key_value
1335
key_dict = nodes_by_key
1336
for subkey in key[:-1]:
1337
key_dict = key_dict.setdefault(subkey, {})
1338
key_dict[key[-1]] = key_value
1340
if self._key_length == 1:
1341
for _1, key, value in self.iter_all_entries():
1345
for _1, key, value in self.iter_all_entries():
1346
key_value = key, value
1347
# For a key of (foo, bar, baz) create
1348
# _nodes_by_key[foo][bar][baz] = key_value
1349
key_dict = nodes_by_key
1350
for subkey in key[:-1]:
1351
key_dict = key_dict.setdefault(subkey, {})
1352
key_dict[key[-1]] = key_value
1353
if self._key_length == 1:
1357
raise errors.BadIndexKey(key)
1358
if len(key) != self._key_length:
1359
raise errors.BadIndexKey(key)
1361
if self.node_ref_lists:
1362
value, node_refs = nodes[key]
1363
yield self, key, value, node_refs
1365
yield self, key, nodes[key]
1372
raise errors.BadIndexKey(key)
1373
if len(key) != self._key_length:
1374
raise errors.BadIndexKey(key)
1375
# find what it refers to:
1376
key_dict = nodes_by_key
1377
elements = list(key)
1378
# find the subdict whose contents should be returned.
1380
while len(elements) and elements[0] is not None:
1381
key_dict = key_dict[elements[0]]
1384
# a non-existant lookup.
1389
key_dict = dicts.pop(-1)
1390
# can't be empty or would not exist
1391
item, value = key_dict.iteritems().next()
1392
if type(value) == dict:
1394
dicts.extend(key_dict.itervalues())
1397
for value in key_dict.itervalues():
1398
# each value is the key:value:node refs tuple
1400
yield (self, ) + value
1402
# the last thing looked up was a terminal element
1403
yield (self, ) + key_dict
1405
def key_count(self):
1406
"""Return an estimate of the number of keys in this index.
1408
For BTreeGraphIndex the estimate is exact as it is contained in the
1411
if self._key_count is None:
1412
self._get_root_node()
1413
return self._key_count
1415
def _compute_row_offsets(self):
1416
"""Fill out the _row_offsets attribute based on _row_lengths."""
1419
for row in self._row_lengths:
1420
offsets.append(row_offset)
1422
offsets.append(row_offset)
1423
self._row_offsets = offsets
1425
def _parse_header_from_bytes(self, bytes):
1426
"""Parse the header from a region of bytes.
1428
:param bytes: The data to parse.
1429
:return: An offset, data tuple such as readv yields, for the unparsed
1430
data. (which may be of length 0).
1432
signature = bytes[0:len(self._signature())]
1433
if not signature == self._signature():
1434
raise errors.BadIndexFormatSignature(self._name, BTreeGraphIndex)
1435
lines = bytes[len(self._signature()):].splitlines()
1436
options_line = lines[0]
1437
if not options_line.startswith(_OPTION_NODE_REFS):
1438
raise errors.BadIndexOptions(self)
1440
self.node_ref_lists = int(options_line[len(_OPTION_NODE_REFS):])
1442
raise errors.BadIndexOptions(self)
1443
options_line = lines[1]
1444
if not options_line.startswith(_OPTION_KEY_ELEMENTS):
1445
raise errors.BadIndexOptions(self)
1447
self._key_length = int(options_line[len(_OPTION_KEY_ELEMENTS):])
1449
raise errors.BadIndexOptions(self)
1450
options_line = lines[2]
1451
if not options_line.startswith(_OPTION_LEN):
1452
raise errors.BadIndexOptions(self)
1454
self._key_count = int(options_line[len(_OPTION_LEN):])
1456
raise errors.BadIndexOptions(self)
1457
options_line = lines[3]
1458
if not options_line.startswith(_OPTION_ROW_LENGTHS):
1459
raise errors.BadIndexOptions(self)
1461
self._row_lengths = map(int, [length for length in
1462
options_line[len(_OPTION_ROW_LENGTHS):].split(',')
1465
raise errors.BadIndexOptions(self)
1466
self._compute_row_offsets()
1468
# calculate the bytes we have processed
1469
header_end = (len(signature) + sum(map(len, lines[0:4])) + 4)
1470
return header_end, bytes[header_end:]
1472
def _read_nodes(self, nodes):
1473
"""Read some nodes from disk into the LRU cache.
1475
This performs a readv to get the node data into memory, and parses each
1476
node, then yields it to the caller. The nodes are requested in the
1477
supplied order. If possible doing sort() on the list before requesting
1478
a read may improve performance.
1480
:param nodes: The nodes to read. 0 - first node, 1 - second node etc.
1483
# may be the byte string of the whole file
1485
# list of (offset, length) regions of the file that should, evenually
1486
# be read in to data_ranges, either from 'bytes' or from the transport
1489
offset = index * _PAGE_SIZE
1492
# Root node - special case
1494
size = min(_PAGE_SIZE, self._size)
1496
# The only case where we don't know the size, is for very
1497
# small indexes. So we read the whole thing
1498
bytes = self._transport.get_bytes(self._name)
1499
self._size = len(bytes)
1500
# the whole thing should be parsed out of 'bytes'
1501
ranges.append((0, len(bytes)))
1504
if offset > self._size:
1505
raise AssertionError('tried to read past the end'
1506
' of the file %s > %s'
1507
% (offset, self._size))
1508
size = min(size, self._size - offset)
1509
ranges.append((offset, size))
1512
elif bytes is not None:
1513
# already have the whole file
1514
data_ranges = [(start, bytes[start:start+_PAGE_SIZE])
1515
for start in xrange(0, len(bytes), _PAGE_SIZE)]
1516
elif self._file is None:
1517
data_ranges = self._transport.readv(self._name, ranges)
1520
for offset, size in ranges:
1521
self._file.seek(offset)
1522
data_ranges.append((offset, self._file.read(size)))
1523
for offset, data in data_ranges:
1525
# extract the header
1526
offset, data = self._parse_header_from_bytes(data)
1529
bytes = zlib.decompress(data)
1530
if bytes.startswith(_LEAF_FLAG):
1531
node = _LeafNode(bytes, self._key_length, self.node_ref_lists)
1532
elif bytes.startswith(_INTERNAL_FLAG):
1533
node = _InternalNode(bytes)
1535
raise AssertionError("Unknown node type for %r" % bytes)
1536
yield offset / _PAGE_SIZE, node
1538
def _signature(self):
1539
"""The file signature for this index type."""
1543
"""Validate that everything in the index can be accessed."""
1544
# just read and parse every node.
1545
self._get_root_node()
1546
if len(self._row_lengths) > 1:
1547
start_node = self._row_offsets[1]
1549
# We shouldn't be reading anything anyway
1551
node_end = self._row_offsets[-1]
1552
for node in self._read_nodes(range(start_node, node_end)):
1557
from bzrlib import _btree_serializer_pyx as _btree_serializer
1558
except ImportError, e:
1559
osutils.failed_to_load_extension(e)
1560
from bzrlib import _btree_serializer_py as _btree_serializer
added
removed
bzrlib/btree_index.py
