Rev 2636: Create an adapter between indices with differing key lengths. in http://people.ubuntu.com/~robertc/baz2.0/index

Robert Collins robertc at robertcollins.net
Mon Jul 30 00:37:45 BST 2007


At http://people.ubuntu.com/~robertc/baz2.0/index

------------------------------------------------------------
revno: 2636
revision-id: robertc at robertcollins.net-20070729233741-tp1d2j06b7zde9j3
parent: robertc at robertcollins.net-20070728013353-qk7394wehmg2iiph
committer: Robert Collins <robertc at robertcollins.net>
branch nick: index
timestamp: Mon 2007-07-30 09:37:41 +1000
message:
  Create an adapter between indices with differing key lengths.
modified:
  bzrlib/index.py                index.py-20070712131115-lolkarso50vjr64s-1
  bzrlib/tests/test_index.py     test_index.py-20070712131115-lolkarso50vjr64s-2
=== modified file 'bzrlib/index.py'
--- a/bzrlib/index.py	2007-07-28 01:33:53 +0000
+++ b/bzrlib/index.py	2007-07-29 23:37:41 +0000
@@ -20,6 +20,7 @@
     'CombinedGraphIndex',
     'GraphIndex',
     'GraphIndexBuilder',
+    'GraphIndexPrefixAdapter',
     'InMemoryGraphIndex',
     ]
 
@@ -671,3 +672,83 @@
 
     def validate(self):
         """In memory index's have no known corruption at the moment."""
+
+
+class GraphIndexPrefixAdapter(object):
+    """An adapter between GraphIndex with different key lengths.
+
+    Queries against this will emit queries against the adapted Graph with the
+    prefix added, queries for all items use iter_entries_prefix. The returned
+    nodes will have their keys and node references adjusted to remove the 
+    prefix. Finally, an add_nodes_callback can be supplied - when called the
+    nodes and references being added will have prefix prepended.
+    """
+
+    def __init__(self, adapted, prefix, missing_key_length, add_nodes_callback=None):
+        """Construct an adapter against adapted with prefix."""
+        self.adapted = adapted
+        self.prefix = prefix + (None,)*missing_key_length
+        self.prefix_key = prefix
+        self.prefix_len = len(prefix)
+        self.add_nodes_callback = add_nodes_callback
+
+    def _strip_prefix(self, an_iter):
+        """Strip prefix data from nodes and return it."""
+        for node in an_iter:
+            # cross checks
+            if node[0][:self.prefix_len] != self.prefix_key:
+                raise errors.BadIndexData(self)
+            for ref_list in node[2]:
+                for ref_node in ref_list:
+                    if ref_node[:self.prefix_len] != self.prefix_key:
+                        raise errors.BadIndexData(self)
+            yield node[0][self.prefix_len:], node[1], (
+                tuple(tuple(ref_node[self.prefix_len:] for ref_node in ref_list)
+                for ref_list in node[2]))
+
+    def iter_all_entries(self):
+        """Iterate over all keys within the index
+
+        iter_all_entries is implemented against the adapted index using
+        iter_entries_prefix.
+
+        :return: An iterable of (key, reference_lists, value). There is no
+            defined order for the result iteration - it will be in the most
+            efficient order for the index (in this case dictionary hash order).
+        """
+        return self._strip_prefix(self.adapted.iter_entries_prefix([self.prefix]))
+
+    def iter_entries(self, keys):
+        """Iterate over keys within the index.
+
+        :param keys: An iterable providing the keys to be retrieved.
+        :return: An iterable of (key, reference_lists, value). There is no
+            defined order for the result iteration - it will be in the most
+            efficient order for the index (keys iteration order in this case).
+        """
+        return self._strip_prefix(self.adapted.iter_entries(
+            self.prefix_key + key for key in keys))
+
+    def iter_entries_prefix(self, keys):
+        """Iterate over keys within the index using prefix matching.
+
+        Prefix matching is applied within the tuple of a key, not to within
+        the bytestring of each key element. e.g. if you have the keys ('foo',
+        'bar'), ('foobar', 'gam') and do a prefix search for ('foo', None) then
+        only the former key is returned.
+
+        :param keys: An iterable providing the key prefixes to be retrieved.
+            Each key prefix takes the form of a tuple the length of a key, but
+            with the last N elements 'None' rather than a regular bytestring.
+            The first element cannot be 'None'.
+        :return: An iterable as per iter_all_entries, but restricted to the
+            keys with a matching prefix to those supplied. No additional keys
+            will be returned, and every match that is in the index will be
+            returned.
+        """
+        return self._strip_prefix(self.adapted.iter_entries_prefix(
+            self.prefix_key + key for key in keys))
+
+    def validate(self):
+        """Call the adapted's validate."""
+        self.adapted.validate()

=== modified file 'bzrlib/tests/test_index.py'
--- a/bzrlib/tests/test_index.py	2007-07-28 01:33:53 +0000
+++ b/bzrlib/tests/test_index.py	2007-07-29 23:37:41 +0000
@@ -754,3 +754,67 @@
         index.validate()
 
 
+class TestGraphIndexPrefixAdapter(TestCaseWithMemoryTransport):
+
+    def make_index(self, ref_lists=1, key_elements=2, nodes=[]):
+        result = InMemoryGraphIndex(ref_lists, key_elements=key_elements)
+        result.add_nodes(nodes)
+        adapter = GraphIndexPrefixAdapter(result, ('prefix', ), key_elements - 1)
+        return result, adapter
+
+    def test_construct(self):
+        index = InMemoryGraphIndex()
+        adapter = GraphIndexPrefixAdapter(index, ('prefix', ), 1)
+
+    def test_construct_with_callback(self):
+        index = InMemoryGraphIndex()
+        adapter = GraphIndexPrefixAdapter(index, ('prefix', ), 1, index.add_nodes)
+
+    def test_iter_all_entries_cross_prefix_map_errors(self):
+        index, adapter = self.make_index(nodes=[
+            (('prefix', 'key1'), 'data1', ((('prefixaltered', 'key2'),),))])
+        self.assertRaises(errors.BadIndexData, list, adapter.iter_all_entries())
+
+    def test_iter_all_entries(self):
+        index, adapter = self.make_index(nodes=[
+            (('notprefix', 'key1'), 'data', ((), )),
+            (('prefix', 'key1'), 'data1', ((), )),
+            (('prefix', 'key2'), 'data2', ((('prefix', 'key1'),),))])
+        self.assertEqual(set([(('key1', ), 'data1', ((),)),
+            (('key2', ), 'data2', ((('key1',),),))]),
+            set(adapter.iter_all_entries()))
+
+    def test_iter_entries(self):
+        index, adapter = self.make_index(nodes=[
+            (('notprefix', 'key1'), 'data', ((), )),
+            (('prefix', 'key1'), 'data1', ((), )),
+            (('prefix', 'key2'), 'data2', ((('prefix', 'key1'),),))])
+        # ask for many - get all
+        self.assertEqual(set([(('key1', ), 'data1', ((),)),
+            (('key2', ), 'data2', ((('key1', ),),))]),
+            set(adapter.iter_entries([('key1', ), ('key2', )])))
+        # ask for one, get one
+        self.assertEqual(set([(('key1', ), 'data1', ((),))]),
+            set(adapter.iter_entries([('key1', )])))
+        # ask for missing, get none
+        self.assertEqual(set(),
+            set(adapter.iter_entries([('key3', )])))
+
+    def test_iter_entries_prefix(self):
+        index, adapter = self.make_index(key_elements=3, nodes=[
+            (('notprefix', 'foo', 'key1'), 'data', ((), )),
+            (('prefix', 'prefix2', 'key1'), 'data1', ((), )),
+            (('prefix', 'prefix2', 'key2'), 'data2', ((('prefix', 'prefix2', 'key1'),),))])
+        # ask for a prefix, get the results for just that prefix, adjusted.
+        self.assertEqual(set([(('prefix2', 'key1', ), 'data1', ((),)),
+            (('prefix2', 'key2', ), 'data2', ((('prefix2', 'key1', ),),))]),
+            set(adapter.iter_entries_prefix([('prefix2', None)])))
+
+    def test_validate(self):
+        index, adapter = self.make_index()
+        calls = []
+        def validate():
+            calls.append('called')
+        index.validate = validate
+        adapter.validate()
+        self.assertEqual(['called'], calls)



More information about the bazaar-commits mailing list