Rev 3812: Add functions for _search_key_16 and _search_key_255 and some basic tests for them. in http://bzr.arbash-meinel.com/branches/bzr/brisbane/hash_search_key

[John Arbash Meinel]

At http://bzr.arbash-meinel.com/branches/bzr/brisbane/hash_search_key

------------------------------------------------------------
revno: 3812
revision-id: john at arbash-meinel.com-20090121200529-a1di2ljywetnbaz0
parent: john at arbash-meinel.com-20090121193956-ijxjv8tslli5vpir
committer: John Arbash Meinel <john at arbash-meinel.com>
branch nick: hash_search_key
timestamp: Wed 2009-01-21 14:05:29 -0600
message:
  Add functions for _search_key_16 and _search_key_255 and some basic tests for them.
-------------- next part --------------
=== modified file 'bzrlib/chk_map.py'
--- a/bzrlib/chk_map.py	2009-01-21 19:39:56 +0000
+++ b/bzrlib/chk_map.py	2009-01-21 20:05:29 +0000
@@ -41,6 +41,9 @@
 
 from bzrlib import lazy_import
 lazy_import.lazy_import(globals(), """
+import zlib
+import struct
+
 from bzrlib import versionedfile
 """)
 from bzrlib import lru_cache
@@ -53,6 +56,21 @@
 _page_cache = lru_cache.LRUSizeCache(_PAGE_CACHE_SIZE)
 
 
+def _search_key_16(key):
+    """Map the key tuple into a search key string which has 16-way fan out."""
+    return '\x00'.join(['%08X' % abs(zlib.crc32(bit)) for bit in key])
+
+
+def _search_key_255(key):
+    """Map the key tuple into a search key string which has 255-way fan out.
+
+    We use 255-way because '\n' is used as a delimiter, and causes problems
+    while parsing.
+    """
+    bytes = '\x00'.join([struct.pack('>i', zlib.crc32(bit)) for bit in key])
+    return bytes.replace('\n', '_')
+
+
 class CHKMap(object):
     """A persistent map from string to string backed by a CHK store."""
 

=== modified file 'bzrlib/tests/test_chk_map.py'
--- a/bzrlib/tests/test_chk_map.py	2009-01-21 19:39:56 +0000
+++ b/bzrlib/tests/test_chk_map.py	2009-01-21 20:05:29 +0000
@@ -18,7 +18,11 @@
 
 from itertools import izip
 
-from bzrlib import chk_map, osutils
+from bzrlib import (
+    chk_map,
+    osutils,
+    tests,
+    )
 from bzrlib.chk_map import (
     CHKMap,
     InternalNode,
@@ -1063,6 +1067,41 @@
                              , chkmap._dump_tree())
 
 
+class TestSearchKeyFuncs(tests.TestCase):
+
+    def assertSearchKey16(self, expected, key):
+        self.assertEqual(expected, chk_map._search_key_16(key))
+
+    def assertSearchKey255(self, expected, key):
+        actual = chk_map._search_key_255(key)
+        self.assertEqual(expected, actual, 'actual: %r' % (actual,))
+
+    def test_simple_16(self):
+        self.assertSearchKey16('738C9ADF', ('foo',))
+        self.assertSearchKey16('738C9ADF\x00738C9ADF', ('foo', 'foo'))
+        self.assertSearchKey16('738C9ADF\x0076FF8CAA', ('foo', 'bar'))
+        self.assertSearchKey16('127D32EF', ('abcd',))
+
+    def test_simple_255(self):
+        self.assertSearchKey255('\x8cse!', ('foo',))
+        self.assertSearchKey255('\x8cse!\x00\x8cse!', ('foo', 'foo'))
+        self.assertSearchKey255('\x8cse!\x00v\xff\x8c\xaa', ('foo', 'bar'))
+        # The standard mapping for these would include '\n', so it should be
+        # mapped to '_'
+        self.assertSearchKey255('\xfdm\x93_\x00P_\x1bL', ('<', 'V'))
+
+    def test_255_does_not_include_newline(self):
+        # When mapping via _search_key_255, we should never have the '\n'
+        # character, but all other 255 values should be present
+        chars_used = set()
+        for char_in in range(256):
+            search_key = chk_map._search_key_255((chr(char_in),))
+            chars_used.update(search_key)
+        all_chars = set([chr(x) for x in range(256)])
+        unused_chars = all_chars.symmetric_difference(chars_used)
+        self.assertEqual(set('\n'), unused_chars)
+
+
 class TestLeafNode(TestCaseWithStore):
 
     def test_current_size_empty(self):