43
from .index import _OPTION_NODE_REFS, _OPTION_KEY_ELEMENTS, _OPTION_LEN
46
_BTSIGNATURE = b"B+Tree Graph Index 2\n"
47
_OPTION_ROW_LENGTHS = b"row_lengths="
48
_LEAF_FLAG = b"type=leaf\n"
49
_INTERNAL_FLAG = b"type=internal\n"
50
_INTERNAL_OFFSET = b"offset="
44
from bzrlib.index import _OPTION_NODE_REFS, _OPTION_KEY_ELEMENTS, _OPTION_LEN
47
_BTSIGNATURE = "B+Tree Graph Index 2\n"
48
_OPTION_ROW_LENGTHS = "row_lengths="
49
_LEAF_FLAG = "type=leaf\n"
50
_INTERNAL_FLAG = "type=internal\n"
51
_INTERNAL_OFFSET = "offset="
52
53
_RESERVED_HEADER_BYTES = 120
67
68
def __init__(self):
68
69
"""Create a _BuilderRow."""
70
self.spool = None # tempfile.TemporaryFile(prefix='bzr-index-row-')
71
self.spool = None# tempfile.TemporaryFile(prefix='bzr-index-row-')
73
74
def finish_node(self, pad=True):
74
75
byte_lines, _, padding = self.writer.finish()
75
76
if self.nodes == 0:
76
self.spool = BytesIO()
77
self.spool = cStringIO.StringIO()
78
self.spool.write(b"\x00" * _RESERVED_HEADER_BYTES)
79
self.spool.write("\x00" * _RESERVED_HEADER_BYTES)
79
80
elif self.nodes == 1:
80
81
# We got bigger than 1 node, switch to a temp file
81
82
spool = tempfile.TemporaryFile(prefix='bzr-index-row-')
142
143
of nodes that BTreeBuilder will hold in memory.
144
145
index.GraphIndexBuilder.__init__(self, reference_lists=reference_lists,
145
key_elements=key_elements)
146
key_elements=key_elements)
146
147
self._spill_at = spill_at
147
148
self._backing_indices = []
148
149
# A map of {key: (node_refs, value)}
170
171
# we don't care about absent_references
171
172
node_refs, _ = self._check_key_ref_value(key, references, value)
172
173
if key in self._nodes:
173
raise index.BadIndexDuplicateKey(key, self)
174
raise errors.BadIndexDuplicateKey(key, self)
174
175
self._nodes[key] = static_tuple.StaticTuple(node_refs, value)
175
176
if self._nodes_by_key is not None and self._key_length > 1:
176
177
self._update_nodes_by_key(key, value, node_refs)
262
263
current_values = []
263
264
for iterator in iterators_to_combine:
265
current_values.append(next(iterator))
266
current_values.append(iterator.next())
266
267
except StopIteration:
267
268
current_values.append(None)
270
271
# Decorate candidates with the value to allow 2.4's min to be used.
271
272
candidates = [(item[1][1], item) for item
272
in enumerate(current_values) if item[1] is not None]
273
in enumerate(current_values) if item[1] is not None]
273
274
if not len(candidates):
275
276
selected = min(candidates)
276
277
# undecorate back to (pos, node)
277
278
selected = selected[1]
278
279
if last == selected[1][1]:
279
raise index.BadIndexDuplicateKey(last, self)
280
raise errors.BadIndexDuplicateKey(last, self)
280
281
last = selected[1][1]
281
282
# Yield, with self as the index
282
283
yield (self,) + selected[1][1:]
283
284
pos = selected[0]
285
current_values[pos] = next(iterators_to_combine[pos])
286
current_values[pos] = iterators_to_combine[pos].next()
286
287
except StopIteration:
287
288
current_values[pos] = None
305
306
if internal_row.writer is None:
306
307
length = _PAGE_SIZE
307
308
if internal_row.nodes == 0:
308
length -= _RESERVED_HEADER_BYTES # padded
309
length -= _RESERVED_HEADER_BYTES # padded
309
310
if allow_optimize:
310
311
optimize_for_size = self._optimize_for_size
312
313
optimize_for_size = False
313
internal_row.writer = chunk_writer.ChunkWriter(
314
length, 0, optimize_for_size=optimize_for_size)
314
internal_row.writer = chunk_writer.ChunkWriter(length, 0,
315
optimize_for_size=optimize_for_size)
315
316
internal_row.writer.write(_INTERNAL_FLAG)
316
internal_row.writer.write(_INTERNAL_OFFSET
317
+ b"%d\n" % rows[pos + 1].nodes)
317
internal_row.writer.write(_INTERNAL_OFFSET +
318
str(rows[pos + 1].nodes) + "\n")
319
320
length = _PAGE_SIZE
320
321
if rows[-1].nodes == 0:
321
length -= _RESERVED_HEADER_BYTES # padded
322
rows[-1].writer = chunk_writer.ChunkWriter(
323
length, optimize_for_size=self._optimize_for_size)
322
length -= _RESERVED_HEADER_BYTES # padded
323
rows[-1].writer = chunk_writer.ChunkWriter(length,
324
optimize_for_size=self._optimize_for_size)
324
325
rows[-1].writer.write(_LEAF_FLAG)
325
326
if rows[-1].writer.write(line):
326
327
# if we failed to write, despite having an empty page to write to,
327
328
# then line is too big. raising the error avoids infinite recursion
328
329
# searching for a suitably large page that will not be found.
330
raise index.BadIndexKey(string_key)
331
raise errors.BadIndexKey(string_key)
331
332
# this key did not fit in the node:
332
333
rows[-1].finish_node()
333
key_line = string_key + b"\n"
334
key_line = string_key + "\n"
335
336
for row in reversed(rows[:-1]):
336
337
# Mark the start of the next node in the node above. If it
358
359
optimize_for_size=self._optimize_for_size)
359
360
new_row.writer.write(_INTERNAL_FLAG)
360
new_row.writer.write(_INTERNAL_OFFSET
361
+ b"%d\n" % (rows[1].nodes - 1))
361
new_row.writer.write(_INTERNAL_OFFSET +
362
str(rows[1].nodes - 1) + "\n")
362
363
new_row.writer.write(key_line)
363
self._add_key(string_key, line, rows,
364
allow_optimize=allow_optimize)
364
self._add_key(string_key, line, rows, allow_optimize=allow_optimize)
366
366
def _write_nodes(self, node_iterator, allow_optimize=True):
367
367
"""Write node_iterator out as a B+Tree.
393
393
# First key triggers the first row
394
394
rows.append(_LeafBuilderRow())
396
string_key, line = _btree_serializer._flatten_node(
397
node, self.reference_lists)
398
self._add_key(string_key, line, rows,
399
allow_optimize=allow_optimize)
396
string_key, line = _btree_serializer._flatten_node(node,
397
self.reference_lists)
398
self._add_key(string_key, line, rows, allow_optimize=allow_optimize)
400
399
for row in reversed(rows):
401
pad = (not isinstance(row, _LeafBuilderRow))
400
pad = (type(row) != _LeafBuilderRow)
402
401
row.finish_node(pad=pad)
403
402
lines = [_BTSIGNATURE]
404
lines.append(b'%s%d\n' % (_OPTION_NODE_REFS, self.reference_lists))
405
lines.append(b'%s%d\n' % (_OPTION_KEY_ELEMENTS, self._key_length))
406
lines.append(b'%s%d\n' % (_OPTION_LEN, key_count))
403
lines.append(_OPTION_NODE_REFS + str(self.reference_lists) + '\n')
404
lines.append(_OPTION_KEY_ELEMENTS + str(self._key_length) + '\n')
405
lines.append(_OPTION_LEN + str(key_count) + '\n')
407
406
row_lengths = [row.nodes for row in rows]
408
lines.append(_OPTION_ROW_LENGTHS + ','.join(
409
map(str, row_lengths)).encode('ascii') + b'\n')
407
lines.append(_OPTION_ROW_LENGTHS + ','.join(map(str, row_lengths)) + '\n')
410
408
if row_lengths and row_lengths[-1] > 1:
411
409
result = tempfile.NamedTemporaryFile(prefix='bzr-index-')
411
result = cStringIO.StringIO()
414
412
result.writelines(lines)
415
413
position = sum(map(len, lines))
416
415
if position > _RESERVED_HEADER_BYTES:
417
416
raise AssertionError("Could not fit the header in the"
418
417
" reserved space: %d > %d"
419
418
% (position, _RESERVED_HEADER_BYTES))
420
419
# write the rows out:
422
reserved = _RESERVED_HEADER_BYTES # reserved space for first node
421
reserved = _RESERVED_HEADER_BYTES # reserved space for first node
423
422
row.spool.flush()
424
423
row.spool.seek(0)
425
424
# copy nodes to the finalised file.
427
426
node = row.spool.read(_PAGE_SIZE)
428
427
result.write(node[reserved:])
429
428
if len(node) == _PAGE_SIZE:
430
result.write(b"\x00" * (reserved - position))
431
position = 0 # Only the root row actually has an offset
429
result.write("\x00" * (reserved - position))
430
position = 0 # Only the root row actually has an offset
432
431
copied_len = osutils.pumpfile(row.spool, result)
433
432
if copied_len != (row.nodes - 1) * _PAGE_SIZE:
434
if not isinstance(row, _LeafBuilderRow):
433
if type(row) != _LeafBuilderRow:
435
434
raise AssertionError("Incorrect amount of data copied"
436
" expected: %d, got: %d"
437
% ((row.nodes - 1) * _PAGE_SIZE,
435
" expected: %d, got: %d"
436
% ((row.nodes - 1) * _PAGE_SIZE,
440
439
size = result.tell()
457
456
efficient order for the index (in this case dictionary hash order).
459
458
if 'evil' in debug.debug_flags:
460
trace.mutter_callsite(
461
3, "iter_all_entries scales with size of history.")
459
trace.mutter_callsite(3,
460
"iter_all_entries scales with size of history.")
462
461
# Doing serial rather than ordered would be faster; but this shouldn't
463
462
# be getting called routinely anyway.
464
463
iterators = [self._iter_mem_nodes()]
473
472
"""Iterate over keys within the index.
475
474
:param keys: An iterable providing the keys to be retrieved.
476
:return: An iterable of (index, key, value, reference_lists). There is
477
no defined order for the result iteration - it will be in the most
475
:return: An iterable of (index, key, value, reference_lists). There is no
476
defined order for the result iteration - it will be in the most
478
477
efficient order for the index (keys iteration order in this case).
498
497
# Find things that are in backing indices that have not been handled
500
499
if not self._backing_indices:
501
return # We won't find anything there either
500
return # We won't find anything there either
502
501
# Remove all of the keys that we found locally
503
502
keys.difference_update(local_keys)
504
503
for backing in self._backing_indices:
537
538
yield (self,) + node[1:]
538
539
if self._key_length == 1:
540
index._sanity_check_key(self, key)
543
raise errors.BadIndexKey(key)
544
if len(key) != self._key_length:
545
raise errors.BadIndexKey(key)
542
547
node = self._nodes[key]
548
553
yield self, key, node[1]
550
nodes_by_key = self._get_nodes_by_key()
551
for entry in index._iter_entries_prefix(self, nodes_by_key, keys):
558
raise errors.BadIndexKey(key)
559
if len(key) != self._key_length:
560
raise errors.BadIndexKey(key)
561
# find what it refers to:
562
key_dict = self._get_nodes_by_key()
564
# find the subdict to return
566
while len(elements) and elements[0] is not None:
567
key_dict = key_dict[elements[0]]
570
# a non-existant lookup.
575
key_dict = dicts.pop(-1)
576
# can't be empty or would not exist
577
item, value = key_dict.iteritems().next()
578
if type(value) == dict:
580
dicts.extend(key_dict.itervalues())
583
for value in key_dict.itervalues():
584
yield (self, ) + tuple(value)
586
yield (self, ) + key_dict
554
588
def _get_nodes_by_key(self):
555
589
if self._nodes_by_key is None:
556
590
nodes_by_key = {}
557
591
if self.reference_lists:
558
for key, (references, value) in self._nodes.items():
592
for key, (references, value) in self._nodes.iteritems():
559
593
key_dict = nodes_by_key
560
594
for subkey in key[:-1]:
561
595
key_dict = key_dict.setdefault(subkey, {})
562
596
key_dict[key[-1]] = key, value, references
564
for key, (references, value) in self._nodes.items():
598
for key, (references, value) in self._nodes.iteritems():
565
599
key_dict = nodes_by_key
566
600
for subkey in key[:-1]:
567
601
key_dict = key_dict.setdefault(subkey, {})
575
609
For InMemoryGraphIndex the estimate is exact.
577
return len(self._nodes) + sum(
579
for backing in self._backing_indices
580
if backing is not None)
611
return len(self._nodes) + sum(backing.key_count() for backing in
612
self._backing_indices if backing is not None)
582
614
def validate(self):
583
615
"""In memory index's have no known corruption at the moment."""
585
def __lt__(self, other):
586
if isinstance(other, type(self)):
587
return self._nodes < other._nodes
588
# Always sort existing indexes before ones that are still being built.
589
if isinstance(other, BTreeGraphIndex):
594
618
class _LeafNode(dict):
595
619
"""A leaf node for a serialised B+Tree index."""
599
623
def __init__(self, bytes, key_length, ref_list_length):
600
624
"""Parse bytes to create a leaf node object."""
601
625
# splitlines mangles the \r delimiters.. don't use it.
602
key_list = _btree_serializer._parse_leaf_lines(
603
bytes, key_length, ref_list_length)
626
key_list = _btree_serializer._parse_leaf_lines(bytes,
627
key_length, ref_list_length)
605
629
self.min_key = key_list[0][0]
606
630
self.max_key = key_list[-1][0]
628
654
def __init__(self, bytes):
629
655
"""Parse bytes to create an internal node object."""
630
656
# splitlines mangles the \r delimiters.. don't use it.
631
self.keys = self._parse_lines(bytes.split(b'\n'))
657
self.keys = self._parse_lines(bytes.split('\n'))
633
659
def _parse_lines(self, lines):
635
661
self.offset = int(lines[1][7:])
636
662
as_st = static_tuple.StaticTuple.from_sequence
637
663
for line in lines[2:]:
640
# GZ 2017-05-24: Used to intern() each chunk of line as well, need
641
# to recheck performance and perhaps adapt StaticTuple to adjust.
642
nodes.append(as_st(line.split(b'\0')).intern())
666
nodes.append(as_st(map(intern, line.split('\0'))).intern())
676
700
self._base_offset = offset
677
701
self._leaf_factory = _LeafNode
678
702
# Default max size is 100,000 leave values
679
self._leaf_value_cache = None # lru_cache.LRUCache(100*1000)
703
self._leaf_value_cache = None # lru_cache.LRUCache(100*1000)
680
704
if unlimited_cache:
681
705
self._leaf_node_cache = {}
682
706
self._internal_node_cache = {}
688
712
self._internal_node_cache = fifo_cache.FIFOCache(100)
689
713
self._key_count = None
690
714
self._row_lengths = None
691
self._row_offsets = None # Start of each row, [-1] is the end
715
self._row_offsets = None # Start of each row, [-1] is the end
696
717
def __eq__(self, other):
697
718
"""Equal when self and other were created with the same parameters."""
699
isinstance(self, type(other))
700
and self._transport == other._transport
701
and self._name == other._name
702
and self._size == other._size)
704
def __lt__(self, other):
705
if isinstance(other, type(self)):
706
return ((self._name, self._size) < (other._name, other._size))
707
# Always sort existing indexes before ones that are still being built.
708
if isinstance(other, BTreeBuilder):
720
type(self) == type(other) and
721
self._transport == other._transport and
722
self._name == other._name and
723
self._size == other._size)
712
725
def __ne__(self, other):
713
726
return not self.__eq__(other)
747
760
pages fit in that length.
749
762
recommended_read = self._transport.recommended_page_size()
750
recommended_pages = int(math.ceil(recommended_read / _PAGE_SIZE))
763
recommended_pages = int(math.ceil(recommended_read /
751
765
return recommended_pages
753
767
def _compute_total_pages_in_index(self):
764
778
return self._row_offsets[-1]
765
779
# This is the number of pages as defined by the size of the index. They
766
780
# should be indentical.
767
total_pages = int(math.ceil(self._size / _PAGE_SIZE))
781
total_pages = int(math.ceil(self._size / float(_PAGE_SIZE)))
768
782
return total_pages
770
784
def _expand_offsets(self, offsets):
801
815
if total_pages - len(cached_offsets) <= self._recommended_pages:
802
816
# Read whatever is left
803
817
if cached_offsets:
804
expanded = [x for x in range(total_pages)
805
if x not in cached_offsets]
818
expanded = [x for x in xrange(total_pages)
819
if x not in cached_offsets]
807
expanded = list(range(total_pages))
821
expanded = range(total_pages)
808
822
if 'index' in debug.debug_flags:
809
823
trace.mutter(' reading all unread pages: %s', expanded)
859
873
if first is None:
860
874
first, end = self._find_layer_first_and_end(pos)
861
875
previous = pos - 1
863
previous not in cached_offsets and
864
previous not in final_offsets and
877
and previous not in cached_offsets
878
and previous not in final_offsets
879
and previous >= first):
866
880
next_tips.add(previous)
868
if (after < total_pages and
869
after not in cached_offsets and
870
after not in final_offsets and
882
if (after < total_pages
883
and after not in cached_offsets
884
and after not in final_offsets
872
886
next_tips.add(after)
873
887
# This would keep us from going bigger than
874
888
# recommended_pages by only expanding the first offsets.
898
912
self._get_root_node()
899
913
if ref_list_num + 1 > self.node_ref_lists:
900
914
raise ValueError('No ref list %d, index has %d ref lists'
901
% (ref_list_num, self.node_ref_lists))
915
% (ref_list_num, self.node_ref_lists))
904
918
for node in self.iter_all_entries():
924
938
def _get_offsets_to_cached_pages(self):
925
939
"""Determine what nodes we already have cached."""
926
cached_offsets = set(self._internal_node_cache)
927
# cache may be dict or LRUCache, keys() is the common method
940
cached_offsets = set(self._internal_node_cache.keys())
928
941
cached_offsets.update(self._leaf_node_cache.keys())
929
942
if self._root_node is not None:
930
943
cached_offsets.add(0)
963
976
def _cache_leaf_values(self, nodes):
964
977
"""Cache directly from key => value, skipping the btree."""
965
978
if self._leaf_value_cache is not None:
966
for node in nodes.values():
979
for node in nodes.itervalues():
967
980
for key, value in node.all_items():
968
981
if key in self._leaf_value_cache:
969
982
# Don't add the rest of the keys, we've seen this node
980
993
def iter_all_entries(self):
981
994
"""Iterate over all keys within the index.
983
:return: An iterable of (index, key, value) or
984
(index, key, value, reference_lists).
996
:return: An iterable of (index, key, value) or (index, key, value, reference_lists).
985
997
The former tuple is used when there are no reference lists in the
986
998
index, making the API compatible with simple key:value index types.
987
999
There is no defined order for the result iteration - it will be in
988
1000
the most efficient order for the index.
990
1002
if 'evil' in debug.debug_flags:
991
trace.mutter_callsite(
992
3, "iter_all_entries scales with size of history.")
1003
trace.mutter_callsite(3,
1004
"iter_all_entries scales with size of history.")
993
1005
if not self.key_count():
995
1007
if self._row_offsets[-1] == 1:
1004
1016
start_of_leaves = self._row_offsets[-2]
1005
1017
end_of_leaves = self._row_offsets[-1]
1006
needed_offsets = list(range(start_of_leaves, end_of_leaves))
1018
needed_offsets = range(start_of_leaves, end_of_leaves)
1007
1019
if needed_offsets == [0]:
1008
1020
# Special case when we only have a root node, as we have already
1009
1021
# read everything
1047
1059
# function, so there is even more to be gained.
1048
1060
# iter_steps = len(in_keys) + len(fixed_keys)
1049
1061
# bisect_steps = len(in_keys) * math.log(len(fixed_keys), 2)
1050
if len(in_keys) == 1: # Bisect will always be faster for M = 1
1062
if len(in_keys) == 1: # Bisect will always be faster for M = 1
1051
1063
return [(bisect.bisect_right(fixed_keys, in_keys[0]), in_keys)]
1052
1064
# elif bisect_steps < iter_steps:
1057
1069
# return [(o, offsets[o]) for o in sorted(offsets)]
1058
1070
in_keys_iter = iter(in_keys)
1059
1071
fixed_keys_iter = enumerate(fixed_keys)
1060
cur_in_key = next(in_keys_iter)
1061
cur_fixed_offset, cur_fixed_key = next(fixed_keys_iter)
1063
class InputDone(Exception):
1066
class FixedDone(Exception):
1072
cur_in_key = in_keys_iter.next()
1073
cur_fixed_offset, cur_fixed_key = fixed_keys_iter.next()
1075
class InputDone(Exception): pass
1076
class FixedDone(Exception): pass
1129
1138
positions = self._multi_bisect_right(sub_keys, node.keys)
1130
1139
node_offset = next_row_start + node.offset
1131
1140
next_nodes_and_keys.extend([(node_offset + pos, s_keys)
1132
for pos, s_keys in positions])
1141
for pos, s_keys in positions])
1133
1142
keys_at_index = next_nodes_and_keys
1134
1143
# We should now be at the _LeafNodes
1135
1144
node_indexes = [idx for idx, s_keys in keys_at_index]
1227
1237
if ref_list_num >= self.node_ref_lists:
1228
1238
raise ValueError('No ref list %d, index has %d ref lists'
1229
% (ref_list_num, self.node_ref_lists))
1239
% (ref_list_num, self.node_ref_lists))
1231
1241
# The main trick we are trying to accomplish is that when we find a
1232
1242
# key listing its parents, we expect that the parent key is also likely
1308
1318
parents_not_on_page.add(key)
1310
# assert (key != node.min_key and
1311
# key != node.max_key)
1320
# assert key != node.min_key and key != node.max_key
1312
1321
# If it was going to be present, it would be on
1313
1322
# *this* page, so mark it missing.
1314
1323
missing_keys.add(key)
1351
1360
self._get_root_node()
1352
1361
# TODO: only access nodes that can satisfy the prefixes we are looking
1353
1362
# for. For now, to meet API usage (as this function is not used by
1354
# current breezy) just suck the entire index and iterate in memory.
1363
# current bzrlib) just suck the entire index and iterate in memory.
1356
1365
if self.node_ref_lists:
1357
1366
if self._key_length == 1:
1383
1392
key_dict[key[-1]] = key_value
1384
1393
if self._key_length == 1:
1385
1394
for key in keys:
1386
index._sanity_check_key(self, key)
1397
raise errors.BadIndexKey(key)
1398
if len(key) != self._key_length:
1399
raise errors.BadIndexKey(key)
1388
1401
if self.node_ref_lists:
1389
1402
value, node_refs = nodes[key]
1393
1406
except KeyError:
1396
for entry in index._iter_entries_prefix(self, nodes_by_key, keys):
1412
raise errors.BadIndexKey(key)
1413
if len(key) != self._key_length:
1414
raise errors.BadIndexKey(key)
1415
# find what it refers to:
1416
key_dict = nodes_by_key
1417
elements = list(key)
1418
# find the subdict whose contents should be returned.
1420
while len(elements) and elements[0] is not None:
1421
key_dict = key_dict[elements[0]]
1424
# a non-existant lookup.
1429
key_dict = dicts.pop(-1)
1430
# can't be empty or would not exist
1431
item, value = key_dict.iteritems().next()
1432
if type(value) == dict:
1434
dicts.extend(key_dict.itervalues())
1437
for value in key_dict.itervalues():
1438
# each value is the key:value:node refs tuple
1440
yield (self, ) + value
1442
# the last thing looked up was a terminal element
1443
yield (self, ) + key_dict
1399
1445
def key_count(self):
1400
1446
"""Return an estimate of the number of keys in this index.
1426
1472
signature = bytes[0:len(self._signature())]
1427
1473
if not signature == self._signature():
1428
raise index.BadIndexFormatSignature(self._name, BTreeGraphIndex)
1474
raise errors.BadIndexFormatSignature(self._name, BTreeGraphIndex)
1429
1475
lines = bytes[len(self._signature()):].splitlines()
1430
1476
options_line = lines[0]
1431
1477
if not options_line.startswith(_OPTION_NODE_REFS):
1432
raise index.BadIndexOptions(self)
1478
raise errors.BadIndexOptions(self)
1434
1480
self.node_ref_lists = int(options_line[len(_OPTION_NODE_REFS):])
1435
1481
except ValueError:
1436
raise index.BadIndexOptions(self)
1482
raise errors.BadIndexOptions(self)
1437
1483
options_line = lines[1]
1438
1484
if not options_line.startswith(_OPTION_KEY_ELEMENTS):
1439
raise index.BadIndexOptions(self)
1485
raise errors.BadIndexOptions(self)
1441
1487
self._key_length = int(options_line[len(_OPTION_KEY_ELEMENTS):])
1442
1488
except ValueError:
1443
raise index.BadIndexOptions(self)
1489
raise errors.BadIndexOptions(self)
1444
1490
options_line = lines[2]
1445
1491
if not options_line.startswith(_OPTION_LEN):
1446
raise index.BadIndexOptions(self)
1492
raise errors.BadIndexOptions(self)
1448
1494
self._key_count = int(options_line[len(_OPTION_LEN):])
1449
1495
except ValueError:
1450
raise index.BadIndexOptions(self)
1496
raise errors.BadIndexOptions(self)
1451
1497
options_line = lines[3]
1452
1498
if not options_line.startswith(_OPTION_ROW_LENGTHS):
1453
raise index.BadIndexOptions(self)
1499
raise errors.BadIndexOptions(self)
1455
self._row_lengths = [int(length) for length in
1456
options_line[len(_OPTION_ROW_LENGTHS):].split(
1501
self._row_lengths = map(int, [length for length in
1502
options_line[len(_OPTION_ROW_LENGTHS):].split(',')
1459
1504
except ValueError:
1460
raise index.BadIndexOptions(self)
1505
raise errors.BadIndexOptions(self)
1461
1506
self._compute_row_offsets()
1463
1508
# calculate the bytes we have processed
1496
1541
self._size = num_bytes - base_offset
1497
1542
# the whole thing should be parsed out of 'bytes'
1498
1543
ranges = [(start, min(_PAGE_SIZE, num_bytes - start))
1500
base_offset, num_bytes, _PAGE_SIZE)]
1544
for start in xrange(base_offset, num_bytes, _PAGE_SIZE)]
1503
1547
if offset > self._size:
1511
1555
elif bytes is not None:
1512
1556
# already have the whole file
1513
data_ranges = [(start, bytes[start:start + size])
1557
data_ranges = [(start, bytes[start:start+size])
1514
1558
for start, size in ranges]
1515
1559
elif self._file is None:
1516
1560
data_ranges = self._transport.readv(self._name, ranges)
1534
1578
node = _InternalNode(bytes)
1536
1580
raise AssertionError("Unknown node type for %r" % bytes)
1537
yield offset // _PAGE_SIZE, node
1581
yield offset / _PAGE_SIZE, node
1539
1583
def _signature(self):
1540
1584
"""The file signature for this index type."""
1550
1594
# We shouldn't be reading anything anyway
1552
1596
node_end = self._row_offsets[-1]
1553
for node in self._read_nodes(list(range(start_node, node_end))):
1597
for node in self._read_nodes(range(start_node, node_end)):
1557
1601
_gcchk_factory = _LeafNode
1560
from . import _btree_serializer_pyx as _btree_serializer
1604
from bzrlib import _btree_serializer_pyx as _btree_serializer
1561
1605
_gcchk_factory = _btree_serializer._parse_into_chk
1562
except ImportError as e:
1606
except ImportError, e:
1563
1607
osutils.failed_to_load_extension(e)
1564
from . import _btree_serializer_py as _btree_serializer
1608
from bzrlib import _btree_serializer_py as _btree_serializer
added
removed
bzrlib/btree_index.py
