Rev 3808: Add tests that LeafNodes track the common prefix for both their lookup keys in http://bzr.arbash-meinel.com/branches/bzr/brisbane/prefix
John Arbash Meinel
john at arbash-meinel.com
Sat Dec 13 00:01:06 GMT 2008
At http://bzr.arbash-meinel.com/branches/bzr/brisbane/prefix
------------------------------------------------------------
revno: 3808
revision-id: john at arbash-meinel.com-20081213000100-kthnsue12wcfm7ea
parent: john at arbash-meinel.com-20081212233830-bibp9nqi2pgpvt53
committer: John Arbash Meinel <john at arbash-meinel.com>
branch nick: prefix
timestamp: Fri 2008-12-12 18:01:00 -0600
message:
Add tests that LeafNodes track the common prefix for both their lookup keys
and for their serialized keys.
-------------- next part --------------
=== modified file 'bzrlib/chk_map.py'
--- a/bzrlib/chk_map.py 2008-12-12 23:38:30 +0000
+++ b/bzrlib/chk_map.py 2008-12-13 00:01:00 +0000
@@ -381,7 +381,11 @@
class Node(object):
- """Base class defining the protocol for CHK Map nodes."""
+ """Base class defining the protocol for CHK Map nodes.
+
+ :ivar _raw_size: The total size of the serialized key:value data, before
+ adding the header bytes, and without prefix compression.
+ """
def __init__(self, key_width=1):
"""Create a node.
@@ -394,7 +398,7 @@
self._maximum_size = 0
self._key_width = 1
# current size in bytes
- self._size = 0
+ self._raw_size = 0
# The pointers/values this node has - meaning defined by child classes.
self._items = {}
# The common lookup prefix
@@ -405,7 +409,7 @@
if len(items_str) > 20:
items_str = items_str[16] + '...]'
return '%s(key:%s len:%s size:%s max:%s prefix:%s items:%s)' % (
- self.__class__.__name__, self._key, self._len, self._size,
+ self.__class__.__name__, self._key, self._len, self._raw_size,
self._maximum_size, self._lookup_prefix, items_str)
def key(self):
@@ -487,14 +491,14 @@
def _current_size(self):
"""Answer the current serialised size of this node.
- This differs from self._size in that it includes the bytes used for the
- header.
+ This differs from self._raw_size in that it includes the bytes used for
+ the header.
"""
return (12 # bytes overhead for the header and separators
+ len(str(self._len))
+ len(str(self._key_width))
+ len(str(self._maximum_size))
- + self._size)
+ + self._raw_size)
@classmethod
def deserialise(klass, bytes, key):
@@ -521,7 +525,8 @@
result._maximum_size = maximum_size
result._key = key
result._key_width = width
- result._size = len(bytes)
+ # XXX: This will change when we have prefix compression
+ result._raw_size = len(bytes)
result._compute_lookup_prefix()
result._compute_serialised_prefix()
return result
@@ -564,7 +569,7 @@
:return: True if adding this node should cause us to split.
"""
self._items[key] = value
- self._size += self._key_value_len(key, value)
+ self._raw_size += self._key_value_len(key, value)
self._len += 1
serialised_key = self._serialise_key(key)
if self._common_serialised_prefix is None:
@@ -621,7 +626,7 @@
def map(self, store, key, value):
"""Map key to value."""
if key in self._items:
- self._size -= self._key_value_len(key, self._items[key])
+ self._raw_size -= self._key_value_len(key, self._items[key])
self._len -= 1
self._key = None
if self._map_no_split(key, value):
@@ -676,7 +681,7 @@
def unmap(self, store, key):
"""Unmap key from the node."""
- self._size -= self._key_value_len(key, self._items[key])
+ self._raw_size -= self._key_value_len(key, self._items[key])
self._len -= 1
del self._items[key]
self._key = None
@@ -699,7 +704,6 @@
def __init__(self, prefix=''):
Node.__init__(self)
# The size of an internalnode with default values and no children.
- # self._size = 12
# How many octets key prefixes within this node are.
self._node_width = 0
self._lookup_prefix = prefix
@@ -709,7 +713,7 @@
if len(items_str) > 20:
items_str = items_str[16] + '...]'
return '%s(key:%s len:%s size:%s max:%s prefix:%s items:%s)' % (
- self.__class__.__name__, self._key, self._len, self._size,
+ self.__class__.__name__, self._key, self._len, self._raw_size,
self._maximum_size, self._lookup_prefix, items_str)
def add_node(self, prefix, node):
@@ -730,7 +734,7 @@
def _current_size(self):
"""Answer the current serialised size of this node."""
- return (self._size + len(str(self._len)) + len(str(self._key_width)) +
+ return (self._raw_size + len(str(self._len)) + len(str(self._key_width)) +
len(str(self._maximum_size)))
@classmethod
@@ -757,7 +761,9 @@
result._maximum_size = maximum_size
result._key = key
result._key_width = width
- result._size = len(bytes)
+ # XXX: InternalNodes don't really care about their size, and this will
+ # change if we add prefix compression
+ result._raw_size = None # len(bytes)
result._node_width = len(prefix)
result._compute_lookup_prefix()
return result
=== modified file 'bzrlib/tests/test_chk_map.py'
--- a/bzrlib/tests/test_chk_map.py 2008-12-12 23:38:30 +0000
+++ b/bzrlib/tests/test_chk_map.py 2008-12-13 00:01:00 +0000
@@ -1018,6 +1018,47 @@
self.assertEqual({}, self.to_dict(node, None))
self.assertEqual(0, len(node))
+ def test_map_maintains_common_prefixes(self):
+ node = LeafNode()
+ node._key_width = 2
+ node.map(None, ("foo bar", "baz"), "baz quux")
+ self.assertEqual('foo bar\x00baz', node._lookup_prefix)
+ self.assertEqual('foo bar\x00baz', node._common_serialised_prefix)
+ node.map(None, ("foo bar", "bing"), "baz quux")
+ self.assertEqual('foo bar\x00b', node._lookup_prefix)
+ self.assertEqual('foo bar\x00b', node._common_serialised_prefix)
+ node.map(None, ("fool", "baby"), "baz quux")
+ self.assertEqual('foo', node._lookup_prefix)
+ self.assertEqual('foo', node._common_serialised_prefix)
+ node.map(None, ("foo bar", "baz"), "replaced")
+ self.assertEqual('foo', node._lookup_prefix)
+ self.assertEqual('foo', node._common_serialised_prefix)
+ node.map(None, ("very", "different"), "value")
+ self.assertEqual('', node._lookup_prefix)
+ self.assertEqual('', node._common_serialised_prefix)
+
+ def test_unmap_maintains_common_prefixes(self):
+ node = LeafNode()
+ node._key_width = 2
+ node.map(None, ("foo bar", "baz"), "baz quux")
+ node.map(None, ("foo bar", "bing"), "baz quux")
+ node.map(None, ("fool", "baby"), "baz quux")
+ node.map(None, ("very", "different"), "value")
+ self.assertEqual('', node._lookup_prefix)
+ self.assertEqual('', node._common_serialised_prefix)
+ node.unmap(None, ("very", "different"))
+ self.assertEqual("foo", node._lookup_prefix)
+ self.assertEqual("foo", node._common_serialised_prefix)
+ node.unmap(None, ("fool", "baby"))
+ self.assertEqual('foo bar\x00b', node._lookup_prefix)
+ self.assertEqual('foo bar\x00b', node._common_serialised_prefix)
+ node.unmap(None, ("foo bar", "baz"))
+ self.assertEqual('foo bar\x00bing', node._lookup_prefix)
+ self.assertEqual('foo bar\x00bing', node._common_serialised_prefix)
+ node.unmap(None, ("foo bar", "bing"))
+ self.assertEqual('', node._lookup_prefix)
+ self.assertEqual('', node._common_serialised_prefix)
+
class TestInternalNode(TestCaseWithStore):
More information about the bazaar-commits
mailing list