« back to all changes in this revision
Viewing changes to bzrlib/chk_map.py
- browse files at revision 3735.19.1
- compare with another revision
- compare with revision 2255.7.57
- download diff
- download tarball
- view history from revision 3735.19.1
- Committer: Ian Clatworthy
- Date: 2009-02-27 07:02:44 UTC
- mto: (3735.2.108 brisbane-core)
- mto: This revision was merged to the branch mainline in revision 4280.
- Revision ID: ian.clatworthy@canonical.com-20090227070244-anpzbyaxmjhmuegc
CHKMap cleanups
- files modified:
- bzrlib/chk_map.py
added
removed
bzrlib/chk_map.py
22
22
with internal nodes of 8-bit fan out; The key tuples are mapped to strings by
23
23
joining them by \x00, and \x00 padding shorter keys out to the length of the
24
24
longest key. Leaf nodes are packed as densely as possible, and internal nodes
25
are all and additional 8-bits wide leading to a sparse upper tree.
25
are all an additional 8-bits wide leading to a sparse upper tree.
26
26
27
27
Updates to a CHKMap are done preferentially via the apply_delta method, to
28
28
allow optimisation of the update operation; but individual map/unmap calls are
53
53
registry,
54
54
)
55
55
56
# approx 2MB
56
# approx 4MB
57
57
# If each line is 50 bytes, and you have 255 internal pages, with 255-way fan
58
58
# out, it takes 3.1MB to cache the layer.
59
59
_PAGE_CACHE_SIZE = 4*1024*1024
134
134
"""
135
135
for old, new, value in delta:
136
136
if old is not None and old != new:
137
# unmap
138
137
self.unmap(old)
139
138
for old, new, value in delta:
140
139
if new is not None:
141
# map
142
140
self.map(new, value)
143
141
return self._save()
144
142
148
146
# Demand-load the root
149
147
self._root_node = self._get_node(self._root_node)
150
148
# XXX: Shouldn't this be put into _deserialize?
149
# IGC: I'm pretty sure this next line is redundant and can go
151
150
self._root_node._search_key_func = self._search_key_func
152
151
153
152
def _get_node(self, node):
154
153
"""Get a node.
155
154
156
Node that this does not update the _items dict in objects containing a
155
Note that this does not update the _items dict in objects containing a
157
156
reference to this node. As such it does not prevent subsequent IO being
158
157
performed.
159
158
200
199
include_keys=include_keys))
201
200
else:
202
201
for key, value in sorted(node._items.iteritems()):
202
# IGC: Shouldn't prefix and indent be used below?
203
203
result.append(' %r %r' % (key, value))
204
204
return result
205
205
206
206
@classmethod
207
def from_dict(klass, store, initial_value, maximum_size=0, key_width=1):
207
def from_dict(klass, store, initial_value, maximum_size=0, key_width=1,
208
search_key_func=None):
208
209
"""Create a CHKMap in store with initial_value as the content.
209
210
210
211
:param store: The store to record initial_value in, a VersionedFiles
215
216
determines the size at which no new data is added to a single node.
216
217
:param key_width: The number of elements in each key_tuple being stored
217
218
in this map.
218
:return: The root chk of te resulting CHKMap.
219
:param search_key_func: A function mapping a key => bytes. These bytes
220
are then used by the internal nodes to split up leaf nodes into
221
multiple pages.
222
:return: The root chk of the resulting CHKMap.
219
223
"""
220
result = CHKMap(store, None)
224
result = CHKMap(store, None, search_key_func=search_key_func)
221
225
result._root_node.set_maximum_size(maximum_size)
222
226
result._root_node._key_width = key_width
223
227
delta = []
224
228
for key, value in initial_value.items():
225
229
delta.append((None, key, value))
226
result.apply_delta(delta)
227
return result._save()
230
return result.apply_delta(delta)
228
231
229
232
def iter_changes(self, basis):
230
233
"""Iterate over the changes between basis and self.
425
428
self._root_node.add_node(split, node)
426
429
427
430
def _node_key(self, node):
428
"""Get the key for a node whether its a tuple o r node."""
431
"""Get the key for a node whether it's a tuple or node."""
429
432
if type(node) == tuple:
430
433
return node
431
434
else:
465
468
# Current number of elements
466
469
self._len = 0
467
470
self._maximum_size = 0
468
self._key_width = 1
471
self._key_width = key_width
469
472
# current size in bytes
470
473
self._raw_size = 0
471
474
# The pointers/values this node has - meaning defined by child classes.
627
630
result._compute_search_prefix()
628
631
result._compute_serialised_prefix()
629
632
if len(bytes) != result._current_size():
630
import pdb; pdb.set_trace()
633
#import pdb; pdb.set_trace()
631
634
raise AssertionError('_current_size computed incorrectly')
632
635
return result
633
636
777
780
self._key = ("sha1:" + sha1,)
778
781
bytes = ''.join(lines)
779
782
if len(bytes) != self._current_size():
780
import pdb; pdb.set_trace()
783
#import pdb; pdb.set_trace()
781
784
raise AssertionError('Invalid _current_size')
782
785
_page_cache.add(self._key, bytes)
783
786
return [self._key]
821
824
serialised_keys = [self._serialise_key(key) for key in self._items]
822
825
self._common_serialised_prefix = self.common_prefix_for_keys(
823
826
serialised_keys)
827
return self._common_serialised_prefix
824
828
825
829
def unmap(self, store, key):
826
830
"""Unmap key from the node."""
855
859
else:
856
860
self._search_key_func = search_key_func
857
861
858
def __repr__(self):
859
items_str = sorted(self._items)
860
if len(items_str) > 20:
861
items_str = items_str[16] + '...]'
862
return '%s(key:%s len:%s size:%s max:%s prefix:%s items:%s)' % (
863
self.__class__.__name__, self._key, self._len, self._raw_size,
864
self._maximum_size, self._search_prefix, items_str)
865
866
862
def add_node(self, prefix, node):
867
863
"""Add a child node with prefix prefix, and node node.
868
864
Loggerhead is a web-based interface for Breezy
Version: 2.0.1