Rev 4605: Name the specific index api _find_ancestors, and the public CombinedGraphIndex api find_ancestry() in http://bazaar.launchpad.net/~jameinel/bzr/1.18-faster-iter-ancestry
John Arbash Meinel
john at arbash-meinel.com
Thu Aug 13 20:56:34 BST 2009
At http://bazaar.launchpad.net/~jameinel/bzr/1.18-faster-iter-ancestry
------------------------------------------------------------
revno: 4605
revision-id: john at arbash-meinel.com-20090813195626-tlsu5cexc1q8lzmr
parent: john at arbash-meinel.com-20090811170307-31ip7d2lswbbcr3w
committer: John Arbash Meinel <john at arbash-meinel.com>
branch nick: 1.18-faster-iter-ancestry
timestamp: Thu 2009-08-13 14:56:26 -0500
message:
Name the specific index api _find_ancestors, and the public CombinedGraphIndex api find_ancestry()
-------------- next part --------------
=== modified file 'bzrlib/btree_index.py'
--- a/bzrlib/btree_index.py 2009-08-11 17:03:07 +0000
+++ b/bzrlib/btree_index.py 2009-08-13 19:56:26 +0000
@@ -1134,7 +1134,7 @@
else:
yield (self, next_sub_key, value)
- def find_ancestry(self, keys, ref_list_num, parent_map, missing_keys):
+ def _find_ancestors(self, keys, ref_list_num, parent_map, missing_keys):
"""Find the parent_map information for the set of keys.
This populates the parent_map dict and missing_keys set based on the
@@ -1142,7 +1142,7 @@
it finds while searching for the supplied keys.
It is unlikely that you want to call this directly. See
- "CombinedGraphIndex.get_ancestry()" for a more appropriate API.
+ "CombinedGraphIndex.find_ancestry()" for a more appropriate API.
:param keys: A keys whose ancestry we want to return
Every key will either end up in 'parent_map' or 'missing_keys'.
=== modified file 'bzrlib/index.py'
--- a/bzrlib/index.py 2009-08-11 17:03:07 +0000
+++ b/bzrlib/index.py 2009-08-13 19:56:26 +0000
@@ -702,9 +702,8 @@
# the last thing looked up was a terminal element
yield (self, ) + key_dict
- def get_local_parent_map(self, keys, ref_list_num, parent_map,
- missing_keys):
- """See BTreeIndex.get_local_parent_map."""
+ def _find_ancestors(self, keys, ref_list_num, parent_map, missing_keys):
+ """See BTreeIndex._find_ancestors."""
# 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.
@@ -1315,10 +1314,15 @@
except errors.NoSuchFile:
self._reload_or_raise()
- def get_ancestry(self, keys):
+ def find_ancestry(self, keys, ref_list_num):
"""Find the complete ancestry for the given set of keys.
+ Note that this is a whole-ancestry request, so it should be used
+ sparingly.
+
:param keys: An iterable of keys to look for
+ :param ref_list_num: The reference list which references the parents
+ we care about.
:return: (parent_map, missing_keys)
"""
missing_keys = set()
@@ -1351,8 +1355,8 @@
# TODO: ref_list_num should really be a parameter, since
# CombinedGraphIndex does not know what the ref lists
# mean.
- search_keys = index.get_ancestry(search_keys, 0,
- parent_map, index_missing_keys)
+ search_keys = index._find_ancestors(search_keys,
+ ref_list_num, parent_map, index_missing_keys)
# print ' \t \t%2d\t%4d\t%5d\t%5d' % (
# sub_generation, len(search_keys),
# len(parent_map), len(index_missing_keys))
=== modified file 'bzrlib/tests/test_btree_index.py'
--- a/bzrlib/tests/test_btree_index.py 2009-08-11 17:03:07 +0000
+++ b/bzrlib/tests/test_btree_index.py 2009-08-13 19:56:26 +0000
@@ -981,7 +981,7 @@
])
self.assertEqual(set([]), index.external_references(0))
- def test_get_ancestry_one_page(self):
+ def test__find_ancestors_one_page(self):
key1 = ('key-1',)
key2 = ('key-2',)
index = self.make_index(ref_lists=1, key_elements=1, nodes=[
@@ -990,12 +990,12 @@
])
parent_map = {}
missing_keys = set()
- search_keys = index.get_ancestry([key1], 0, parent_map, missing_keys)
+ search_keys = index._find_ancestors([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):
+ def test__find_ancestors_one_page_w_missing(self):
key1 = ('key-1',)
key2 = ('key-2',)
key3 = ('key-3',)
@@ -1005,15 +1005,15 @@
])
parent_map = {}
missing_keys = set()
- search_keys = index.get_ancestry([key2, key3], 0, parent_map,
- missing_keys)
+ search_keys = index._find_ancestors([key2, key3], 0, parent_map,
+ missing_keys)
self.assertEqual({key2: ()}, parent_map)
# we know that key3 is missing because we read the page that it would
# otherwise be on
self.assertEqual(set([key3]), missing_keys)
self.assertEqual(set(), search_keys)
- def test_get_ancestry_one_parent_missing(self):
+ def test__find_ancestors_one_parent_missing(self):
key1 = ('key-1',)
key2 = ('key-2',)
key3 = ('key-3',)
@@ -1023,22 +1023,22 @@
])
parent_map = {}
missing_keys = set()
- search_keys = index.get_ancestry([key1], 0, parent_map,
- missing_keys)
+ search_keys = index._find_ancestors([key1], 0, parent_map,
+ missing_keys)
self.assertEqual({key1: (key2,), key2: (key3,)}, parent_map)
self.assertEqual(set(), missing_keys)
# all we know is that key3 wasn't present on the page we were reading
# but if you look, the last key is key2 which comes before key3, so we
# don't know whether key3 would land on this page or not.
self.assertEqual(set([key3]), search_keys)
- search_keys = index.get_ancestry(search_keys, 0, parent_map,
- missing_keys)
+ search_keys = index._find_ancestors(search_keys, 0, parent_map,
+ missing_keys)
# passing it back in, we are sure it is 'missing'
self.assertEqual({key1: (key2,), key2: (key3,)}, parent_map)
self.assertEqual(set([key3]), missing_keys)
self.assertEqual(set([]), search_keys)
- def test_get_ancestry_dont_search_known(self):
+ def test__find_ancestors_dont_search_known(self):
key1 = ('key-1',)
key2 = ('key-2',)
key3 = ('key-3',)
@@ -1050,13 +1050,13 @@
# 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)
+ search_keys = index._find_ancestors([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):
+ def test__find_ancestors_multiple_pages(self):
# We need to use enough keys that we actually cause a split
start_time = 1249671539
email = "joebob at example.com"
@@ -1093,24 +1093,24 @@
# parent of that key
parent_map = {}
missing_keys = set()
- search_keys = index.get_ancestry([next_key], 0, parent_map,
- missing_keys)
+ search_keys = index._find_ancestors([next_key], 0, parent_map,
+ missing_keys)
self.assertEqual([min_l2_key, next_key], sorted(parent_map))
self.assertEqual(set(), missing_keys)
self.assertEqual(set([max_l1_key]), search_keys)
parent_map = {}
- search_keys = index.get_ancestry([max_l1_key], 0, parent_map,
- missing_keys)
+ search_keys = index._find_ancestors([max_l1_key], 0, parent_map,
+ missing_keys)
self.assertEqual(sorted(l1.keys), sorted(parent_map))
self.assertEqual(set(), missing_keys)
self.assertEqual(set(), search_keys)
- def test_get_ancestry_empty_index(self):
+ def test__find_ancestors_empty_index(self):
index = self.make_index(ref_lists=1, key_elements=1, nodes=[])
parent_map = {}
missing_keys = set()
- search_keys = index.get_ancestry([('one',), ('two',)], 0, parent_map,
- missing_keys)
+ search_keys = index._find_ancestors([('one',), ('two',)], 0, parent_map,
+ missing_keys)
self.assertEqual(set(), search_keys)
self.assertEqual({}, parent_map)
self.assertEqual(set([('one',), ('two',)]), missing_keys)
=== modified file 'bzrlib/tests/test_index.py'
--- a/bzrlib/tests/test_index.py 2009-08-11 17:03:07 +0000
+++ b/bzrlib/tests/test_index.py 2009-08-13 19:56:26 +0000
@@ -953,7 +953,7 @@
])
self.assertEqual(set([]), index.external_references(0))
- def test_get_ancestry(self):
+ def test__find_ancestors(self):
key1 = ('key-1',)
key2 = ('key-2',)
index = self.make_index(ref_lists=1, key_elements=1, nodes=[
@@ -962,17 +962,17 @@
])
parent_map = {}
missing_keys = set()
- search_keys = index.get_ancestry([key1], 0, parent_map, missing_keys)
+ search_keys = index._find_ancestors([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)
+ search_keys = index._find_ancestors(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):
+ def test__find_ancestors_w_missing(self):
key1 = ('key-1',)
key2 = ('key-2',)
key3 = ('key-3',)
@@ -982,13 +982,13 @@
])
parent_map = {}
missing_keys = set()
- search_keys = index.get_ancestry([key2, key3], 0, parent_map,
- missing_keys)
+ search_keys = index._find_ancestors([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):
+ def test__find_ancestors_dont_search_known(self):
key1 = ('key-1',)
key2 = ('key-2',)
key3 = ('key-3',)
@@ -1000,8 +1000,8 @@
# 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)
+ search_keys = index._find_ancestors([key1], 0, parent_map,
+ missing_keys)
self.assertEqual({key1: (key2,), key2: (key3,)}, parent_map)
self.assertEqual(set(), missing_keys)
self.assertEqual(set(), search_keys)
@@ -1324,7 +1324,7 @@
['1', '2', '3'])
self.assertRaises(errors.NoSuchFile, index.validate)
- def test_get_ancestry_across_indexes(self):
+ def test_find_ancestors_across_indexes(self):
key1 = ('key-1',)
key2 = ('key-2',)
key3 = ('key-3',)
@@ -1338,17 +1338,17 @@
(key4, 'value', ([key3],)),
])
c_index = CombinedGraphIndex([index1, index2])
- parent_map, missing_keys = c_index.get_ancestry([key1])
+ parent_map, missing_keys = c_index.find_ancestry([key1], 0)
self.assertEqual({key1: ()}, parent_map)
self.assertEqual(set(), missing_keys)
# Now look for a key from index2 which requires us to find the key in
# the second index, and then continue searching for parents in the
# first index
- parent_map, missing_keys = c_index.get_ancestry([key3])
+ parent_map, missing_keys = c_index.find_ancestry([key3], 0)
self.assertEqual({key1: (), key2: (key1,), key3: (key2,)}, parent_map)
self.assertEqual(set(), missing_keys)
- def test_get_ancestry_missing_keys(self):
+ def test_find_ancestors_missing_keys(self):
key1 = ('key-1',)
key2 = ('key-2',)
key3 = ('key-3',)
@@ -1363,18 +1363,18 @@
c_index = CombinedGraphIndex([index1, index2])
# Searching for a key which is actually not present at all should
# eventually converge
- parent_map, missing_keys = c_index.get_ancestry([key4])
+ parent_map, missing_keys = c_index.find_ancestry([key4], 0)
self.assertEqual({}, parent_map)
self.assertEqual(set([key4]), missing_keys)
- def test_get_ancestry_no_indexes(self):
+ def test_find_ancestors_no_indexes(self):
c_index = CombinedGraphIndex([])
key1 = ('key-1',)
- parent_map, missing_keys = c_index.get_ancestry([key1])
+ parent_map, missing_keys = c_index.find_ancestry([key1], 0)
self.assertEqual({}, parent_map)
self.assertEqual(set([key1]), missing_keys)
- def test_get_ancestry_ghost_parent(self):
+ def test_find_ancestors_ghost_parent(self):
key1 = ('key-1',)
key2 = ('key-2',)
key3 = ('key-3',)
@@ -1389,17 +1389,17 @@
c_index = CombinedGraphIndex([index1, index2])
# Searching for a key which is actually not present at all should
# eventually converge
- parent_map, missing_keys = c_index.get_ancestry([key4])
+ parent_map, missing_keys = c_index.find_ancestry([key4], 0)
self.assertEqual({key4: (key2, key3), key2: (key1,), key1: ()},
parent_map)
self.assertEqual(set([key3]), missing_keys)
- def test_get_ancestry_empty_index(self):
- index = self.make_index(ref_lists=1, key_elements=1, nodes=[])
+ def test__find_ancestors_empty_index(self):
+ index = self.make_index('test', ref_lists=1, key_elements=1, nodes=[])
parent_map = {}
missing_keys = set()
- search_keys = index.get_ancestry([('one',), ('two',)], 0, parent_map,
- missing_keys)
+ search_keys = index._find_ancestors([('one',), ('two',)], 0, parent_map,
+ missing_keys)
self.assertEqual(set(), search_keys)
self.assertEqual({}, parent_map)
self.assertEqual(set([('one',), ('two',)]), missing_keys)
More information about the bazaar-commits
mailing list