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