Rev 4600: Basic implementation of a conforming interface for GraphIndex. in http://bazaar.launchpad.net/~jameinel/bzr/1.18-faster-iter-ancestry

[John Arbash Meinel]

At http://bazaar.launchpad.net/~jameinel/bzr/1.18-faster-iter-ancestry

------------------------------------------------------------
revno: 4600
revision-id: john at arbash-meinel.com-20090807193730-b4ib7013ei79rfdy
parent: john at arbash-meinel.com-20090807191937-41ev37kaytvszydt
committer: John Arbash Meinel <john at arbash-meinel.com>
branch nick: 1.18-faster-iter-ancestry
timestamp: Fri 2009-08-07 14:37:30 -0500
message:
  Basic implementation of a conforming interface for GraphIndex.
  
  Add some simple tests, for now we won't try to do anything fancier.
  Time to start working on CombinedGraphIndex's interface.
-------------- next part --------------
=== modified file 'bzrlib/index.py'
--- a/bzrlib/index.py	2009-07-01 10:53:08 +0000
+++ b/bzrlib/index.py	2009-08-07 19:37:30 +0000
@@ -702,6 +702,23 @@
                 # the last thing looked up was a terminal element
                 yield (self, ) + key_dict
 
+    def get_ancestry(self, keys, ref_list_num, parent_map, missing_keys):
+        """See BTreeIndex.get_ancestry."""
+        # The api can be implemented as a trivial overlay on top of
+        # iter_entries, it is not an efficient implementation, but it at least
+        # gets the job done.
+        found_keys = set()
+        search_keys = set()
+        for index, key, value, refs in self.iter_entries(keys):
+            parent_keys = refs[ref_list_num]
+            found_keys.add(key)
+            parent_map[key] = parent_keys
+            search_keys.update(parent_keys)
+        # Figure out what, if anything, was missing
+        missing_keys.update(set(keys).difference(found_keys))
+        search_keys = search_keys.difference(parent_map)
+        return search_keys
+
     def key_count(self):
         """Return an estimate of the number of keys in this index.
 

=== modified file 'bzrlib/tests/test_btree_index.py'
--- a/bzrlib/tests/test_btree_index.py	2009-08-07 19:19:37 +0000
+++ b/bzrlib/tests/test_btree_index.py	2009-08-07 19:37:30 +0000
@@ -993,6 +993,7 @@
         search_keys = index.get_ancestry([key1], 0, parent_map, missing_keys)
         self.assertEqual({key1: (key2,), key2: ()}, parent_map)
         self.assertEqual(set(), missing_keys)
+        self.assertEqual(set(), search_keys)
 
     def test_get_ancestry_one_page_w_missing(self):
         key1 = ('key-1',)
@@ -1037,6 +1038,24 @@
         self.assertEqual(set([key3]), missing_keys)
         self.assertEqual(set([]), search_keys)
 
+    def test_get_ancestry_dont_search_known(self):
+        key1 = ('key-1',)
+        key2 = ('key-2',)
+        key3 = ('key-3',)
+        index = self.make_index(ref_lists=1, key_elements=1, nodes=[
+            (key1, 'value', ([key2],)),
+            (key2, 'value', ([key3],)),
+            (key3, 'value', ([],)),
+            ])
+        # We already know about key2, so we won't try to search for key3
+        parent_map = {key2: (key3,)}
+        missing_keys = set()
+        search_keys = index.get_ancestry([key1], 0, parent_map,
+                                         missing_keys)
+        self.assertEqual({key1: (key2,), key2: (key3,)}, parent_map)
+        self.assertEqual(set(), missing_keys)
+        self.assertEqual(set(), search_keys)
+
     def test_get_ancestry_multiple_pages(self):
         # We need to use enough keys that we actually cause a split
         start_time = 1249671539

=== modified file 'bzrlib/tests/test_index.py'
--- a/bzrlib/tests/test_index.py	2009-03-23 14:59:43 +0000
+++ b/bzrlib/tests/test_index.py	2009-08-07 19:37:30 +0000
@@ -953,6 +953,59 @@
             ])
         self.assertEqual(set([]), index.external_references(0))
 
+    def test_get_ancestry(self):
+        key1 = ('key-1',)
+        key2 = ('key-2',)
+        index = self.make_index(ref_lists=1, key_elements=1, nodes=[
+            (key1, 'value', ([key2],)),
+            (key2, 'value', ([],)),
+            ])
+        parent_map = {}
+        missing_keys = set()
+        search_keys = index.get_ancestry([key1], 0, parent_map, missing_keys)
+        self.assertEqual({key1: (key2,)}, parent_map)
+        self.assertEqual(set(), missing_keys)
+        self.assertEqual(set([key2]), search_keys)
+        search_keys = index.get_ancestry(search_keys, 0, parent_map,
+                                         missing_keys)
+        self.assertEqual({key1: (key2,), key2: ()}, parent_map)
+        self.assertEqual(set(), missing_keys)
+        self.assertEqual(set(), search_keys)
+
+    def test_get_ancestry_w_missing(self):
+        key1 = ('key-1',)
+        key2 = ('key-2',)
+        key3 = ('key-3',)
+        index = self.make_index(ref_lists=1, key_elements=1, nodes=[
+            (key1, 'value', ([key2],)),
+            (key2, 'value', ([],)),
+            ])
+        parent_map = {}
+        missing_keys = set()
+        search_keys = index.get_ancestry([key2, key3], 0, parent_map,
+                                         missing_keys)
+        self.assertEqual({key2: ()}, parent_map)
+        self.assertEqual(set([key3]), missing_keys)
+        self.assertEqual(set(), search_keys)
+
+    def test_get_ancestry_dont_search_known(self):
+        key1 = ('key-1',)
+        key2 = ('key-2',)
+        key3 = ('key-3',)
+        index = self.make_index(ref_lists=1, key_elements=1, nodes=[
+            (key1, 'value', ([key2],)),
+            (key2, 'value', ([key3],)),
+            (key3, 'value', ([],)),
+            ])
+        # We already know about key2, so we won't try to search for key3
+        parent_map = {key2: (key3,)}
+        missing_keys = set()
+        search_keys = index.get_ancestry([key1], 0, parent_map,
+                                         missing_keys)
+        self.assertEqual({key1: (key2,), key2: (key3,)}, parent_map)
+        self.assertEqual(set(), missing_keys)
+        self.assertEqual(set(), search_keys)
+
 
 class TestCombinedGraphIndex(TestCaseWithMemoryTransport):