116
118
# Check preconditions first.
117
new_items = set([key for (old, key, value) in delta if key is not None
119
as_st = StaticTuple.from_sequence
120
new_items = set([as_st(key) for (old, key, value) in delta
121
if key is not None and old is None])
119
122
existing_new = list(self.iteritems(key_filter=new_items))
121
124
raise errors.InconsistentDeltaDelta(delta,
149
152
:param node: A tuple key or node object.
150
153
:return: A node object.
152
if type(node) is tuple:
155
if type(node) is StaticTuple:
153
156
bytes = self._read_bytes(node)
154
157
return _deserialise(bytes, node,
155
158
search_key_func=self._search_key_func)
196
199
for key, value in sorted(node._items.iteritems()):
197
200
# Don't use prefix nor indent here to line up when used in
198
201
# tests in conjunction with assertEqualDiff
199
result.append(' %r %r' % (key, value))
202
result.append(' %r %r' % (tuple(key), value))
220
223
root_key = klass._create_directly(store, initial_value,
221
224
maximum_size=maximum_size, key_width=key_width,
222
225
search_key_func=search_key_func)
226
if type(root_key) is not StaticTuple:
227
raise AssertionError('we got a %s instead of a StaticTuple'
240
246
node = LeafNode(search_key_func=search_key_func)
241
247
node.set_maximum_size(maximum_size)
242
248
node._key_width = key_width
243
node._items = dict(initial_value)
249
as_st = StaticTuple.from_sequence
250
node._items = dict([(as_st(key), val) for key, val
251
in initial_value.iteritems()])
244
252
node._raw_size = sum([node._key_value_len(key, value)
245
for key,value in initial_value.iteritems()])
253
for key,value in node._items.iteritems()])
246
254
node._len = len(node._items)
247
255
node._compute_search_prefix()
248
256
node._compute_serialised_prefix()
484
492
def iteritems(self, key_filter=None):
485
493
"""Iterate over the entire CHKMap's contents."""
486
494
self._ensure_root()
495
if key_filter is not None:
496
as_st = StaticTuple.from_sequence
497
key_filter = [as_st(key) for key in key_filter]
487
498
return self._root_node.iteritems(self._store, key_filter=key_filter)
490
501
"""Return the key for this map."""
491
if type(self._root_node) is tuple:
502
if type(self._root_node) is StaticTuple:
492
503
return self._root_node
494
505
return self._root_node._key
503
514
:param key: A key to map.
504
515
:param value: The value to assign to key.
517
key = StaticTuple.from_sequence(key)
506
518
# Need a root object.
507
519
self._ensure_root()
508
520
prefix, node_details = self._root_node.map(self._store, key, value)
519
531
def _node_key(self, node):
520
532
"""Get the key for a node whether it's a tuple or node."""
521
533
if type(node) is tuple:
534
node = StaticTuple.from_sequence(node)
535
if type(node) is StaticTuple:
526
540
def unmap(self, key, check_remap=True):
527
541
"""remove key from the map."""
542
key = StaticTuple.from_sequence(key)
528
543
self._ensure_root()
529
544
if type(self._root_node) is InternalNode:
530
545
unmapped = self._root_node.unmap(self._store, key,
706
721
:param bytes: The bytes of the node.
707
722
:param key: The key that the serialised node has.
724
key = static_tuple.expect_static_tuple(key)
709
725
return _deserialise_leaf_node(bytes, key,
710
726
search_key_func=search_key_func)
881
897
lines.append(serialized[prefix_len:])
882
898
lines.extend(value_lines)
883
899
sha1, _, _ = store.add_lines((None,), (), lines)
884
self._key = ("sha1:" + sha1,)
900
self._key = StaticTuple("sha1:" + sha1,).intern()
885
901
bytes = ''.join(lines)
886
902
if len(bytes) != self._current_size():
887
903
raise AssertionError('Invalid _current_size')
1004
1020
:param key: The key that the serialised node has.
1005
1021
:return: An InternalNode instance.
1023
key = static_tuple.expect_static_tuple(key)
1007
1024
return _deserialise_internal_node(bytes, key,
1008
1025
search_key_func=search_key_func)
1034
1051
# for whatever we are missing
1035
1052
shortcut = True
1036
1053
for prefix, node in self._items.iteritems():
1037
if node.__class__ is tuple:
1054
if node.__class__ is StaticTuple:
1038
1055
keys[node] = (prefix, None)
1040
1057
yield node, None
1069
1086
# A given key can only match 1 child node, if it isn't
1070
1087
# there, then we can just return nothing
1072
if node.__class__ is tuple:
1089
if node.__class__ is StaticTuple:
1073
1090
keys[node] = (search_prefix, [key])
1075
1092
# This is loaded, and the only thing that can match,
1102
1119
# We can ignore this one
1104
1121
node_key_filter = prefix_to_keys[search_prefix]
1105
if node.__class__ is tuple:
1122
if node.__class__ is StaticTuple:
1106
1123
keys[node] = (search_prefix, node_key_filter)
1108
1125
yield node, node_key_filter
1117
1134
if sub_prefix in length_filter:
1118
1135
node_key_filter.extend(prefix_to_keys[sub_prefix])
1119
1136
if node_key_filter: # this key matched something, yield it
1120
if node.__class__ is tuple:
1137
if node.__class__ is StaticTuple:
1121
1138
keys[node] = (prefix, node_key_filter)
1123
1140
yield node, node_key_filter
1272
1289
lines.append('%s\n' % (self._search_prefix,))
1273
1290
prefix_len = len(self._search_prefix)
1274
1291
for prefix, node in sorted(self._items.items()):
1275
if type(node) is tuple:
1292
if type(node) is StaticTuple:
1278
1295
key = node._key[0]
1282
1299
% (serialised, self._search_prefix))
1283
1300
lines.append(serialised[prefix_len:])
1284
1301
sha1, _, _ = store.add_lines((None,), (), lines)
1285
self._key = ("sha1:" + sha1,)
1302
self._key = StaticTuple("sha1:" + sha1,).intern()
1286
1303
_page_cache.add(self._key, ''.join(lines))
1287
1304
yield self._key
1438
1455
def __init__(self, store, new_root_keys, old_root_keys,
1439
1456
search_key_func, pb=None):
1457
# TODO: Should we add a StaticTuple barrier here? It would be nice to
1458
# force callers to use StaticTuple, because there will often be
1459
# lots of keys passed in here. And even if we cast it locally,
1460
# that just meanst that we will have *both* a StaticTuple and a
1461
# tuple() in memory, referring to the same object. (so a net
1462
# increase in memory, not a decrease.)
1440
1463
self._store = store
1441
1464
self._new_root_keys = new_root_keys
1442
1465
self._old_root_keys = old_root_keys
1444
1467
# All uninteresting chks that we have seen. By the time they are added
1445
1468
# here, they should be either fully ignored, or queued up for
1470
# TODO: This might grow to a large size if there are lots of merge
1471
# parents, etc. However, it probably doesn't scale to O(history)
1472
# like _processed_new_refs does.
1447
1473
self._all_old_chks = set(self._old_root_keys)
1448
1474
# All items that we have seen from the old_root_keys
1449
1475
self._all_old_items = set()
1450
1476
# These are interesting items which were either read, or already in the
1451
1477
# interesting queue (so we don't need to walk them again)
1478
# TODO: processed_new_refs becomes O(all_chks), consider switching to
1452
1480
self._processed_new_refs = set()
1453
1481
self._search_key_func = search_key_func
1466
1494
# this code. (We may want to evaluate saving the raw bytes into the
1467
1495
# page cache, which would allow a working tree update after the fetch
1468
1496
# to not have to read the bytes again.)
1497
as_st = StaticTuple.from_sequence
1469
1498
stream = self._store.get_record_stream(keys, 'unordered', True)
1470
1499
for record in stream:
1471
1500
if self._pb is not None:
1478
1507
if type(node) is InternalNode:
1479
1508
# Note we don't have to do node.refs() because we know that
1480
1509
# there are no children that have been pushed into this node
1510
# Note: Using as_st() here seemed to save 1.2MB, which would
1511
# indicate that we keep 100k prefix_refs around while
1512
# processing. They *should* be shorter lived than that...
1513
# It does cost us ~10s of processing time
1514
#prefix_refs = [as_st(item) for item in node._items.iteritems()]
1481
1515
prefix_refs = node._items.items()
1484
1518
prefix_refs = []
1519
# Note: We don't use a StaticTuple here. Profiling showed a
1520
# minor memory improvement (0.8MB out of 335MB peak 0.2%)
1521
# But a significant slowdown (15s / 145s, or 10%)
1485
1522
items = node._items.items()
1486
1523
yield record, node, prefix_refs, items
1495
1532
if p_r[1] not in all_old_chks]
1496
1533
new_refs = [p_r[1] for p_r in prefix_refs]
1497
1534
all_old_chks.update(new_refs)
1535
# TODO: This might be a good time to turn items into StaticTuple
1536
# instances and possibly intern them. However, this does not
1537
# impact 'initial branch' performance, so I'm not worrying
1498
1539
self._all_old_items.update(items)
1499
1540
# Queue up the uninteresting references
1500
1541
# Don't actually put them in the 'to-read' queue until we have
1553
1594
# current design allows for this, as callers will do the work
1554
1595
# to make the results unique. We might profile whether we
1555
1596
# gain anything by ensuring unique return values for items
1597
# TODO: This might be a good time to cast to StaticTuple, as
1598
# self._new_item_queue will hold the contents of multiple
1599
# records for an extended lifetime
1556
1600
new_items = [item for item in items
1557
1601
if item not in self._all_old_items]
1558
1602
self._new_item_queue.extend(new_items)
1584
1628
yield None, new_items
1585
1629
refs = refs.difference(all_old_chks)
1630
processed_new_refs.update(refs)
1632
# TODO: Using a SimpleSet for self._processed_new_refs and
1633
# saved as much as 10MB of peak memory. However, it requires
1634
# implementing a non-pyrex version.
1587
1635
next_refs = set()
1588
1636
next_refs_update = next_refs.update
1589
1637
# Inlining _read_nodes_from_store improves 'bzr branch bzr.dev'
1590
1638
# from 1m54s to 1m51s. Consider it.
1591
1639
for record, _, p_refs, items in self._read_nodes_from_store(refs):
1592
items = [item for item in items
1593
if item not in all_old_items]
1641
# using the 'if' check saves about 145s => 141s, when
1642
# streaming initial branch of Launchpad data.
1643
items = [item for item in items
1644
if item not in all_old_items]
1594
1645
yield record, items
1595
1646
next_refs_update([p_r[1] for p_r in p_refs])
1648
# set1.difference(set/dict) walks all of set1, and checks if it
1649
# exists in 'other'.
1650
# set1.difference(iterable) walks all of iterable, and does a
1651
# 'difference_update' on a clone of set1. Pick wisely based on the
1652
# expected sizes of objects.
1653
# in our case it is expected that 'new_refs' will always be quite
1596
1655
next_refs = next_refs.difference(all_old_chks)
1597
1656
next_refs = next_refs.difference(processed_new_refs)
1598
1657
processed_new_refs.update(next_refs)
1605
1664
self._old_queue = []
1606
1665
all_old_chks = self._all_old_chks
1607
1666
for record, _, prefix_refs, items in self._read_nodes_from_store(refs):
1667
# TODO: Use StaticTuple here?
1608
1668
self._all_old_items.update(items)
1609
1669
refs = [r for _,r in prefix_refs if r not in all_old_chks]
1610
1670
self._old_queue.extend(refs)
1661
1721
search_key_registry.register('hash-16-way', _search_key_16)
1662
1722
search_key_registry.register('hash-255-way', _search_key_255)
1725
def _check_key(key):
1726
"""Helper function to assert that a key is properly formatted.
1728
This generally shouldn't be used in production code, but it can be helpful
1731
if type(key) is not StaticTuple:
1732
raise TypeError('key %r is not StaticTuple but %s' % (key, type(key)))
1734
raise ValueError('key %r should have length 1, not %d' % (key, len(key),))
1735
if type(key[0]) is not str:
1736
raise TypeError('key %r should hold a str, not %r'
1737
% (key, type(key[0])))
1738
if not key[0].startswith('sha1:'):
1739
raise ValueError('key %r should point to a sha1:' % (key,))
added
removed
bzrlib/chk_map.py
