« back to all changes in this revision
Viewing changes to bzrlib/tests/test_chk_map.py
- browse files at revision 4603.1.19
- compare with another revision
- compare with revision 4964
- download diff
- download tarball
- view history from revision 4603.1.19
- Committer: Aaron Bentley
- Date: 2009-10-31 00:44:22 UTC
- mfrom: (4778 +trunk)
- mto: (4603.1.22 shelve-editor)
- mto: This revision was merged to the branch mainline in revision 4795.
- Revision ID: aaron@aaronbentley.com-20091031004422-i2qciijx2ik4gctc
Merged bzr.dev into shelve-editor.
- files added:
- bzrlib/cleanup.py
- files modified:
- Makefile
added
removed
bzrlib/tests/test_chk_map.py
31
31
LeafNode,
32
32
Node,
33
33
)
34
from bzrlib.static_tuple import StaticTuple
34
35
35
36
36
37
class TestNode(tests.TestCase):
831
832
# 'ab' and 'ac' nodes
832
833
chkmap.map(('aad',), 'v')
833
834
self.assertIsInstance(chkmap._root_node._items['aa'], InternalNode)
834
self.assertIsInstance(chkmap._root_node._items['ab'], tuple)
835
self.assertIsInstance(chkmap._root_node._items['ac'], tuple)
835
self.assertIsInstance(chkmap._root_node._items['ab'], StaticTuple)
836
self.assertIsInstance(chkmap._root_node._items['ac'], StaticTuple)
836
837
# Unmapping 'acd' can notice that 'aa' is an InternalNode and not have
837
838
# to map in 'ab'
838
839
chkmap.unmap(('acd',))
839
840
self.assertIsInstance(chkmap._root_node._items['aa'], InternalNode)
840
self.assertIsInstance(chkmap._root_node._items['ab'], tuple)
841
self.assertIsInstance(chkmap._root_node._items['ab'], StaticTuple)
841
842
842
843
def test_unmap_without_fitting_doesnt_page_in(self):
843
844
store = self.get_chk_bytes()
860
861
chkmap.map(('aaf',), 'v')
861
862
# At this point, the previous nodes should not be paged in, but the
862
863
# newly added nodes would be
863
self.assertIsInstance(chkmap._root_node._items['aaa'], tuple)
864
self.assertIsInstance(chkmap._root_node._items['aab'], tuple)
864
self.assertIsInstance(chkmap._root_node._items['aaa'], StaticTuple)
865
self.assertIsInstance(chkmap._root_node._items['aab'], StaticTuple)
865
866
self.assertIsInstance(chkmap._root_node._items['aac'], LeafNode)
866
867
self.assertIsInstance(chkmap._root_node._items['aad'], LeafNode)
867
868
self.assertIsInstance(chkmap._root_node._items['aae'], LeafNode)
869
870
# Now unmapping one of the new nodes will use only the already-paged-in
870
871
# nodes to determine that we don't need to do more.
871
872
chkmap.unmap(('aaf',))
872
self.assertIsInstance(chkmap._root_node._items['aaa'], tuple)
873
self.assertIsInstance(chkmap._root_node._items['aab'], tuple)
873
self.assertIsInstance(chkmap._root_node._items['aaa'], StaticTuple)
874
self.assertIsInstance(chkmap._root_node._items['aab'], StaticTuple)
874
875
self.assertIsInstance(chkmap._root_node._items['aac'], LeafNode)
875
876
self.assertIsInstance(chkmap._root_node._items['aad'], LeafNode)
876
877
self.assertIsInstance(chkmap._root_node._items['aae'], LeafNode)
897
898
chkmap.map(('aad',), 'v')
898
899
# At this point, the previous nodes should not be paged in, but the
899
900
# newly added node would be
900
self.assertIsInstance(chkmap._root_node._items['aaa'], tuple)
901
self.assertIsInstance(chkmap._root_node._items['aab'], tuple)
902
self.assertIsInstance(chkmap._root_node._items['aac'], tuple)
901
self.assertIsInstance(chkmap._root_node._items['aaa'], StaticTuple)
902
self.assertIsInstance(chkmap._root_node._items['aab'], StaticTuple)
903
self.assertIsInstance(chkmap._root_node._items['aac'], StaticTuple)
903
904
self.assertIsInstance(chkmap._root_node._items['aad'], LeafNode)
904
905
# Unmapping the new node will check the existing nodes to see if they
905
906
# would fit.
937
938
chkmap.map(('aad',), 'v')
938
939
# At this point, the previous nodes should not be paged in, but the
939
940
# newly added node would be
940
self.assertIsInstance(chkmap._root_node._items['aaa'], tuple)
941
self.assertIsInstance(chkmap._root_node._items['aab'], tuple)
942
self.assertIsInstance(chkmap._root_node._items['aac'], tuple)
941
self.assertIsInstance(chkmap._root_node._items['aaa'], StaticTuple)
942
self.assertIsInstance(chkmap._root_node._items['aab'], StaticTuple)
943
self.assertIsInstance(chkmap._root_node._items['aac'], StaticTuple)
943
944
self.assertIsInstance(chkmap._root_node._items['aad'], LeafNode)
944
945
# Now clear the page cache, and only include 2 of the children in the
945
946
# cache
954
955
# Unmapping the new node will check the nodes from the page cache
955
956
# first, and not have to read in 'aaa'
956
957
chkmap.unmap(('aad',))
957
self.assertIsInstance(chkmap._root_node._items['aaa'], tuple)
958
self.assertIsInstance(chkmap._root_node._items['aaa'], StaticTuple)
958
959
self.assertIsInstance(chkmap._root_node._items['aab'], LeafNode)
959
960
self.assertIsInstance(chkmap._root_node._items['aac'], LeafNode)
960
961
974
975
chkmap.map(('aaf',), 'val')
975
976
# At this point, the previous nodes should not be paged in, but the
976
977
# newly added node would be
977
self.assertIsInstance(chkmap._root_node._items['aaa'], tuple)
978
self.assertIsInstance(chkmap._root_node._items['aab'], tuple)
979
self.assertIsInstance(chkmap._root_node._items['aac'], tuple)
978
self.assertIsInstance(chkmap._root_node._items['aaa'], StaticTuple)
979
self.assertIsInstance(chkmap._root_node._items['aab'], StaticTuple)
980
self.assertIsInstance(chkmap._root_node._items['aac'], StaticTuple)
980
981
self.assertIsInstance(chkmap._root_node._items['aad'], LeafNode)
981
982
self.assertIsInstance(chkmap._root_node._items['aae'], LeafNode)
982
983
self.assertIsInstance(chkmap._root_node._items['aaf'], LeafNode)
984
985
# Unmapping a new node will see the other nodes that are already in
985
986
# memory, and not need to page in anything else
986
987
chkmap.unmap(('aad',))
987
self.assertIsInstance(chkmap._root_node._items['aaa'], tuple)
988
self.assertIsInstance(chkmap._root_node._items['aab'], tuple)
989
self.assertIsInstance(chkmap._root_node._items['aac'], tuple)
988
self.assertIsInstance(chkmap._root_node._items['aaa'], StaticTuple)
989
self.assertIsInstance(chkmap._root_node._items['aab'], StaticTuple)
990
self.assertIsInstance(chkmap._root_node._items['aac'], StaticTuple)
990
991
self.assertIsInstance(chkmap._root_node._items['aae'], LeafNode)
991
992
self.assertIsInstance(chkmap._root_node._items['aaf'], LeafNode)
992
993
1031
1032
{('a',): 'content here', ('b',): 'more content'},
1032
1033
chk_bytes=basis._store, maximum_size=10)
1033
1034
list(target.iter_changes(basis))
1034
self.assertIsInstance(target._root_node, tuple)
1035
self.assertIsInstance(basis._root_node, tuple)
1035
self.assertIsInstance(target._root_node, StaticTuple)
1036
self.assertIsInstance(basis._root_node, StaticTuple)
1036
1037
1037
1038
def test_iter_changes_ab_ab_changed_values_shown(self):
1038
1039
basis = self._get_map({('a',): 'content here', ('b',): 'more content'},
1144
1145
1145
1146
def test_iteritems_keys_prefixed_by_2_width_nodes_hashed(self):
1146
1147
search_key_func = chk_map.search_key_registry.get('hash-16-way')
1147
self.assertEqual('E8B7BE43\x00E8B7BE43', search_key_func(('a', 'a')))
1148
self.assertEqual('E8B7BE43\x0071BEEFF9', search_key_func(('a', 'b')))
1149
self.assertEqual('71BEEFF9\x0000000000', search_key_func(('b', '')))
1148
self.assertEqual('E8B7BE43\x00E8B7BE43',
1149
search_key_func(StaticTuple('a', 'a')))
1150
self.assertEqual('E8B7BE43\x0071BEEFF9',
1151
search_key_func(StaticTuple('a', 'b')))
1152
self.assertEqual('71BEEFF9\x0000000000',
1153
search_key_func(StaticTuple('b', '')))
1150
1154
chkmap = self._get_map(
1151
1155
{("a","a"):"content here", ("a", "b",):"more content",
1152
1156
("b", ""): 'boring content'},
1449
1453
, chkmap._dump_tree())
1450
1454
1451
1455
1452
class TestSearchKeyFuncs(tests.TestCase):
1453
1454
def assertSearchKey16(self, expected, key):
1455
self.assertEqual(expected, chk_map._search_key_16(key))
1456
1457
def assertSearchKey255(self, expected, key):
1458
actual = chk_map._search_key_255(key)
1459
self.assertEqual(expected, actual, 'actual: %r' % (actual,))
1460
1461
def test_simple_16(self):
1462
self.assertSearchKey16('8C736521', ('foo',))
1463
self.assertSearchKey16('8C736521\x008C736521', ('foo', 'foo'))
1464
self.assertSearchKey16('8C736521\x0076FF8CAA', ('foo', 'bar'))
1465
self.assertSearchKey16('ED82CD11', ('abcd',))
1466
1467
def test_simple_255(self):
1468
self.assertSearchKey255('\x8cse!', ('foo',))
1469
self.assertSearchKey255('\x8cse!\x00\x8cse!', ('foo', 'foo'))
1470
self.assertSearchKey255('\x8cse!\x00v\xff\x8c\xaa', ('foo', 'bar'))
1471
# The standard mapping for these would include '\n', so it should be
1472
# mapped to '_'
1473
self.assertSearchKey255('\xfdm\x93_\x00P_\x1bL', ('<', 'V'))
1474
1475
def test_255_does_not_include_newline(self):
1476
# When mapping via _search_key_255, we should never have the '\n'
1477
# character, but all other 255 values should be present
1478
chars_used = set()
1479
for char_in in range(256):
1480
search_key = chk_map._search_key_255((chr(char_in),))
1481
chars_used.update(search_key)
1482
all_chars = set([chr(x) for x in range(256)])
1483
unused_chars = all_chars.symmetric_difference(chars_used)
1484
self.assertEqual(set('\n'), unused_chars)
1485
1486
1487
1456
class TestLeafNode(TestCaseWithStore):
1488
1457
1489
1458
def test_current_size_empty(self):
1908
1877
search_key_func = chk_map.search_key_registry.get('hash-255-way')
1909
1878
node = InternalNode(search_key_func=search_key_func)
1910
1879
leaf1 = LeafNode(search_key_func=search_key_func)
1911
leaf1.map(None, ('foo bar',), 'quux')
1880
leaf1.map(None, StaticTuple('foo bar',), 'quux')
1912
1881
leaf2 = LeafNode(search_key_func=search_key_func)
1913
leaf2.map(None, ('strange',), 'beast')
1914
self.assertEqual('\xbeF\x014', search_key_func(('foo bar',)))
1915
self.assertEqual('\x85\xfa\xf7K', search_key_func(('strange',)))
1882
leaf2.map(None, StaticTuple('strange',), 'beast')
1883
self.assertEqual('\xbeF\x014', search_key_func(StaticTuple('foo bar',)))
1884
self.assertEqual('\x85\xfa\xf7K', search_key_func(StaticTuple('strange',)))
1916
1885
node.add_node("\xbe", leaf1)
1917
1886
# This sets up a path that should not be followed - it will error if
1918
1887
# the code tries to.
1919
1888
node._items['\xbe'] = None
1920
1889
node.add_node("\x85", leaf2)
1921
1890
self.assertEqual([(('strange',), 'beast')],
1922
sorted(node.iteritems(None, [('strange',), ('weird',)])))
1891
sorted(node.iteritems(None, [StaticTuple('strange',),
1892
StaticTuple('weird',)])))
1923
1893
1924
1894
def test_iteritems_partial_empty(self):
1925
1895
node = InternalNode()
1932
1902
# Ensure test validity: nothing paged in below the root.
1933
1903
self.assertEqual(2,
1934
1904
len([value for value in node._items.values()
1935
if type(value) == tuple]))
1905
if type(value) is StaticTuple]))
1936
1906
# now, mapping to k3 should add a k3 leaf
1937
1907
prefix, nodes = node.map(None, ('k3',), 'quux')
1938
1908
self.assertEqual("k", prefix)
1971
1941
# Ensure test validity: nothing paged in below the root.
1972
1942
self.assertEqual(2,
1973
1943
len([value for value in node._items.values()
1974
if type(value) == tuple]))
1944
if type(value) is StaticTuple]))
1975
1945
# now, mapping to k23 causes k22 ('k2' in node) to split into k22 and
1976
1946
# k23, which for simplicity in the current implementation generates
1977
1947
# a new internal node between node, and k22/k23.
2016
1986
node = InternalNode(search_key_func=search_key_func)
2017
1987
node._key_width = 2
2018
1988
node._node_width = 4
2019
self.assertEqual('E8B7BE43\x0071BEEFF9', search_key_func(('a', 'b')))
2020
self.assertEqual('E8B7', node._search_prefix_filter(('a', 'b')))
2021
self.assertEqual('E8B7', node._search_prefix_filter(('a',)))
1989
self.assertEqual('E8B7BE43\x0071BEEFF9', search_key_func(
1990
StaticTuple('a', 'b')))
1991
self.assertEqual('E8B7', node._search_prefix_filter(
1992
StaticTuple('a', 'b')))
1993
self.assertEqual('E8B7', node._search_prefix_filter(
1994
StaticTuple('a',)))
2022
1995
2023
1996
def test_unmap_k23_from_k1_k22_k23_gives_k1_k22_tree_new(self):
2024
1997
chkmap = self._get_map(
Loggerhead is a web-based interface for Breezy
Version: 2.0.1