To get this branch, use:
bzr branch
http://gegoxaren.bato24.eu/bzr/brz/remove-bazaar
« back to all changes in this revision
Viewing changes to bzrlib/chk_map.py
- browse files at revision 4744.3.6
- compare with another revision
- compare with revision 1036
- download diff
- download tarball
- view history from revision 4744.3.6
- Committer: Andrew Bennetts
- Date: 2009-10-28 00:12:03 UTC
- mfrom: (4774 +trunk)
- mto: This revision was merged to the branch mainline in revision 4775.
- Revision ID: andrew.bennetts@canonical.com-20091028001203-m7lgs1wtnilgo3br
Merge lp:bzr, resolving NEWS conflict.
- files added:
- bzrlib/static_tuple.py
- bzrlib/tests/per_foreign_vcs
- bzrlib/tests/per_uifactory
- files modified:
- Makefile
added
removed
bzrlib/chk_map.py
52
52
registry,
53
53
trace,
54
54
)
55
from bzrlib.static_tuple import StaticTuple
55
56
56
57
# approx 4MB
57
58
# If each line is 50 bytes, and you have 255 internal pages, with 255-way fan
83
84
class CHKMap(object):
84
85
"""A persistent map from string to string backed by a CHK store."""
85
86
87
__slots__ = ('_store', '_root_node', '_search_key_func')
88
86
89
def __init__(self, store, root_key, search_key_func=None):
87
90
"""Create a CHKMap object.
88
91
112
115
"""
113
116
delete_count = 0
114
117
# Check preconditions first.
115
new_items = set([key for (old, key, value) in delta if key is not None
116
and old is None])
118
as_st = StaticTuple.from_sequence
119
new_items = set([as_st(key) for (old, key, value) in delta
120
if key is not None and old is None])
117
121
existing_new = list(self.iteritems(key_filter=new_items))
118
122
if existing_new:
119
123
raise errors.InconsistentDeltaDelta(delta,
133
137
134
138
def _ensure_root(self):
135
139
"""Ensure that the root node is an object not a key."""
136
if type(self._root_node) is tuple:
140
if type(self._root_node) is StaticTuple:
137
141
# Demand-load the root
138
142
self._root_node = self._get_node(self._root_node)
139
143
147
151
:param node: A tuple key or node object.
148
152
:return: A node object.
149
153
"""
150
if type(node) is tuple:
154
if type(node) is StaticTuple:
151
155
bytes = self._read_bytes(node)
152
156
return _deserialise(bytes, node,
153
157
search_key_func=self._search_key_func)
194
198
for key, value in sorted(node._items.iteritems()):
195
199
# Don't use prefix nor indent here to line up when used in
196
200
# tests in conjunction with assertEqualDiff
197
result.append(' %r %r' % (key, value))
201
result.append(' %r %r' % (tuple(key), value))
198
202
return result
199
203
200
204
@classmethod
218
222
root_key = klass._create_directly(store, initial_value,
219
223
maximum_size=maximum_size, key_width=key_width,
220
224
search_key_func=search_key_func)
225
if type(root_key) is not StaticTuple:
226
raise AssertionError('we got a %s instead of a StaticTuple'
227
% (type(root_key),))
221
228
return root_key
222
229
223
230
@classmethod
238
245
node = LeafNode(search_key_func=search_key_func)
239
246
node.set_maximum_size(maximum_size)
240
247
node._key_width = key_width
241
node._items = dict(initial_value)
248
as_st = StaticTuple.from_sequence
249
node._items = dict([(as_st(key), val) for key, val
250
in initial_value.iteritems()])
242
251
node._raw_size = sum([node._key_value_len(key, value)
243
for key,value in initial_value.iteritems()])
252
for key,value in node._items.iteritems()])
244
253
node._len = len(node._items)
245
254
node._compute_search_prefix()
246
255
node._compute_serialised_prefix()
482
491
def iteritems(self, key_filter=None):
483
492
"""Iterate over the entire CHKMap's contents."""
484
493
self._ensure_root()
494
if key_filter is not None:
495
as_st = StaticTuple.from_sequence
496
key_filter = [as_st(key) for key in key_filter]
485
497
return self._root_node.iteritems(self._store, key_filter=key_filter)
486
498
487
499
def key(self):
488
500
"""Return the key for this map."""
489
if type(self._root_node) is tuple:
501
if type(self._root_node) is StaticTuple:
490
502
return self._root_node
491
503
else:
492
504
return self._root_node._key
501
513
:param key: A key to map.
502
514
:param value: The value to assign to key.
503
515
"""
516
key = StaticTuple.from_sequence(key)
504
517
# Need a root object.
505
518
self._ensure_root()
506
519
prefix, node_details = self._root_node.map(self._store, key, value)
517
530
def _node_key(self, node):
518
531
"""Get the key for a node whether it's a tuple or node."""
519
532
if type(node) is tuple:
533
node = StaticTuple.from_sequence(node)
534
if type(node) is StaticTuple:
520
535
return node
521
536
else:
522
537
return node._key
523
538
524
539
def unmap(self, key, check_remap=True):
525
540
"""remove key from the map."""
541
key = StaticTuple.from_sequence(key)
526
542
self._ensure_root()
527
543
if type(self._root_node) is InternalNode:
528
544
unmapped = self._root_node.unmap(self._store, key,
542
558
543
559
:return: The key of the root node.
544
560
"""
545
if type(self._root_node) is tuple:
561
if type(self._root_node) is StaticTuple:
546
562
# Already saved.
547
563
return self._root_node
548
564
keys = list(self._root_node.serialise(self._store))
556
572
adding the header bytes, and without prefix compression.
557
573
"""
558
574
575
__slots__ = ('_key', '_len', '_maximum_size', '_key_width',
576
'_raw_size', '_items', '_search_prefix', '_search_key_func'
577
)
578
559
579
def __init__(self, key_width=1):
560
580
"""Create a node.
561
581
650
670
the key/value pairs.
651
671
"""
652
672
673
__slots__ = ('_common_serialised_prefix', '_serialise_key')
674
653
675
def __init__(self, search_key_func=None):
654
676
Node.__init__(self)
655
677
# All of the keys in this leaf node share this common prefix
873
895
lines.append(serialized[prefix_len:])
874
896
lines.extend(value_lines)
875
897
sha1, _, _ = store.add_lines((None,), (), lines)
876
self._key = ("sha1:" + sha1,)
898
self._key = StaticTuple("sha1:" + sha1,).intern()
877
899
bytes = ''.join(lines)
878
900
if len(bytes) != self._current_size():
879
901
raise AssertionError('Invalid _current_size')
947
969
LeafNode or InternalNode.
948
970
"""
949
971
972
__slots__ = ('_node_width',)
973
950
974
def __init__(self, prefix='', search_key_func=None):
951
975
Node.__init__(self)
952
976
# The size of an internalnode with default values and no children.
994
1018
:param key: The key that the serialised node has.
995
1019
:return: An InternalNode instance.
996
1020
"""
1021
if type(key) is not StaticTuple:
1022
raise AssertionError('deserialise should be called with a'
1023
' StaticTuple not %s' % (type(key),))
997
1024
return _deserialise_internal_node(bytes, key,
998
1025
search_key_func=search_key_func)
999
1026
1024
1051
# for whatever we are missing
1025
1052
shortcut = True
1026
1053
for prefix, node in self._items.iteritems():
1027
if node.__class__ is tuple:
1054
if node.__class__ is StaticTuple:
1028
1055
keys[node] = (prefix, None)
1029
1056
else:
1030
1057
yield node, None
1059
1086
# A given key can only match 1 child node, if it isn't
1060
1087
# there, then we can just return nothing
1061
1088
return
1062
if node.__class__ is tuple:
1089
if node.__class__ is StaticTuple:
1063
1090
keys[node] = (search_prefix, [key])
1064
1091
else:
1065
1092
# This is loaded, and the only thing that can match,
1092
1119
# We can ignore this one
1093
1120
continue
1094
1121
node_key_filter = prefix_to_keys[search_prefix]
1095
if node.__class__ is tuple:
1122
if node.__class__ is StaticTuple:
1096
1123
keys[node] = (search_prefix, node_key_filter)
1097
1124
else:
1098
1125
yield node, node_key_filter
1107
1134
if sub_prefix in length_filter:
1108
1135
node_key_filter.extend(prefix_to_keys[sub_prefix])
1109
1136
if node_key_filter: # this key matched something, yield it
1110
if node.__class__ is tuple:
1137
if node.__class__ is StaticTuple:
1111
1138
keys[node] = (prefix, node_key_filter)
1112
1139
else:
1113
1140
yield node, node_key_filter
1245
1272
:return: An iterable of the keys inserted by this operation.
1246
1273
"""
1247
1274
for node in self._items.itervalues():
1248
if type(node) is tuple:
1275
if type(node) is StaticTuple:
1249
1276
# Never deserialised.
1250
1277
continue
1251
1278
if node._key is not None:
1262
1289
lines.append('%s\n' % (self._search_prefix,))
1263
1290
prefix_len = len(self._search_prefix)
1264
1291
for prefix, node in sorted(self._items.items()):
1265
if type(node) is tuple:
1292
if type(node) is StaticTuple:
1266
1293
key = node[0]
1267
1294
else:
1268
1295
key = node._key[0]
1272
1299
% (serialised, self._search_prefix))
1273
1300
lines.append(serialised[prefix_len:])
1274
1301
sha1, _, _ = store.add_lines((None,), (), lines)
1275
self._key = ("sha1:" + sha1,)
1302
self._key = StaticTuple("sha1:" + sha1,).intern()
1276
1303
_page_cache.add(self._key, ''.join(lines))
1277
1304
yield self._key
1278
1305
1307
1334
raise AssertionError("unserialised nodes have no refs.")
1308
1335
refs = []
1309
1336
for value in self._items.itervalues():
1310
if type(value) is tuple:
1337
if type(value) is StaticTuple:
1311
1338
refs.append(value)
1312
1339
else:
1313
1340
refs.append(value.key())
1427
1454
1428
1455
def __init__(self, store, new_root_keys, old_root_keys,
1429
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.)
1430
1463
self._store = store
1431
1464
self._new_root_keys = new_root_keys
1432
1465
self._old_root_keys = old_root_keys
1434
1467
# All uninteresting chks that we have seen. By the time they are added
1435
1468
# here, they should be either fully ignored, or queued up for
1436
1469
# processing
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.
1437
1473
self._all_old_chks = set(self._old_root_keys)
1438
1474
# All items that we have seen from the old_root_keys
1439
1475
self._all_old_items = set()
1440
1476
# These are interesting items which were either read, or already in the
1441
1477
# interesting queue (so we don't need to walk them again)
1478
# TODO: processed_new_refs becomes O(all_chks), consider switching to
1479
# SimpleSet here.
1442
1480
self._processed_new_refs = set()
1443
1481
self._search_key_func = search_key_func
1444
1482
1456
1494
# this code. (We may want to evaluate saving the raw bytes into the
1457
1495
# page cache, which would allow a working tree update after the fetch
1458
1496
# to not have to read the bytes again.)
1497
as_st = StaticTuple.from_sequence
1459
1498
stream = self._store.get_record_stream(keys, 'unordered', True)
1460
1499
for record in stream:
1461
1500
if self._pb is not None:
1468
1507
if type(node) is InternalNode:
1469
1508
# Note we don't have to do node.refs() because we know that
1470
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()]
1471
1515
prefix_refs = node._items.items()
1472
1516
items = []
1473
1517
else:
1474
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%)
1475
1522
items = node._items.items()
1476
1523
yield record, node, prefix_refs, items
1477
1524
1485
1532
if p_r[1] not in all_old_chks]
1486
1533
new_refs = [p_r[1] for p_r in prefix_refs]
1487
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
1538
# about this yet
1488
1539
self._all_old_items.update(items)
1489
1540
# Queue up the uninteresting references
1490
1541
# Don't actually put them in the 'to-read' queue until we have
1543
1594
# current design allows for this, as callers will do the work
1544
1595
# to make the results unique. We might profile whether we
1545
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
1546
1600
new_items = [item for item in items
1547
1601
if item not in self._all_old_items]
1548
1602
self._new_item_queue.extend(new_items)
1573
1627
if new_items:
1574
1628
yield None, new_items
1575
1629
refs = refs.difference(all_old_chks)
1630
processed_new_refs.update(refs)
1576
1631
while 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.
1577
1635
next_refs = set()
1578
1636
next_refs_update = next_refs.update
1579
1637
# Inlining _read_nodes_from_store improves 'bzr branch bzr.dev'
1580
1638
# from 1m54s to 1m51s. Consider it.
1581
1639
for record, _, p_refs, items in self._read_nodes_from_store(refs):
1582
items = [item for item in items
1583
if item not in all_old_items]
1640
if 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]
1584
1645
yield record, items
1585
1646
next_refs_update([p_r[1] for p_r in p_refs])
1647
del 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
1654
# small.
1586
1655
next_refs = next_refs.difference(all_old_chks)
1587
1656
next_refs = next_refs.difference(processed_new_refs)
1588
1657
processed_new_refs.update(next_refs)
1595
1664
self._old_queue = []
1596
1665
all_old_chks = self._all_old_chks
1597
1666
for record, _, prefix_refs, items in self._read_nodes_from_store(refs):
1667
# TODO: Use StaticTuple here?
1598
1668
self._all_old_items.update(items)
1599
1669
refs = [r for _,r in prefix_refs if r not in all_old_chks]
1600
1670
self._old_queue.extend(refs)
1650
1720
)
1651
1721
search_key_registry.register('hash-16-way', _search_key_16)
1652
1722
search_key_registry.register('hash-255-way', _search_key_255)
1723
1724
1725
def _check_key(key):
1726
"""Helper function to assert that a key is properly formatted.
1727
1728
This generally shouldn't be used in production code, but it can be helpful
1729
to debug problems.
1730
"""
1731
if type(key) is not StaticTuple:
1732
raise TypeError('key %r is not StaticTuple but %s' % (key, type(key)))
1733
if len(key) != 1:
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,))
1740
1741
Loggerhead is a web-based interface for Breezy
Version: 2.0.2.dev0