53
from ..sixish import (
51
57
from ..static_tuple import StaticTuple
54
60
# If each line is 50 bytes, and you have 255 internal pages, with 255-way fan
55
61
# out, it takes 3.1MB to cache the layer.
56
_PAGE_CACHE_SIZE = 4 * 1024 * 1024
62
_PAGE_CACHE_SIZE = 4*1024*1024
57
63
# Per thread caches for 2 reasons:
58
64
# - in the server we may be serving very different content, so we get less
132
137
# Check preconditions first.
133
138
as_st = StaticTuple.from_sequence
134
139
new_items = {as_st(key) for (old, key, value) in delta
135
if key is not None and old is None}
140
if key is not None and old is None}
136
141
existing_new = list(self.iteritems(key_filter=new_items))
138
143
raise errors.InconsistentDeltaDelta(delta,
139
"New items are already in the map %r." % existing_new)
144
"New items are already in the map %r." % existing_new)
140
145
# Now apply changes.
141
146
for old, new, value in delta:
142
147
if old is not None and old != new:
168
173
if isinstance(node, StaticTuple):
169
174
bytes = self._read_bytes(node)
170
175
return _deserialise(bytes, node,
171
search_key_func=self._search_key_func)
176
search_key_func=self._search_key_func)
177
182
return _get_cache()[key]
179
184
stream = self._store.get_record_stream([key], 'unordered', True)
180
bytes = next(stream).get_bytes_as('fulltext')
185
bytes = stream.next().get_bytes_as('fulltext')
181
186
_get_cache()[key] = bytes
184
def _dump_tree(self, include_keys=False, encoding='utf-8'):
189
def _dump_tree(self, include_keys=False):
185
190
"""Return the tree in a string representation."""
186
191
self._ensure_root()
187
def decode(x): return x.decode(encoding)
188
res = self._dump_tree_node(self._root_node, prefix=b'', indent='',
189
decode=decode, include_keys=include_keys)
190
res.append('') # Give a trailing '\n'
191
return '\n'.join(res)
192
res = self._dump_tree_node(self._root_node, prefix='', indent='',
193
include_keys=include_keys)
194
res.append(b'') # Give a trailing '\n'
195
return b'\n'.join(res)
193
def _dump_tree_node(self, node, prefix, indent, decode, include_keys=True):
197
def _dump_tree_node(self, node, prefix, indent, include_keys=True):
194
198
"""For this node and all children, generate a string representation."""
196
200
if not include_keys:
199
203
node_key = node.key()
200
204
if node_key is not None:
201
key_str = ' %s' % (decode(node_key[0]),)
205
key_str = b' %s' % (node_key[0],)
204
result.append('%s%r %s%s' % (indent, decode(prefix), node.__class__.__name__,
208
result.append(b'%s%r %s%s' % (indent, prefix, node.__class__.__name__,
206
210
if isinstance(node, InternalNode):
207
211
# Trigger all child nodes to get loaded
208
212
list(node._iter_nodes(self._store))
209
for prefix, sub in sorted(node._items.items()):
213
for prefix, sub in sorted(viewitems(node._items)):
210
214
result.extend(self._dump_tree_node(sub, prefix, indent + ' ',
211
decode=decode, include_keys=include_keys))
215
include_keys=include_keys))
213
for key, value in sorted(node._items.items()):
217
for key, value in sorted(viewitems(node._items)):
214
218
# Don't use prefix nor indent here to line up when used in
215
219
# tests in conjunction with assertEqualDiff
216
result.append(' %r %r' % (
217
tuple([decode(ke) for ke in key]), decode(value)))
220
result.append(b' %r %r' % (tuple(key), value))
221
224
def from_dict(klass, store, initial_value, maximum_size=0, key_width=1,
222
search_key_func=None):
225
search_key_func=None):
223
226
"""Create a CHKMap in store with initial_value as the content.
225
228
:param store: The store to record initial_value in, a VersionedFiles
236
239
:return: The root chk of the resulting CHKMap.
238
241
root_key = klass._create_directly(store, initial_value,
239
maximum_size=maximum_size, key_width=key_width,
240
search_key_func=search_key_func)
242
maximum_size=maximum_size, key_width=key_width,
243
search_key_func=search_key_func)
241
244
if not isinstance(root_key, StaticTuple):
242
245
raise AssertionError('we got a %s instead of a StaticTuple'
243
246
% (type(root_key),))
250
253
result._root_node.set_maximum_size(maximum_size)
251
254
result._root_node._key_width = key_width
253
for key, value in initial_value.items():
256
for key, value in viewitems(initial_value):
254
257
delta.append((None, key, value))
255
258
root_key = result.apply_delta(delta)
263
266
node._key_width = key_width
264
267
as_st = StaticTuple.from_sequence
265
268
node._items = dict((as_st(key), val)
266
for key, val in initial_value.items())
269
for key, val in viewitems(initial_value))
267
270
node._raw_size = sum(node._key_value_len(key, value)
268
for key, value in node._items.items())
271
for key, value in viewitems(node._items))
269
272
node._len = len(node._items)
270
273
node._compute_search_prefix()
271
274
node._compute_serialised_prefix()
272
if (node._len > 1 and
274
node._current_size() > maximum_size):
277
and node._current_size() > maximum_size):
275
278
prefix, node_details = node._split(store)
276
279
if len(node_details) == 1:
277
280
raise AssertionError('Failed to split using node._split')
323
326
# key_path (a list of tuples, tail-sharing down the tree.)
324
327
self_pending = []
325
328
basis_pending = []
327
329
def process_node(node, path, a_map, pending):
328
330
# take a node and expand it
329
331
node = a_map._get_node(node)
330
332
if isinstance(node, LeafNode):
331
333
path = (node._key, path)
332
for key, value in node._items.items():
334
for key, value in viewitems(node._items):
333
335
# For a LeafNode, the key is a serialized_key, rather than
334
336
# a search_key, but the heap is using search_keys
335
337
search_key = node._search_key_func(key)
338
340
# type(node) == InternalNode
339
341
path = (node._key, path)
340
for prefix, child in node._items.items():
342
for prefix, child in viewitems(node._items):
341
343
heapq.heappush(pending, (prefix, None, child, path))
343
344
def process_common_internal_nodes(self_node, basis_node):
344
self_items = set(self_node._items.items())
345
basis_items = set(basis_node._items.items())
345
self_items = set(viewitems(self_node._items))
346
basis_items = set(viewitems(basis_node._items))
346
347
path = (self_node._key, None)
347
348
for prefix, child in self_items - basis_items:
348
349
heapq.heappush(self_pending, (prefix, None, child, path))
349
350
path = (basis_node._key, None)
350
351
for prefix, child in basis_items - self_items:
351
352
heapq.heappush(basis_pending, (prefix, None, child, path))
353
353
def process_common_leaf_nodes(self_node, basis_node):
354
self_items = set(self_node._items.items())
355
basis_items = set(basis_node._items.items())
354
self_items = set(viewitems(self_node._items))
355
basis_items = set(viewitems(basis_node._items))
356
356
path = (self_node._key, None)
357
357
for key, value in self_items - basis_items:
358
358
prefix = self._search_key_func(key)
361
361
for key, value in basis_items - self_items:
362
362
prefix = basis._search_key_func(key)
363
363
heapq.heappush(basis_pending, (prefix, key, value, path))
365
364
def process_common_prefix_nodes(self_node, self_path,
366
365
basis_node, basis_path):
367
366
# Would it be more efficient if we could request both at the same
369
368
self_node = self._get_node(self_node)
370
369
basis_node = basis._get_node(basis_node)
371
if (isinstance(self_node, InternalNode) and
372
isinstance(basis_node, InternalNode)):
370
if (isinstance(self_node, InternalNode)
371
and isinstance(basis_node, InternalNode)):
373
372
# Matching internal nodes
374
373
process_common_internal_nodes(self_node, basis_node)
375
elif (isinstance(self_node, LeafNode) and
376
isinstance(basis_node, LeafNode)):
374
elif (isinstance(self_node, LeafNode)
375
and isinstance(basis_node, LeafNode)):
377
376
process_common_leaf_nodes(self_node, basis_node)
379
378
process_node(self_node, self_path, self, self_pending)
472
470
basis_details = heapq.heappop(basis_pending)
473
471
if self_details[2] != basis_details[2]:
474
472
yield (self_details[1],
475
basis_details[2], self_details[2])
473
basis_details[2], self_details[2])
477
475
# At least one side wasn't a simple value
478
if (self._node_key(self_pending[0][2])
479
== self._node_key(basis_pending[0][2])):
476
if (self._node_key(self_pending[0][2]) ==
477
self._node_key(basis_pending[0][2])):
480
478
# Identical pointers, skip (and don't bother adding to
481
479
# excluded, it won't turn up again.
482
480
heapq.heappop(self_pending)
531
529
def map(self, key, value):
532
530
"""Map a key tuple to value.
534
532
:param key: A key to map.
535
533
:param value: The value to assign to key.
542
540
self._root_node = node_details[0][1]
544
542
self._root_node = InternalNode(prefix,
545
search_key_func=self._search_key_func)
543
search_key_func=self._search_key_func)
546
544
self._root_node.set_maximum_size(node_details[0][1].maximum_size)
547
545
self._root_node._key_width = node_details[0][1]._key_width
548
546
for split, node in node_details:
563
561
self._ensure_root()
564
562
if isinstance(self._root_node, InternalNode):
565
563
unmapped = self._root_node.unmap(self._store, key,
566
check_remap=check_remap)
564
check_remap=check_remap)
568
566
unmapped = self._root_node.unmap(self._store, key)
569
567
self._root_node = unmapped
596
594
__slots__ = ('_key', '_len', '_maximum_size', '_key_width',
597
595
'_raw_size', '_items', '_search_prefix', '_search_key_func'
600
598
def __init__(self, key_width=1):
601
599
"""Create a node.
711
708
'%s(key:%s len:%s size:%s max:%s prefix:%s keywidth:%s items:%s)' \
712
709
% (self.__class__.__name__, self._key, self._len, self._raw_size,
713
self._maximum_size, self._search_prefix, self._key_width, items_str)
710
self._maximum_size, self._search_prefix, self._key_width, items_str)
715
712
def _current_size(self):
716
713
"""Answer the current serialised size of this node.
728
725
prefix_len = len(self._common_serialised_prefix)
729
726
bytes_for_items = (self._raw_size - (prefix_len * self._len))
730
return (9 + # 'chkleaf:\n' +
731
len(str(self._maximum_size)) + 1 +
732
len(str(self._key_width)) + 1 +
733
len(str(self._len)) + 1 +
727
return (9 # 'chkleaf:\n'
728
+ len(str(self._maximum_size)) + 1
729
+ len(str(self._key_width)) + 1
730
+ len(str(self._len)) + 1
738
735
def deserialise(klass, bytes, key, search_key_func=None):
769
766
# Short items, we need to match based on a prefix
770
767
filters.setdefault(len(key), set()).add(key)
772
filters_itemview = filters.items()
773
for item in self._items.items():
769
filters_itemview = viewitems(filters)
770
for item in viewitems(self._items):
774
771
for length, length_filter in filters_itemview:
775
772
if item[0][:length] in length_filter:
779
yield from self._items.items()
776
for item in viewitems(self._items):
781
779
def _key_value_len(self, key, value):
782
780
# TODO: Should probably be done without actually joining the key, but
783
781
# then that can be done via the C extension
784
return (len(self._serialise_key(key)) + 1 +
785
len(b'%d' % value.count(b'\n')) + 1 +
782
return (len(self._serialise_key(key)) + 1
783
+ len(str(value.count(b'\n'))) + 1
788
786
def _search_key(self, key):
789
787
return self._search_key_func(key)
814
812
self._search_prefix = self.common_prefix(
815
813
self._search_prefix, search_key)
816
if (self._len > 1 and
817
self._maximum_size and
818
self._current_size() > self._maximum_size):
815
and self._maximum_size
816
and self._current_size() > self._maximum_size):
819
817
# Check to see if all of the search_keys for this node are
820
818
# identical. We allow the node to grow under that circumstance
821
819
# (we could track this as common state, but it is infrequent)
822
if (search_key != self._search_prefix or
823
not self._are_search_keys_identical()):
820
if (search_key != self._search_prefix
821
or not self._are_search_keys_identical()):
837
835
common_prefix = self._search_prefix
838
836
split_at = len(common_prefix) + 1
840
for key, value in self._items.items():
838
for key, value in viewitems(self._items):
841
839
search_key = self._search_key(key)
842
840
prefix = search_key[:split_at]
843
841
# TODO: Generally only 1 key can be exactly the right length,
849
847
# may get a '\00' node anywhere, but won't have keys of
850
848
# different lengths.
851
849
if len(prefix) < split_at:
852
prefix += b'\x00' * (split_at - len(prefix))
850
prefix += b'\x00'*(split_at - len(prefix))
853
851
if prefix not in result:
854
852
node = LeafNode(search_key_func=self._search_key_func)
855
853
node.set_maximum_size(self._maximum_size)
865
863
result.pop(prefix)
866
864
new_node = InternalNode(sub_prefix,
867
search_key_func=self._search_key_func)
865
search_key_func=self._search_key_func)
868
866
new_node.set_maximum_size(self._maximum_size)
869
867
new_node._key_width = self._key_width
870
868
for split, node in node_details:
871
869
new_node.add_node(split, node)
872
870
result[prefix] = new_node
873
return common_prefix, list(result.items())
871
return common_prefix, list(viewitems(result))
875
873
def map(self, store, key, value):
876
874
"""Map key to value."""
884
882
if self._search_prefix is _unknown:
885
883
raise AssertionError('%r must be known' % self._search_prefix)
886
return self._search_prefix, [(b"", self)]
884
return self._search_prefix, [("", self)]
888
886
_serialise_key = b'\x00'.join
901
899
lines.append(b'\n')
902
900
if len(self._items) != 0:
903
901
raise AssertionError('If _common_serialised_prefix is None'
904
' we should have no items')
902
' we should have no items')
906
904
lines.append(b'%s\n' % (self._common_serialised_prefix,))
907
905
prefix_len = len(self._common_serialised_prefix)
908
for key, value in sorted(self._items.items()):
906
for key, value in sorted(viewitems(self._items)):
909
907
# Always add a final newline
910
908
value_lines = osutils.chunks_to_lines([value + b'\n'])
911
909
serialized = b"%s\x00%d\n" % (self._serialise_key(key),
913
911
if not serialized.startswith(self._common_serialised_prefix):
914
912
raise AssertionError('We thought the common prefix was %r'
915
' but entry %r does not have it in common'
916
% (self._common_serialised_prefix, serialized))
913
' but entry %r does not have it in common'
914
% (self._common_serialised_prefix, serialized))
917
915
lines.append(serialized[prefix_len:])
918
916
lines.extend(value_lines)
919
917
sha1, _, _ = store.add_lines((None,), (), lines)
994
992
__slots__ = ('_node_width',)
996
def __init__(self, prefix=b'', search_key_func=None):
994
def __init__(self, prefix='', search_key_func=None):
997
995
Node.__init__(self)
998
996
# The size of an internalnode with default values and no children.
999
997
# How many octets key prefixes within this node are.
1014
1012
raise AssertionError("_search_prefix should not be None")
1015
1013
if not prefix.startswith(self._search_prefix):
1016
1014
raise AssertionError("prefixes mismatch: %s must start with %s"
1017
% (prefix, self._search_prefix))
1015
% (prefix, self._search_prefix))
1018
1016
if len(prefix) != len(self._search_prefix) + 1:
1019
1017
raise AssertionError("prefix wrong length: len(%s) is not %d" %
1020
(prefix, len(self._search_prefix) + 1))
1018
(prefix, len(self._search_prefix) + 1))
1021
1019
self._len += len(node)
1022
1020
if not len(self._items):
1023
1021
self._node_width = len(prefix)
1024
1022
if self._node_width != len(self._search_prefix) + 1:
1025
1023
raise AssertionError("node width mismatch: %d is not %d" %
1026
(self._node_width, len(self._search_prefix) + 1))
1024
(self._node_width, len(self._search_prefix) + 1))
1027
1025
self._items[prefix] = node
1028
1026
self._key = None
1030
1028
def _current_size(self):
1031
1029
"""Answer the current serialised size of this node."""
1032
return (self._raw_size + len(str(self._len)) + len(str(self._key_width))
1033
+ len(str(self._maximum_size)))
1030
return (self._raw_size + len(str(self._len)) + len(str(self._key_width)) +
1031
len(str(self._maximum_size)))
1036
1034
def deserialise(klass, bytes, key, search_key_func=None):
1070
1068
# yielding all nodes, yield whatever we have, and queue up a read
1071
1069
# for whatever we are missing
1072
1070
shortcut = True
1073
for prefix, node in self._items.items():
1071
for prefix, node in viewitems(self._items):
1074
1072
if node.__class__ is StaticTuple:
1075
1073
keys[node] = (prefix, None)
1121
1119
for key in key_filter:
1122
1120
search_prefix = self._search_prefix_filter(key)
1123
1121
length_filter = length_filters.setdefault(
1124
len(search_prefix), set())
1122
len(search_prefix), set())
1125
1123
length_filter.add(search_prefix)
1126
1124
prefix_to_keys.setdefault(search_prefix, []).append(key)
1128
if (self._node_width in length_filters and
1129
len(length_filters) == 1):
1126
if (self._node_width in length_filters
1127
and len(length_filters) == 1):
1130
1128
# all of the search prefixes match exactly _node_width. This
1131
1129
# means that everything is an exact match, and we can do a
1132
1130
# lookup into self._items, rather than iterating over the items
1147
1145
# The slow way. We walk every item in self._items, and check to
1148
1146
# see if there are any matches
1149
length_filters_itemview = length_filters.items()
1150
for prefix, node in self._items.items():
1147
length_filters_itemview = viewitems(length_filters)
1148
for prefix, node in viewitems(self._items):
1151
1149
node_key_filter = []
1152
1150
for length, length_filter in length_filters_itemview:
1153
1151
sub_prefix = prefix[:length]
1154
1152
if sub_prefix in length_filter:
1155
1153
node_key_filter.extend(prefix_to_keys[sub_prefix])
1156
if node_key_filter: # this key matched something, yield it
1154
if node_key_filter: # this key matched something, yield it
1157
1155
if node.__class__ is StaticTuple:
1158
1156
keys[node] = (prefix, node_key_filter)
1170
1168
node = _deserialise(bytes, key,
1171
search_key_func=self._search_key_func)
1169
search_key_func=self._search_key_func)
1172
1170
prefix, node_key_filter = keys[key]
1173
1171
self._items[prefix] = node
1174
1172
found_keys.add(key)
1190
1188
for record in stream:
1191
1189
bytes = record.get_bytes_as('fulltext')
1192
1190
node = _deserialise(bytes, record.key,
1193
search_key_func=self._search_key_func)
1191
search_key_func=self._search_key_func)
1194
1192
prefix, node_key_filter = keys[record.key]
1195
1193
node_and_filters.append((node, node_key_filter))
1196
1194
self._items[prefix] = node
1205
1203
search_key = self._search_key(key)
1206
1204
if self._node_width != len(self._search_prefix) + 1:
1207
1205
raise AssertionError("node width mismatch: %d is not %d" %
1208
(self._node_width, len(self._search_prefix) + 1))
1206
(self._node_width, len(self._search_prefix) + 1))
1209
1207
if not search_key.startswith(self._search_prefix):
1210
1208
# This key doesn't fit in this index, so we need to split at the
1211
1209
# point where it would fit, insert self into that internal node,
1213
1211
new_prefix = self.common_prefix(self._search_prefix,
1215
1213
new_parent = InternalNode(new_prefix,
1216
search_key_func=self._search_key_func)
1214
search_key_func=self._search_key_func)
1217
1215
new_parent.set_maximum_size(self._maximum_size)
1218
1216
new_parent._key_width = self._key_width
1219
new_parent.add_node(self._search_prefix[:len(new_prefix) + 1],
1217
new_parent.add_node(self._search_prefix[:len(new_prefix)+1],
1221
1219
return new_parent.map(store, key, value)
1222
children = [node for node, _ in self._iter_nodes(
1223
store, key_filter=[key])]
1220
children = [node for node, _
1221
in self._iter_nodes(store, key_filter=[key])]
1225
1223
child = children[0]
1255
1253
# amount is over a configurable limit.
1256
1254
new_size = child._current_size()
1257
1255
shrinkage = old_size - new_size
1258
if (shrinkage > 0 and new_size < _INTERESTING_NEW_SIZE or
1259
shrinkage > _INTERESTING_SHRINKAGE_LIMIT):
1256
if (shrinkage > 0 and new_size < _INTERESTING_NEW_SIZE
1257
or shrinkage > _INTERESTING_SHRINKAGE_LIMIT):
1261
1259
"checking remap as size shrunk by %d to be %d",
1262
1260
shrinkage, new_size)
1263
1261
new_node = self._check_remap(store)
1264
1262
if new_node._search_prefix is None:
1265
1263
raise AssertionError("_search_prefix should not be None")
1266
return new_node._search_prefix, [(b'', new_node)]
1264
return new_node._search_prefix, [('', new_node)]
1267
1265
# child has overflown - create a new intermediate node.
1268
1266
# XXX: This is where we might want to try and expand our depth
1269
1267
# to refer to more bytes of every child (which would give us
1274
1272
child.add_node(split, node)
1275
1273
self._len = self._len - old_len + len(child)
1276
1274
self._key = None
1277
return self._search_prefix, [(b"", self)]
1275
return self._search_prefix, [("", self)]
1279
1277
def _new_child(self, search_key, klass):
1280
1278
"""Create a new child node of type klass."""
1291
1289
:param store: A VersionedFiles honouring the CHK extensions.
1292
1290
:return: An iterable of the keys inserted by this operation.
1294
for node in self._items.values():
1292
for node in viewvalues(self._items):
1295
1293
if isinstance(node, StaticTuple):
1296
1294
# Never deserialised.
1308
1306
raise AssertionError("_search_prefix should not be None")
1309
1307
lines.append(b'%s\n' % (self._search_prefix,))
1310
1308
prefix_len = len(self._search_prefix)
1311
for prefix, node in sorted(self._items.items()):
1309
for prefix, node in sorted(viewitems(self._items)):
1312
1310
if isinstance(node, StaticTuple):
1316
1314
serialised = b"%s\x00%s\n" % (prefix, key)
1317
1315
if not serialised.startswith(self._search_prefix):
1318
1316
raise AssertionError("prefixes mismatch: %s must start with %s"
1319
% (serialised, self._search_prefix))
1317
% (serialised, self._search_prefix))
1320
1318
lines.append(serialised[prefix_len:])
1321
1319
sha1, _, _ = store.add_lines((None,), (), lines)
1322
1320
self._key = StaticTuple(b"sha1:" + sha1,).intern()
1327
1325
"""Return the serialised key for key in this node."""
1328
1326
# search keys are fixed width. All will be self._node_width wide, so we
1329
1327
# pad as necessary.
1330
return (self._search_key_func(key) + b'\x00' * self._node_width)[:self._node_width]
1328
return (self._search_key_func(key) + b'\x00'*self._node_width)[:self._node_width]
1332
1330
def _search_prefix_filter(self, key):
1333
1331
"""Serialise key for use as a prefix filter in iteritems."""
1350
1348
if self._key is None:
1351
1349
raise AssertionError("unserialised nodes have no refs.")
1353
for value in self._items.values():
1351
for value in viewvalues(self._items):
1354
1352
if isinstance(value, StaticTuple):
1355
1353
refs.append(value)
1371
1369
if not len(self._items):
1372
1370
raise AssertionError("can't unmap in an empty InternalNode.")
1373
1371
children = [node for node, _
1374
in self._iter_nodes(store, key_filter=[key])]
1372
in self._iter_nodes(store, key_filter=[key])]
1376
1374
child = children[0]
1389
1387
self._items[search_key] = unmapped
1390
1388
if len(self._items) == 1:
1391
1389
# this node is no longer needed:
1392
return list(self._items.values())[0]
1390
return list(viewvalues(self._items))[0]
1393
1391
if isinstance(unmapped, InternalNode):
1395
1393
if check_remap:
1439
1437
if isinstance(node, InternalNode):
1440
1438
# Without looking at any leaf nodes, we are sure
1442
for key, value in node._items.items():
1440
for key, value in viewitems(node._items):
1443
1441
if new_leaf._map_no_split(key, value):
1445
1443
trace.mutter("remap generated a new LeafNode")
1452
1450
node = LeafNode.deserialise(data, key, search_key_func=search_key_func)
1453
1451
elif data.startswith(b"chknode:\n"):
1454
1452
node = InternalNode.deserialise(data, key,
1455
search_key_func=search_key_func)
1453
search_key_func=search_key_func)
1457
1455
raise AssertionError("Unknown node type.")
1528
1526
# indicate that we keep 100k prefix_refs around while
1529
1527
# processing. They *should* be shorter lived than that...
1530
1528
# It does cost us ~10s of processing time
1531
prefix_refs = list(node._items.items())
1529
prefix_refs = list(viewitems(node._items))
1534
1532
prefix_refs = []
1535
1533
# Note: We don't use a StaticTuple here. Profiling showed a
1536
1534
# minor memory improvement (0.8MB out of 335MB peak 0.2%)
1537
1535
# But a significant slowdown (15s / 145s, or 10%)
1538
items = list(node._items.items())
1536
items = list(viewitems(node._items))
1539
1537
yield record, node, prefix_refs, items
1541
1539
def _read_old_roots(self):
1545
1543
self._read_nodes_from_store(self._old_root_keys):
1546
1544
# Uninteresting node
1547
1545
prefix_refs = [p_r for p_r in prefix_refs
1548
if p_r[1] not in all_old_chks]
1546
if p_r[1] not in all_old_chks]
1549
1547
new_refs = [p_r[1] for p_r in prefix_refs]
1550
1548
all_old_chks.update(new_refs)
1551
1549
# TODO: This might be a good time to turn items into StaticTuple
1601
1599
# At this level, we now know all the uninteresting references
1602
1600
# So we filter and queue up whatever is remaining
1603
1601
prefix_refs = [p_r for p_r in prefix_refs
1604
if p_r[1] not in self._all_old_chks and
1605
p_r[1] not in processed_new_refs]
1602
if p_r[1] not in self._all_old_chks
1603
and p_r[1] not in processed_new_refs]
1606
1604
refs = [p_r[1] for p_r in prefix_refs]
1607
1605
new_prefixes.update([p_r[0] for p_r in prefix_refs])
1608
1606
self._new_queue.extend(refs)
1614
1612
# self._new_item_queue will hold the contents of multiple
1615
1613
# records for an extended lifetime
1616
1614
new_items = [item for item in items
1617
if item not in self._all_old_items]
1615
if item not in self._all_old_items]
1618
1616
self._new_item_queue.extend(new_items)
1619
1617
new_prefixes.update([self._search_key_func(item[0])
1620
1618
for item in new_items])
1638
1636
processed_new_refs = self._processed_new_refs
1639
1637
all_old_items = self._all_old_items
1640
1638
new_items = [item for item in self._new_item_queue
1641
if item not in all_old_items]
1639
if item not in all_old_items]
1642
1640
self._new_item_queue = []
1644
1642
yield None, new_items
1735
1733
_search_key_255,
1736
1734
_deserialise_leaf_node,
1737
1735
_deserialise_internal_node,
1739
search_key_registry.register(b'hash-16-way', _search_key_16)
1740
search_key_registry.register(b'hash-255-way', _search_key_255)
1737
search_key_registry.register('hash-16-way', _search_key_16)
1738
search_key_registry.register('hash-255-way', _search_key_255)
1743
1741
def _check_key(key):
1749
1747
if not isinstance(key, StaticTuple):
1750
1748
raise TypeError('key %r is not StaticTuple but %s' % (key, type(key)))
1751
1749
if len(key) != 1:
1752
raise ValueError('key %r should have length 1, not %d' %
1750
raise ValueError('key %r should have length 1, not %d' % (key, len(key),))
1754
1751
if not isinstance(key[0], str):
1755
1752
raise TypeError('key %r should hold a str, not %r'
1756
1753
% (key, type(key[0])))
1757
1754
if not key[0].startswith('sha1:'):
1758
1755
raise ValueError('key %r should point to a sha1:' % (key,))
added
removed
breezy/bzr/chk_map.py
