1
# Copyright (C) 2008, 2009, 2010 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
38
from bzrlib.index import _OPTION_NODE_REFS, _OPTION_KEY_ELEMENTS, _OPTION_LEN
41
_BTSIGNATURE = "B+Tree Graph Index 2\n"
42
_OPTION_ROW_LENGTHS = "row_lengths="
43
_LEAF_FLAG = "type=leaf\n"
44
_INTERNAL_FLAG = "type=internal\n"
45
_INTERNAL_OFFSET = "offset="
47
_RESERVED_HEADER_BYTES = 120
50
# 4K per page: 4MB - 1000 entries
51
_NODE_CACHE_SIZE = 1000
54
class _BuilderRow(object):
55
"""The stored state accumulated while writing out a row in the index.
57
:ivar spool: A temporary file used to accumulate nodes for this row
59
:ivar nodes: The count of nodes emitted so far.
63
"""Create a _BuilderRow."""
65
self.spool = None# tempfile.TemporaryFile(prefix='bzr-index-row-')
68
def finish_node(self, pad=True):
69
byte_lines, _, padding = self.writer.finish()
71
self.spool = cStringIO.StringIO()
73
self.spool.write("\x00" * _RESERVED_HEADER_BYTES)
75
# We got bigger than 1 node, switch to a temp file
76
spool = tempfile.TemporaryFile(prefix='bzr-index-row-')
77
spool.write(self.spool.getvalue())
80
if not pad and padding:
82
skipped_bytes = padding
83
self.spool.writelines(byte_lines)
84
remainder = (self.spool.tell() + skipped_bytes) % _PAGE_SIZE
86
raise AssertionError("incorrect node length: %d, %d"
87
% (self.spool.tell(), remainder))
92
class _InternalBuilderRow(_BuilderRow):
93
"""The stored state accumulated while writing out internal rows."""
95
def finish_node(self, pad=True):
97
raise AssertionError("Must pad internal nodes only.")
98
_BuilderRow.finish_node(self)
101
class _LeafBuilderRow(_BuilderRow):
102
"""The stored state accumulated while writing out a leaf rows."""
105
class BTreeBuilder(index.GraphIndexBuilder):
106
"""A Builder for B+Tree based Graph indices.
108
The resulting graph has the structure:
110
_SIGNATURE OPTIONS NODES
111
_SIGNATURE := 'B+Tree Graph Index 1' NEWLINE
112
OPTIONS := REF_LISTS KEY_ELEMENTS LENGTH
113
REF_LISTS := 'node_ref_lists=' DIGITS NEWLINE
114
KEY_ELEMENTS := 'key_elements=' DIGITS NEWLINE
115
LENGTH := 'len=' DIGITS NEWLINE
116
ROW_LENGTHS := 'row_lengths' DIGITS (COMMA DIGITS)*
117
NODES := NODE_COMPRESSED*
118
NODE_COMPRESSED:= COMPRESSED_BYTES{4096}
119
NODE_RAW := INTERNAL | LEAF
120
INTERNAL := INTERNAL_FLAG POINTERS
121
LEAF := LEAF_FLAG ROWS
122
KEY_ELEMENT := Not-whitespace-utf8
123
KEY := KEY_ELEMENT (NULL KEY_ELEMENT)*
125
ROW := KEY NULL ABSENT? NULL REFERENCES NULL VALUE NEWLINE
127
REFERENCES := REFERENCE_LIST (TAB REFERENCE_LIST){node_ref_lists - 1}
128
REFERENCE_LIST := (REFERENCE (CR REFERENCE)*)?
130
VALUE := no-newline-no-null-bytes
133
def __init__(self, reference_lists=0, key_elements=1, spill_at=100000):
134
"""See GraphIndexBuilder.__init__.
136
:param spill_at: Optional parameter controlling the maximum number
137
of nodes that BTreeBuilder will hold in memory.
139
index.GraphIndexBuilder.__init__(self, reference_lists=reference_lists,
140
key_elements=key_elements)
141
self._spill_at = spill_at
142
self._backing_indices = []
143
# A map of {key: (node_refs, value)}
145
# Indicate it hasn't been built yet
146
self._nodes_by_key = None
147
self._optimize_for_size = False
149
def add_node(self, key, value, references=()):
150
"""Add a node to the index.
152
If adding the node causes the builder to reach its spill_at threshold,
153
disk spilling will be triggered.
155
:param key: The key. keys are non-empty tuples containing
156
as many whitespace-free utf8 bytestrings as the key length
157
defined for this index.
158
:param references: An iterable of iterables of keys. Each is a
159
reference to another key.
160
:param value: The value to associate with the key. It may be any
161
bytes as long as it does not contain \0 or \n.
163
# Ensure that 'key' is a StaticTuple
164
key = static_tuple.StaticTuple.from_sequence(key).intern()
165
# we don't care about absent_references
166
node_refs, _ = self._check_key_ref_value(key, references, value)
167
if key in self._nodes:
168
raise errors.BadIndexDuplicateKey(key, self)
169
self._nodes[key] = static_tuple.StaticTuple(node_refs, value)
170
if self._nodes_by_key is not None and self._key_length > 1:
171
self._update_nodes_by_key(key, value, node_refs)
172
if len(self._nodes) < self._spill_at:
174
self._spill_mem_keys_to_disk()
176
def _spill_mem_keys_to_disk(self):
177
"""Write the in memory keys down to disk to cap memory consumption.
179
If we already have some keys written to disk, we will combine them so
180
as to preserve the sorted order. The algorithm for combining uses
181
powers of two. So on the first spill, write all mem nodes into a
182
single index. On the second spill, combine the mem nodes with the nodes
183
on disk to create a 2x sized disk index and get rid of the first index.
184
On the third spill, create a single new disk index, which will contain
185
the mem nodes, and preserve the existing 2x sized index. On the fourth,
186
combine mem with the first and second indexes, creating a new one of
187
size 4x. On the fifth create a single new one, etc.
189
if self._combine_backing_indices:
190
(new_backing_file, size,
191
backing_pos) = self._spill_mem_keys_and_combine()
193
new_backing_file, size = self._spill_mem_keys_without_combining()
194
# Note: The transport here isn't strictly needed, because we will use
195
# direct access to the new_backing._file object
196
new_backing = BTreeGraphIndex(transport.get_transport('.'),
198
# GC will clean up the file
199
new_backing._file = new_backing_file
200
if self._combine_backing_indices:
201
if len(self._backing_indices) == backing_pos:
202
self._backing_indices.append(None)
203
self._backing_indices[backing_pos] = new_backing
204
for backing_pos in range(backing_pos):
205
self._backing_indices[backing_pos] = None
207
self._backing_indices.append(new_backing)
209
self._nodes_by_key = None
211
def _spill_mem_keys_without_combining(self):
212
return self._write_nodes(self._iter_mem_nodes(), allow_optimize=False)
214
def _spill_mem_keys_and_combine(self):
215
iterators_to_combine = [self._iter_mem_nodes()]
217
for pos, backing in enumerate(self._backing_indices):
221
iterators_to_combine.append(backing.iter_all_entries())
222
backing_pos = pos + 1
223
new_backing_file, size = \
224
self._write_nodes(self._iter_smallest(iterators_to_combine),
225
allow_optimize=False)
226
return new_backing_file, size, backing_pos
228
def add_nodes(self, nodes):
229
"""Add nodes to the index.
231
:param nodes: An iterable of (key, node_refs, value) entries to add.
233
if self.reference_lists:
234
for (key, value, node_refs) in nodes:
235
self.add_node(key, value, node_refs)
237
for (key, value) in nodes:
238
self.add_node(key, value)
240
def _iter_mem_nodes(self):
241
"""Iterate over the nodes held in memory."""
243
if self.reference_lists:
244
for key in sorted(nodes):
245
references, value = nodes[key]
246
yield self, key, value, references
248
for key in sorted(nodes):
249
references, value = nodes[key]
250
yield self, key, value
252
def _iter_smallest(self, iterators_to_combine):
253
if len(iterators_to_combine) == 1:
254
for value in iterators_to_combine[0]:
258
for iterator in iterators_to_combine:
260
current_values.append(iterator.next())
261
except StopIteration:
262
current_values.append(None)
265
# Decorate candidates with the value to allow 2.4's min to be used.
266
candidates = [(item[1][1], item) for item
267
in enumerate(current_values) if item[1] is not None]
268
if not len(candidates):
270
selected = min(candidates)
271
# undecorate back to (pos, node)
272
selected = selected[1]
273
if last == selected[1][1]:
274
raise errors.BadIndexDuplicateKey(last, self)
275
last = selected[1][1]
276
# Yield, with self as the index
277
yield (self,) + selected[1][1:]
280
current_values[pos] = iterators_to_combine[pos].next()
281
except StopIteration:
282
current_values[pos] = None
284
def _add_key(self, string_key, line, rows, allow_optimize=True):
285
"""Add a key to the current chunk.
287
:param string_key: The key to add.
288
:param line: The fully serialised key and value.
289
:param allow_optimize: If set to False, prevent setting the optimize
290
flag when writing out. This is used by the _spill_mem_keys_to_disk
293
if rows[-1].writer is None:
294
# opening a new leaf chunk;
295
for pos, internal_row in enumerate(rows[:-1]):
296
# flesh out any internal nodes that are needed to
297
# preserve the height of the tree
298
if internal_row.writer is None:
300
if internal_row.nodes == 0:
301
length -= _RESERVED_HEADER_BYTES # padded
303
optimize_for_size = self._optimize_for_size
305
optimize_for_size = False
306
internal_row.writer = chunk_writer.ChunkWriter(length, 0,
307
optimize_for_size=optimize_for_size)
308
internal_row.writer.write(_INTERNAL_FLAG)
309
internal_row.writer.write(_INTERNAL_OFFSET +
310
str(rows[pos + 1].nodes) + "\n")
313
if rows[-1].nodes == 0:
314
length -= _RESERVED_HEADER_BYTES # padded
315
rows[-1].writer = chunk_writer.ChunkWriter(length,
316
optimize_for_size=self._optimize_for_size)
317
rows[-1].writer.write(_LEAF_FLAG)
318
if rows[-1].writer.write(line):
319
# this key did not fit in the node:
320
rows[-1].finish_node()
321
key_line = string_key + "\n"
323
for row in reversed(rows[:-1]):
324
# Mark the start of the next node in the node above. If it
325
# doesn't fit then propagate upwards until we find one that
327
if row.writer.write(key_line):
330
# We've found a node that can handle the pointer.
333
# If we reached the current root without being able to mark the
334
# division point, then we need a new root:
337
if 'index' in debug.debug_flags:
338
trace.mutter('Inserting new global row.')
339
new_row = _InternalBuilderRow()
341
rows.insert(0, new_row)
342
# This will be padded, hence the -100
343
new_row.writer = chunk_writer.ChunkWriter(
344
_PAGE_SIZE - _RESERVED_HEADER_BYTES,
346
optimize_for_size=self._optimize_for_size)
347
new_row.writer.write(_INTERNAL_FLAG)
348
new_row.writer.write(_INTERNAL_OFFSET +
349
str(rows[1].nodes - 1) + "\n")
350
new_row.writer.write(key_line)
351
self._add_key(string_key, line, rows, allow_optimize=allow_optimize)
353
def _write_nodes(self, node_iterator, allow_optimize=True):
354
"""Write node_iterator out as a B+Tree.
356
:param node_iterator: An iterator of sorted nodes. Each node should
357
match the output given by iter_all_entries.
358
:param allow_optimize: If set to False, prevent setting the optimize
359
flag when writing out. This is used by the _spill_mem_keys_to_disk
361
:return: A file handle for a temporary file containing a B+Tree for
364
# The index rows - rows[0] is the root, rows[1] is the layer under it
367
# forward sorted by key. In future we may consider topological sorting,
368
# at the cost of table scans for direct lookup, or a second index for
371
# A stack with the number of nodes of each size. 0 is the root node
372
# and must always be 1 (if there are any nodes in the tree).
373
self.row_lengths = []
374
# Loop over all nodes adding them to the bottom row
375
# (rows[-1]). When we finish a chunk in a row,
376
# propagate the key that didn't fit (comes after the chunk) to the
377
# row above, transitively.
378
for node in node_iterator:
380
# First key triggers the first row
381
rows.append(_LeafBuilderRow())
383
string_key, line = _btree_serializer._flatten_node(node,
384
self.reference_lists)
385
self._add_key(string_key, line, rows, allow_optimize=allow_optimize)
386
for row in reversed(rows):
387
pad = (type(row) != _LeafBuilderRow)
388
row.finish_node(pad=pad)
389
lines = [_BTSIGNATURE]
390
lines.append(_OPTION_NODE_REFS + str(self.reference_lists) + '\n')
391
lines.append(_OPTION_KEY_ELEMENTS + str(self._key_length) + '\n')
392
lines.append(_OPTION_LEN + str(key_count) + '\n')
393
row_lengths = [row.nodes for row in rows]
394
lines.append(_OPTION_ROW_LENGTHS + ','.join(map(str, row_lengths)) + '\n')
395
if row_lengths and row_lengths[-1] > 1:
396
result = tempfile.NamedTemporaryFile(prefix='bzr-index-')
398
result = cStringIO.StringIO()
399
result.writelines(lines)
400
position = sum(map(len, lines))
402
if position > _RESERVED_HEADER_BYTES:
403
raise AssertionError("Could not fit the header in the"
404
" reserved space: %d > %d"
405
% (position, _RESERVED_HEADER_BYTES))
406
# write the rows out:
408
reserved = _RESERVED_HEADER_BYTES # reserved space for first node
411
# copy nodes to the finalised file.
412
# Special case the first node as it may be prefixed
413
node = row.spool.read(_PAGE_SIZE)
414
result.write(node[reserved:])
415
if len(node) == _PAGE_SIZE:
416
result.write("\x00" * (reserved - position))
417
position = 0 # Only the root row actually has an offset
418
copied_len = osutils.pumpfile(row.spool, result)
419
if copied_len != (row.nodes - 1) * _PAGE_SIZE:
420
if type(row) != _LeafBuilderRow:
421
raise AssertionError("Incorrect amount of data copied"
422
" expected: %d, got: %d"
423
% ((row.nodes - 1) * _PAGE_SIZE,
431
"""Finalise the index.
433
:return: A file handle for a temporary file containing the nodes added
436
return self._write_nodes(self.iter_all_entries())[0]
438
def iter_all_entries(self):
439
"""Iterate over all keys within the index
441
:return: An iterable of (index, key, value, reference_lists). There is
442
no defined order for the result iteration - it will be in the most
443
efficient order for the index (in this case dictionary hash order).
445
if 'evil' in debug.debug_flags:
446
trace.mutter_callsite(3,
447
"iter_all_entries scales with size of history.")
448
# Doing serial rather than ordered would be faster; but this shouldn't
449
# be getting called routinely anyway.
450
iterators = [self._iter_mem_nodes()]
451
for backing in self._backing_indices:
452
if backing is not None:
453
iterators.append(backing.iter_all_entries())
454
if len(iterators) == 1:
456
return self._iter_smallest(iterators)
458
def iter_entries(self, keys):
459
"""Iterate over keys within the index.
461
:param keys: An iterable providing the keys to be retrieved.
462
:return: An iterable of (index, key, value, reference_lists). There is no
463
defined order for the result iteration - it will be in the most
464
efficient order for the index (keys iteration order in this case).
467
# Note: We don't use keys.intersection() here. If you read the C api,
468
# set.intersection(other) special cases when other is a set and
469
# will iterate the smaller of the two and lookup in the other.
470
# It does *not* do this for any other type (even dict, unlike
471
# some other set functions.) Since we expect keys is generally <<
472
# self._nodes, it is faster to iterate over it in a list
475
local_keys = [key for key in keys if key in nodes]
476
if self.reference_lists:
477
for key in local_keys:
479
yield self, key, node[1], node[0]
481
for key in local_keys:
483
yield self, key, node[1]
484
# Find things that are in backing indices that have not been handled
486
if not self._backing_indices:
487
return # We won't find anything there either
488
# Remove all of the keys that we found locally
489
keys.difference_update(local_keys)
490
for backing in self._backing_indices:
495
for node in backing.iter_entries(keys):
497
yield (self,) + node[1:]
499
def iter_entries_prefix(self, keys):
500
"""Iterate over keys within the index using prefix matching.
502
Prefix matching is applied within the tuple of a key, not to within
503
the bytestring of each key element. e.g. if you have the keys ('foo',
504
'bar'), ('foobar', 'gam') and do a prefix search for ('foo', None) then
505
only the former key is returned.
507
:param keys: An iterable providing the key prefixes to be retrieved.
508
Each key prefix takes the form of a tuple the length of a key, but
509
with the last N elements 'None' rather than a regular bytestring.
510
The first element cannot be 'None'.
511
:return: An iterable as per iter_all_entries, but restricted to the
512
keys with a matching prefix to those supplied. No additional keys
513
will be returned, and every match that is in the index will be
516
# XXX: To much duplication with the GraphIndex class; consider finding
517
# a good place to pull out the actual common logic.
521
for backing in self._backing_indices:
524
for node in backing.iter_entries_prefix(keys):
525
yield (self,) + node[1:]
526
if self._key_length == 1:
530
raise errors.BadIndexKey(key)
531
if len(key) != self._key_length:
532
raise errors.BadIndexKey(key)
534
node = self._nodes[key]
537
if self.reference_lists:
538
yield self, key, node[1], node[0]
540
yield self, key, node[1]
545
raise errors.BadIndexKey(key)
546
if len(key) != self._key_length:
547
raise errors.BadIndexKey(key)
548
# find what it refers to:
549
key_dict = self._get_nodes_by_key()
551
# find the subdict to return
553
while len(elements) and elements[0] is not None:
554
key_dict = key_dict[elements[0]]
557
# a non-existant lookup.
562
key_dict = dicts.pop(-1)
563
# can't be empty or would not exist
564
item, value = key_dict.iteritems().next()
565
if type(value) == dict:
567
dicts.extend(key_dict.itervalues())
570
for value in key_dict.itervalues():
571
yield (self, ) + tuple(value)
573
yield (self, ) + key_dict
575
def _get_nodes_by_key(self):
576
if self._nodes_by_key is None:
578
if self.reference_lists:
579
for key, (references, value) in self._nodes.iteritems():
580
key_dict = nodes_by_key
581
for subkey in key[:-1]:
582
key_dict = key_dict.setdefault(subkey, {})
583
key_dict[key[-1]] = key, value, references
585
for key, (references, value) in self._nodes.iteritems():
586
key_dict = nodes_by_key
587
for subkey in key[:-1]:
588
key_dict = key_dict.setdefault(subkey, {})
589
key_dict[key[-1]] = key, value
590
self._nodes_by_key = nodes_by_key
591
return self._nodes_by_key
594
"""Return an estimate of the number of keys in this index.
596
For InMemoryGraphIndex the estimate is exact.
598
return len(self._nodes) + sum(backing.key_count() for backing in
599
self._backing_indices if backing is not None)
602
"""In memory index's have no known corruption at the moment."""
605
class _LeafNode(dict):
606
"""A leaf node for a serialised B+Tree index."""
608
__slots__ = ('min_key', 'max_key', '_keys')
610
def __init__(self, bytes, key_length, ref_list_length):
611
"""Parse bytes to create a leaf node object."""
612
# splitlines mangles the \r delimiters.. don't use it.
613
key_list = _btree_serializer._parse_leaf_lines(bytes,
614
key_length, ref_list_length)
616
self.min_key = key_list[0][0]
617
self.max_key = key_list[-1][0]
619
self.min_key = self.max_key = None
620
super(_LeafNode, self).__init__(key_list)
621
self._keys = dict(self)
624
"""Return a sorted list of (key, (value, refs)) items"""
630
"""Return a sorted list of all keys."""
636
class _InternalNode(object):
637
"""An internal node for a serialised B+Tree index."""
639
__slots__ = ('keys', 'offset')
641
def __init__(self, bytes):
642
"""Parse bytes to create an internal node object."""
643
# splitlines mangles the \r delimiters.. don't use it.
644
self.keys = self._parse_lines(bytes.split('\n'))
646
def _parse_lines(self, lines):
648
self.offset = int(lines[1][7:])
649
as_st = static_tuple.StaticTuple.from_sequence
650
for line in lines[2:]:
653
nodes.append(as_st(map(intern, line.split('\0'))).intern())
657
class BTreeGraphIndex(object):
658
"""Access to nodes via the standard GraphIndex interface for B+Tree's.
660
Individual nodes are held in a LRU cache. This holds the root node in
661
memory except when very large walks are done.
664
def __init__(self, transport, name, size, unlimited_cache=False,
666
"""Create a B+Tree index object on the index name.
668
:param transport: The transport to read data for the index from.
669
:param name: The file name of the index on transport.
670
:param size: Optional size of the index in bytes. This allows
671
compatibility with the GraphIndex API, as well as ensuring that
672
the initial read (to read the root node header) can be done
673
without over-reading even on empty indices, and on small indices
674
allows single-IO to read the entire index.
675
:param unlimited_cache: If set to True, then instead of using an
676
LRUCache with size _NODE_CACHE_SIZE, we will use a dict and always
677
cache all leaf nodes.
678
:param offset: The start of the btree index data isn't byte 0 of the
679
file. Instead it starts at some point later.
681
self._transport = transport
685
self._recommended_pages = self._compute_recommended_pages()
686
self._root_node = None
687
self._base_offset = offset
688
self._leaf_factory = _LeafNode
689
# Default max size is 100,000 leave values
690
self._leaf_value_cache = None # lru_cache.LRUCache(100*1000)
692
self._leaf_node_cache = {}
693
self._internal_node_cache = {}
695
self._leaf_node_cache = lru_cache.LRUCache(_NODE_CACHE_SIZE)
696
# We use a FIFO here just to prevent possible blowout. However, a
697
# 300k record btree has only 3k leaf nodes, and only 20 internal
698
# nodes. A value of 100 scales to ~100*100*100 = 1M records.
699
self._internal_node_cache = fifo_cache.FIFOCache(100)
700
self._key_count = None
701
self._row_lengths = None
702
self._row_offsets = None # Start of each row, [-1] is the end
704
def __eq__(self, other):
705
"""Equal when self and other were created with the same parameters."""
707
type(self) == type(other) and
708
self._transport == other._transport and
709
self._name == other._name and
710
self._size == other._size)
712
def __ne__(self, other):
713
return not self.__eq__(other)
715
def _get_and_cache_nodes(self, nodes):
716
"""Read nodes and cache them in the lru.
718
The nodes list supplied is sorted and then read from disk, each node
719
being inserted it into the _node_cache.
721
Note: Asking for more nodes than the _node_cache can contain will
722
result in some of the results being immediately discarded, to prevent
723
this an assertion is raised if more nodes are asked for than are
726
:return: A dict of {node_pos: node}
729
start_of_leaves = None
730
for node_pos, node in self._read_nodes(sorted(nodes)):
731
if node_pos == 0: # Special case
732
self._root_node = node
734
if start_of_leaves is None:
735
start_of_leaves = self._row_offsets[-2]
736
if node_pos < start_of_leaves:
737
self._internal_node_cache[node_pos] = node
739
self._leaf_node_cache[node_pos] = node
740
found[node_pos] = node
743
def _compute_recommended_pages(self):
744
"""Convert transport's recommended_page_size into btree pages.
746
recommended_page_size is in bytes, we want to know how many _PAGE_SIZE
747
pages fit in that length.
749
recommended_read = self._transport.recommended_page_size()
750
recommended_pages = int(math.ceil(recommended_read /
752
return recommended_pages
754
def _compute_total_pages_in_index(self):
755
"""How many pages are in the index.
757
If we have read the header we will use the value stored there.
758
Otherwise it will be computed based on the length of the index.
760
if self._size is None:
761
raise AssertionError('_compute_total_pages_in_index should not be'
762
' called when self._size is None')
763
if self._root_node is not None:
764
# This is the number of pages as defined by the header
765
return self._row_offsets[-1]
766
# This is the number of pages as defined by the size of the index. They
767
# should be indentical.
768
total_pages = int(math.ceil(self._size / float(_PAGE_SIZE)))
771
def _expand_offsets(self, offsets):
772
"""Find extra pages to download.
774
The idea is that we always want to make big-enough requests (like 64kB
775
for http), so that we don't waste round trips. So given the entries
776
that we already have cached and the new pages being downloaded figure
777
out what other pages we might want to read.
779
See also doc/developers/btree_index_prefetch.txt for more details.
781
:param offsets: The offsets to be read
782
:return: A list of offsets to download
784
if 'index' in debug.debug_flags:
785
trace.mutter('expanding: %s\toffsets: %s', self._name, offsets)
787
if len(offsets) >= self._recommended_pages:
788
# Don't add more, we are already requesting more than enough
789
if 'index' in debug.debug_flags:
790
trace.mutter(' not expanding large request (%s >= %s)',
791
len(offsets), self._recommended_pages)
793
if self._size is None:
794
# Don't try anything, because we don't know where the file ends
795
if 'index' in debug.debug_flags:
796
trace.mutter(' not expanding without knowing index size')
798
total_pages = self._compute_total_pages_in_index()
799
cached_offsets = self._get_offsets_to_cached_pages()
800
# If reading recommended_pages would read the rest of the index, just
802
if total_pages - len(cached_offsets) <= self._recommended_pages:
803
# Read whatever is left
805
expanded = [x for x in xrange(total_pages)
806
if x not in cached_offsets]
808
expanded = range(total_pages)
809
if 'index' in debug.debug_flags:
810
trace.mutter(' reading all unread pages: %s', expanded)
813
if self._root_node is None:
814
# ATM on the first read of the root node of a large index, we don't
815
# bother pre-reading any other pages. This is because the
816
# likelyhood of actually reading interesting pages is very low.
817
# See doc/developers/btree_index_prefetch.txt for a discussion, and
818
# a possible implementation when we are guessing that the second
819
# layer index is small
820
final_offsets = offsets
822
tree_depth = len(self._row_lengths)
823
if len(cached_offsets) < tree_depth and len(offsets) == 1:
824
# We haven't read enough to justify expansion
825
# If we are only going to read the root node, and 1 leaf node,
826
# then it isn't worth expanding our request. Once we've read at
827
# least 2 nodes, then we are probably doing a search, and we
828
# start expanding our requests.
829
if 'index' in debug.debug_flags:
830
trace.mutter(' not expanding on first reads')
832
final_offsets = self._expand_to_neighbors(offsets, cached_offsets,
835
final_offsets = sorted(final_offsets)
836
if 'index' in debug.debug_flags:
837
trace.mutter('expanded: %s', final_offsets)
840
def _expand_to_neighbors(self, offsets, cached_offsets, total_pages):
841
"""Expand requests to neighbors until we have enough pages.
843
This is called from _expand_offsets after policy has determined that we
845
We only want to expand requests within a given layer. We cheat a little
846
bit and assume all requests will be in the same layer. This is true
847
given the current design, but if it changes this algorithm may perform
850
:param offsets: requested offsets
851
:param cached_offsets: offsets for pages we currently have cached
852
:return: A set() of offsets after expansion
854
final_offsets = set(offsets)
856
new_tips = set(final_offsets)
857
while len(final_offsets) < self._recommended_pages and new_tips:
861
first, end = self._find_layer_first_and_end(pos)
864
and previous not in cached_offsets
865
and previous not in final_offsets
866
and previous >= first):
867
next_tips.add(previous)
869
if (after < total_pages
870
and after not in cached_offsets
871
and after not in final_offsets
874
# This would keep us from going bigger than
875
# recommended_pages by only expanding the first offsets.
876
# However, if we are making a 'wide' request, it is
877
# reasonable to expand all points equally.
878
# if len(final_offsets) > recommended_pages:
880
final_offsets.update(next_tips)
884
def clear_cache(self):
885
"""Clear out any cached/memoized values.
887
This can be called at any time, but generally it is used when we have
888
extracted some information, but don't expect to be requesting any more
891
# Note that we don't touch self._root_node or self._internal_node_cache
892
# We don't expect either of those to be big, and it can save
893
# round-trips in the future. We may re-evaluate this if InternalNode
894
# memory starts to be an issue.
895
self._leaf_node_cache.clear()
897
def external_references(self, ref_list_num):
898
if self._root_node is None:
899
self._get_root_node()
900
if ref_list_num + 1 > self.node_ref_lists:
901
raise ValueError('No ref list %d, index has %d ref lists'
902
% (ref_list_num, self.node_ref_lists))
905
for node in self.iter_all_entries():
907
refs.update(node[3][ref_list_num])
910
def _find_layer_first_and_end(self, offset):
911
"""Find the start/stop nodes for the layer corresponding to offset.
913
:return: (first, end)
914
first is the first node in this layer
915
end is the first node of the next layer
918
for roffset in self._row_offsets:
925
def _get_offsets_to_cached_pages(self):
926
"""Determine what nodes we already have cached."""
927
cached_offsets = set(self._internal_node_cache.keys())
928
cached_offsets.update(self._leaf_node_cache.keys())
929
if self._root_node is not None:
930
cached_offsets.add(0)
931
return cached_offsets
933
def _get_root_node(self):
934
if self._root_node is None:
935
# We may not have a root node yet
936
self._get_internal_nodes([0])
937
return self._root_node
939
def _get_nodes(self, cache, node_indexes):
942
for idx in node_indexes:
943
if idx == 0 and self._root_node is not None:
944
found[0] = self._root_node
947
found[idx] = cache[idx]
952
needed = self._expand_offsets(needed)
953
found.update(self._get_and_cache_nodes(needed))
956
def _get_internal_nodes(self, node_indexes):
957
"""Get a node, from cache or disk.
959
After getting it, the node will be cached.
961
return self._get_nodes(self._internal_node_cache, node_indexes)
963
def _cache_leaf_values(self, nodes):
964
"""Cache directly from key => value, skipping the btree."""
965
if self._leaf_value_cache is not None:
966
for node in nodes.itervalues():
967
for key, value in node.all_items():
968
if key in self._leaf_value_cache:
969
# Don't add the rest of the keys, we've seen this node
972
self._leaf_value_cache[key] = value
974
def _get_leaf_nodes(self, node_indexes):
975
"""Get a bunch of nodes, from cache or disk."""
976
found = self._get_nodes(self._leaf_node_cache, node_indexes)
977
self._cache_leaf_values(found)
980
def iter_all_entries(self):
981
"""Iterate over all keys within the index.
983
:return: An iterable of (index, key, value) or (index, key, value, reference_lists).
984
The former tuple is used when there are no reference lists in the
985
index, making the API compatible with simple key:value index types.
986
There is no defined order for the result iteration - it will be in
987
the most efficient order for the index.
989
if 'evil' in debug.debug_flags:
990
trace.mutter_callsite(3,
991
"iter_all_entries scales with size of history.")
992
if not self.key_count():
994
if self._row_offsets[-1] == 1:
995
# There is only the root node, and we read that via key_count()
996
if self.node_ref_lists:
997
for key, (value, refs) in self._root_node.all_items():
998
yield (self, key, value, refs)
1000
for key, (value, refs) in self._root_node.all_items():
1001
yield (self, key, value)
1003
start_of_leaves = self._row_offsets[-2]
1004
end_of_leaves = self._row_offsets[-1]
1005
needed_offsets = range(start_of_leaves, end_of_leaves)
1006
if needed_offsets == [0]:
1007
# Special case when we only have a root node, as we have already
1009
nodes = [(0, self._root_node)]
1011
nodes = self._read_nodes(needed_offsets)
1012
# We iterate strictly in-order so that we can use this function
1013
# for spilling index builds to disk.
1014
if self.node_ref_lists:
1015
for _, node in nodes:
1016
for key, (value, refs) in node.all_items():
1017
yield (self, key, value, refs)
1019
for _, node in nodes:
1020
for key, (value, refs) in node.all_items():
1021
yield (self, key, value)
1024
def _multi_bisect_right(in_keys, fixed_keys):
1025
"""Find the positions where each 'in_key' would fit in fixed_keys.
1027
This is equivalent to doing "bisect_right" on each in_key into
1030
:param in_keys: A sorted list of keys to match with fixed_keys
1031
:param fixed_keys: A sorted list of keys to match against
1032
:return: A list of (integer position, [key list]) tuples.
1037
# no pointers in the fixed_keys list, which means everything must
1039
return [(0, in_keys)]
1041
# TODO: Iterating both lists will generally take M + N steps
1042
# Bisecting each key will generally take M * log2 N steps.
1043
# If we had an efficient way to compare, we could pick the method
1044
# based on which has the fewer number of steps.
1045
# There is also the argument that bisect_right is a compiled
1046
# function, so there is even more to be gained.
1047
# iter_steps = len(in_keys) + len(fixed_keys)
1048
# bisect_steps = len(in_keys) * math.log(len(fixed_keys), 2)
1049
if len(in_keys) == 1: # Bisect will always be faster for M = 1
1050
return [(bisect_right(fixed_keys, in_keys[0]), in_keys)]
1051
# elif bisect_steps < iter_steps:
1053
# for key in in_keys:
1054
# offsets.setdefault(bisect_right(fixed_keys, key),
1056
# return [(o, offsets[o]) for o in sorted(offsets)]
1057
in_keys_iter = iter(in_keys)
1058
fixed_keys_iter = enumerate(fixed_keys)
1059
cur_in_key = in_keys_iter.next()
1060
cur_fixed_offset, cur_fixed_key = fixed_keys_iter.next()
1062
class InputDone(Exception): pass
1063
class FixedDone(Exception): pass
1068
# TODO: Another possibility is that rather than iterating on each side,
1069
# we could use a combination of bisecting and iterating. For
1070
# example, while cur_in_key < fixed_key, bisect to find its
1071
# point, then iterate all matching keys, then bisect (restricted
1072
# to only the remainder) for the next one, etc.
1075
if cur_in_key < cur_fixed_key:
1077
cur_out = (cur_fixed_offset, cur_keys)
1078
output.append(cur_out)
1079
while cur_in_key < cur_fixed_key:
1080
cur_keys.append(cur_in_key)
1082
cur_in_key = in_keys_iter.next()
1083
except StopIteration:
1085
# At this point cur_in_key must be >= cur_fixed_key
1086
# step the cur_fixed_key until we pass the cur key, or walk off
1088
while cur_in_key >= cur_fixed_key:
1090
cur_fixed_offset, cur_fixed_key = fixed_keys_iter.next()
1091
except StopIteration:
1094
# We consumed all of the input, nothing more to do
1097
# There was some input left, but we consumed all of fixed, so we
1098
# have to add one more for the tail
1099
cur_keys = [cur_in_key]
1100
cur_keys.extend(in_keys_iter)
1101
cur_out = (len(fixed_keys), cur_keys)
1102
output.append(cur_out)
1105
def _walk_through_internal_nodes(self, keys):
1106
"""Take the given set of keys, and find the corresponding LeafNodes.
1108
:param keys: An unsorted iterable of keys to search for
1109
:return: (nodes, index_and_keys)
1110
nodes is a dict mapping {index: LeafNode}
1111
keys_at_index is a list of tuples of [(index, [keys for Leaf])]
1113
# 6 seconds spent in miss_torture using the sorted() line.
1114
# Even with out of order disk IO it seems faster not to sort it when
1115
# large queries are being made.
1116
keys_at_index = [(0, sorted(keys))]
1118
for row_pos, next_row_start in enumerate(self._row_offsets[1:-1]):
1119
node_indexes = [idx for idx, s_keys in keys_at_index]
1120
nodes = self._get_internal_nodes(node_indexes)
1122
next_nodes_and_keys = []
1123
for node_index, sub_keys in keys_at_index:
1124
node = nodes[node_index]
1125
positions = self._multi_bisect_right(sub_keys, node.keys)
1126
node_offset = next_row_start + node.offset
1127
next_nodes_and_keys.extend([(node_offset + pos, s_keys)
1128
for pos, s_keys in positions])
1129
keys_at_index = next_nodes_and_keys
1130
# We should now be at the _LeafNodes
1131
node_indexes = [idx for idx, s_keys in keys_at_index]
1133
# TODO: We may *not* want to always read all the nodes in one
1134
# big go. Consider setting a max size on this.
1135
nodes = self._get_leaf_nodes(node_indexes)
1136
return nodes, keys_at_index
1138
def iter_entries(self, keys):
1139
"""Iterate over keys within the index.
1141
:param keys: An iterable providing the keys to be retrieved.
1142
:return: An iterable as per iter_all_entries, but restricted to the
1143
keys supplied. No additional keys will be returned, and every
1144
key supplied that is in the index will be returned.
1146
# 6 seconds spent in miss_torture using the sorted() line.
1147
# Even with out of order disk IO it seems faster not to sort it when
1148
# large queries are being made.
1149
# However, now that we are doing multi-way bisecting, we need the keys
1150
# in sorted order anyway. We could change the multi-way code to not
1151
# require sorted order. (For example, it bisects for the first node,
1152
# does an in-order search until a key comes before the current point,
1153
# which it then bisects for, etc.)
1154
keys = frozenset(keys)
1158
if not self.key_count():
1162
if self._leaf_value_cache is None:
1166
value = self._leaf_value_cache.get(key, None)
1167
if value is not None:
1168
# This key is known not to be here, skip it
1170
if self.node_ref_lists:
1171
yield (self, key, value, refs)
1173
yield (self, key, value)
1175
needed_keys.append(key)
1181
nodes, nodes_and_keys = self._walk_through_internal_nodes(needed_keys)
1182
for node_index, sub_keys in nodes_and_keys:
1185
node = nodes[node_index]
1186
for next_sub_key in sub_keys:
1187
if next_sub_key in node:
1188
value, refs = node[next_sub_key]
1189
if self.node_ref_lists:
1190
yield (self, next_sub_key, value, refs)
1192
yield (self, next_sub_key, value)
1194
def _find_ancestors(self, keys, ref_list_num, parent_map, missing_keys):
1195
"""Find the parent_map information for the set of keys.
1197
This populates the parent_map dict and missing_keys set based on the
1198
queried keys. It also can fill out an arbitrary number of parents that
1199
it finds while searching for the supplied keys.
1201
It is unlikely that you want to call this directly. See
1202
"CombinedGraphIndex.find_ancestry()" for a more appropriate API.
1204
:param keys: A keys whose ancestry we want to return
1205
Every key will either end up in 'parent_map' or 'missing_keys'.
1206
:param ref_list_num: This index in the ref_lists is the parents we
1208
:param parent_map: {key: parent_keys} for keys that are present in this
1209
index. This may contain more entries than were in 'keys', that are
1210
reachable ancestors of the keys requested.
1211
:param missing_keys: keys which are known to be missing in this index.
1212
This may include parents that were not directly requested, but we
1213
were able to determine that they are not present in this index.
1214
:return: search_keys parents that were found but not queried to know
1215
if they are missing or present. Callers can re-query this index for
1216
those keys, and they will be placed into parent_map or missing_keys
1218
if not self.key_count():
1219
# We use key_count() to trigger reading the root node and
1220
# determining info about this BTreeGraphIndex
1221
# If we don't have any keys, then everything is missing
1222
missing_keys.update(keys)
1224
if ref_list_num >= self.node_ref_lists:
1225
raise ValueError('No ref list %d, index has %d ref lists'
1226
% (ref_list_num, self.node_ref_lists))
1228
# The main trick we are trying to accomplish is that when we find a
1229
# key listing its parents, we expect that the parent key is also likely
1230
# to sit on the same page. Allowing us to expand parents quickly
1231
# without suffering the full stack of bisecting, etc.
1232
nodes, nodes_and_keys = self._walk_through_internal_nodes(keys)
1234
# These are parent keys which could not be immediately resolved on the
1235
# page where the child was present. Note that we may already be
1236
# searching for that key, and it may actually be present [or known
1237
# missing] on one of the other pages we are reading.
1239
# We could try searching for them in the immediate previous or next
1240
# page. If they occur "later" we could put them in a pending lookup
1241
# set, and then for each node we read thereafter we could check to
1242
# see if they are present.
1243
# However, we don't know the impact of keeping this list of things
1244
# that I'm going to search for every node I come across from here on
1246
# It doesn't handle the case when the parent key is missing on a
1247
# page that we *don't* read. So we already have to handle being
1248
# re-entrant for that.
1249
# Since most keys contain a date string, they are more likely to be
1250
# found earlier in the file than later, but we would know that right
1251
# away (key < min_key), and wouldn't keep searching it on every other
1252
# page that we read.
1253
# Mostly, it is an idea, one which should be benchmarked.
1254
parents_not_on_page = set()
1256
for node_index, sub_keys in nodes_and_keys:
1259
# sub_keys is all of the keys we are looking for that should exist
1260
# on this page, if they aren't here, then they won't be found
1261
node = nodes[node_index]
1262
parents_to_check = set()
1263
for next_sub_key in sub_keys:
1264
if next_sub_key not in node:
1265
# This one is just not present in the index at all
1266
missing_keys.add(next_sub_key)
1268
value, refs = node[next_sub_key]
1269
parent_keys = refs[ref_list_num]
1270
parent_map[next_sub_key] = parent_keys
1271
parents_to_check.update(parent_keys)
1272
# Don't look for things we've already found
1273
parents_to_check = parents_to_check.difference(parent_map)
1274
# this can be used to test the benefit of having the check loop
1276
# parents_not_on_page.update(parents_to_check)
1278
while parents_to_check:
1279
next_parents_to_check = set()
1280
for key in parents_to_check:
1282
value, refs = node[key]
1283
parent_keys = refs[ref_list_num]
1284
parent_map[key] = parent_keys
1285
next_parents_to_check.update(parent_keys)
1287
# This parent either is genuinely missing, or should be
1288
# found on another page. Perf test whether it is better
1289
# to check if this node should fit on this page or not.
1290
# in the 'everything-in-one-pack' scenario, this *not*
1291
# doing the check is 237ms vs 243ms.
1292
# So slightly better, but I assume the standard 'lots
1293
# of packs' is going to show a reasonable improvement
1294
# from the check, because it avoids 'going around
1295
# again' for everything that is in another index
1296
# parents_not_on_page.add(key)
1297
# Missing for some reason
1298
if key < node.min_key:
1299
# in the case of bzr.dev, 3.4k/5.3k misses are
1300
# 'earlier' misses (65%)
1301
parents_not_on_page.add(key)
1302
elif key > node.max_key:
1303
# This parent key would be present on a different
1305
parents_not_on_page.add(key)
1307
# assert key != node.min_key and key != node.max_key
1308
# If it was going to be present, it would be on
1309
# *this* page, so mark it missing.
1310
missing_keys.add(key)
1311
parents_to_check = next_parents_to_check.difference(parent_map)
1312
# Might want to do another .difference() from missing_keys
1313
# parents_not_on_page could have been found on a different page, or be
1314
# known to be missing. So cull out everything that has already been
1316
search_keys = parents_not_on_page.difference(
1317
parent_map).difference(missing_keys)
1320
def iter_entries_prefix(self, keys):
1321
"""Iterate over keys within the index using prefix matching.
1323
Prefix matching is applied within the tuple of a key, not to within
1324
the bytestring of each key element. e.g. if you have the keys ('foo',
1325
'bar'), ('foobar', 'gam') and do a prefix search for ('foo', None) then
1326
only the former key is returned.
1328
WARNING: Note that this method currently causes a full index parse
1329
unconditionally (which is reasonably appropriate as it is a means for
1330
thunking many small indices into one larger one and still supplies
1331
iter_all_entries at the thunk layer).
1333
:param keys: An iterable providing the key prefixes to be retrieved.
1334
Each key prefix takes the form of a tuple the length of a key, but
1335
with the last N elements 'None' rather than a regular bytestring.
1336
The first element cannot be 'None'.
1337
:return: An iterable as per iter_all_entries, but restricted to the
1338
keys with a matching prefix to those supplied. No additional keys
1339
will be returned, and every match that is in the index will be
1342
keys = sorted(set(keys))
1345
# Load if needed to check key lengths
1346
if self._key_count is None:
1347
self._get_root_node()
1348
# TODO: only access nodes that can satisfy the prefixes we are looking
1349
# for. For now, to meet API usage (as this function is not used by
1350
# current bzrlib) just suck the entire index and iterate in memory.
1352
if self.node_ref_lists:
1353
if self._key_length == 1:
1354
for _1, key, value, refs in self.iter_all_entries():
1355
nodes[key] = value, refs
1358
for _1, key, value, refs in self.iter_all_entries():
1359
key_value = key, value, refs
1360
# For a key of (foo, bar, baz) create
1361
# _nodes_by_key[foo][bar][baz] = key_value
1362
key_dict = nodes_by_key
1363
for subkey in key[:-1]:
1364
key_dict = key_dict.setdefault(subkey, {})
1365
key_dict[key[-1]] = key_value
1367
if self._key_length == 1:
1368
for _1, key, value in self.iter_all_entries():
1372
for _1, key, value in self.iter_all_entries():
1373
key_value = key, value
1374
# For a key of (foo, bar, baz) create
1375
# _nodes_by_key[foo][bar][baz] = key_value
1376
key_dict = nodes_by_key
1377
for subkey in key[:-1]:
1378
key_dict = key_dict.setdefault(subkey, {})
1379
key_dict[key[-1]] = key_value
1380
if self._key_length == 1:
1384
raise errors.BadIndexKey(key)
1385
if len(key) != self._key_length:
1386
raise errors.BadIndexKey(key)
1388
if self.node_ref_lists:
1389
value, node_refs = nodes[key]
1390
yield self, key, value, node_refs
1392
yield self, key, nodes[key]
1399
raise errors.BadIndexKey(key)
1400
if len(key) != self._key_length:
1401
raise errors.BadIndexKey(key)
1402
# find what it refers to:
1403
key_dict = nodes_by_key
1404
elements = list(key)
1405
# find the subdict whose contents should be returned.
1407
while len(elements) and elements[0] is not None:
1408
key_dict = key_dict[elements[0]]
1411
# a non-existant lookup.
1416
key_dict = dicts.pop(-1)
1417
# can't be empty or would not exist
1418
item, value = key_dict.iteritems().next()
1419
if type(value) == dict:
1421
dicts.extend(key_dict.itervalues())
1424
for value in key_dict.itervalues():
1425
# each value is the key:value:node refs tuple
1427
yield (self, ) + value
1429
# the last thing looked up was a terminal element
1430
yield (self, ) + key_dict
1432
def key_count(self):
1433
"""Return an estimate of the number of keys in this index.
1435
For BTreeGraphIndex the estimate is exact as it is contained in the
1438
if self._key_count is None:
1439
self._get_root_node()
1440
return self._key_count
1442
def _compute_row_offsets(self):
1443
"""Fill out the _row_offsets attribute based on _row_lengths."""
1446
for row in self._row_lengths:
1447
offsets.append(row_offset)
1449
offsets.append(row_offset)
1450
self._row_offsets = offsets
1452
def _parse_header_from_bytes(self, bytes):
1453
"""Parse the header from a region of bytes.
1455
:param bytes: The data to parse.
1456
:return: An offset, data tuple such as readv yields, for the unparsed
1457
data. (which may be of length 0).
1459
signature = bytes[0:len(self._signature())]
1460
if not signature == self._signature():
1461
raise errors.BadIndexFormatSignature(self._name, BTreeGraphIndex)
1462
lines = bytes[len(self._signature()):].splitlines()
1463
options_line = lines[0]
1464
if not options_line.startswith(_OPTION_NODE_REFS):
1465
raise errors.BadIndexOptions(self)
1467
self.node_ref_lists = int(options_line[len(_OPTION_NODE_REFS):])
1469
raise errors.BadIndexOptions(self)
1470
options_line = lines[1]
1471
if not options_line.startswith(_OPTION_KEY_ELEMENTS):
1472
raise errors.BadIndexOptions(self)
1474
self._key_length = int(options_line[len(_OPTION_KEY_ELEMENTS):])
1476
raise errors.BadIndexOptions(self)
1477
options_line = lines[2]
1478
if not options_line.startswith(_OPTION_LEN):
1479
raise errors.BadIndexOptions(self)
1481
self._key_count = int(options_line[len(_OPTION_LEN):])
1483
raise errors.BadIndexOptions(self)
1484
options_line = lines[3]
1485
if not options_line.startswith(_OPTION_ROW_LENGTHS):
1486
raise errors.BadIndexOptions(self)
1488
self._row_lengths = map(int, [length for length in
1489
options_line[len(_OPTION_ROW_LENGTHS):].split(',')
1492
raise errors.BadIndexOptions(self)
1493
self._compute_row_offsets()
1495
# calculate the bytes we have processed
1496
header_end = (len(signature) + sum(map(len, lines[0:4])) + 4)
1497
return header_end, bytes[header_end:]
1499
def _read_nodes(self, nodes):
1500
"""Read some nodes from disk into the LRU cache.
1502
This performs a readv to get the node data into memory, and parses each
1503
node, then yields it to the caller. The nodes are requested in the
1504
supplied order. If possible doing sort() on the list before requesting
1505
a read may improve performance.
1507
:param nodes: The nodes to read. 0 - first node, 1 - second node etc.
1510
# may be the byte string of the whole file
1512
# list of (offset, length) regions of the file that should, evenually
1513
# be read in to data_ranges, either from 'bytes' or from the transport
1515
base_offset = self._base_offset
1517
offset = (index * _PAGE_SIZE)
1520
# Root node - special case
1522
size = min(_PAGE_SIZE, self._size)
1524
# The only case where we don't know the size, is for very
1525
# small indexes. So we read the whole thing
1526
bytes = self._transport.get_bytes(self._name)
1527
num_bytes = len(bytes)
1528
self._size = num_bytes - base_offset
1529
# the whole thing should be parsed out of 'bytes'
1530
ranges = [(start, min(_PAGE_SIZE, num_bytes - start))
1531
for start in xrange(base_offset, num_bytes, _PAGE_SIZE)]
1534
if offset > self._size:
1535
raise AssertionError('tried to read past the end'
1536
' of the file %s > %s'
1537
% (offset, self._size))
1538
size = min(size, self._size - offset)
1539
ranges.append((base_offset + offset, size))
1542
elif bytes is not None:
1543
# already have the whole file
1544
data_ranges = [(start, bytes[start:start+size])
1545
for start, size in ranges]
1546
elif self._file is None:
1547
data_ranges = self._transport.readv(self._name, ranges)
1550
for offset, size in ranges:
1551
self._file.seek(offset)
1552
data_ranges.append((offset, self._file.read(size)))
1553
for offset, data in data_ranges:
1554
offset -= base_offset
1556
# extract the header
1557
offset, data = self._parse_header_from_bytes(data)
1560
bytes = zlib.decompress(data)
1561
if bytes.startswith(_LEAF_FLAG):
1562
node = self._leaf_factory(bytes, self._key_length,
1563
self.node_ref_lists)
1564
elif bytes.startswith(_INTERNAL_FLAG):
1565
node = _InternalNode(bytes)
1567
raise AssertionError("Unknown node type for %r" % bytes)
1568
yield offset / _PAGE_SIZE, node
1570
def _signature(self):
1571
"""The file signature for this index type."""
1575
"""Validate that everything in the index can be accessed."""
1576
# just read and parse every node.
1577
self._get_root_node()
1578
if len(self._row_lengths) > 1:
1579
start_node = self._row_offsets[1]
1581
# We shouldn't be reading anything anyway
1583
node_end = self._row_offsets[-1]
1584
for node in self._read_nodes(range(start_node, node_end)):
1588
_gcchk_factory = _LeafNode
1591
from bzrlib import _btree_serializer_pyx as _btree_serializer
1592
_gcchk_factory = _btree_serializer._parse_into_chk
1593
except ImportError, e:
1594
osutils.failed_to_load_extension(e)
1595
from bzrlib import _btree_serializer_py as _btree_serializer
added
removed
bzrlib/btree_index.py
