We are currently indexing your data, so search results may be incomplete until we finish.
ObjectStore.get_graph_walker() now no longer yields the same
revision more than once. This has a significant improvement for
performance when wide revision graphs are involved.
Changeset fcbe1e1e6040…
Parent fdbf28356688…
by
Changes to 3 files · Browse files at fcbe1e1e6040 Showing diff from parent fdbf28356688 Diff from another changeset...
|
@@ -34,6 +34,11 @@ * Support ~ in git:// URL paths. (Jelmer Vernooij, #813555)
* Make ShaFile.__eq__ work when other is not a ShaFile. (Dave Borowitz)
+
+ * ObjectStore.get_graph_walker() now no longer yields the same
+ revision more than once. This has a significant improvement for
+ performance when wide revision graphs are involved.
+ (Jelmer Vernooij, #818168)
API CHANGES
|
||
|
@@ -779,8 +779,10 @@ # collect all ancestors
new_ancestors = set()
for a in ancestors:
- if a in self.parents:
- new_ancestors.update(self.parents[a])
+ ps = self.parents.get(a)
+ if ps is not None:
+ new_ancestors.update(ps)
+ self.parents[a] = None
# no more ancestors; stop
if not new_ancestors:
@@ -794,6 +796,6 @@ ret = self.heads.pop()
ps = self.get_parents(ret)
self.parents[ret] = ps
- self.heads.update(ps)
+ self.heads.update([p for p in ps if not p in self.parents])
return ret
return None
|
||
|
@@ -41,6 +41,7 @@ from dulwich.object_store import (
DiskObjectStore,
MemoryObjectStore,
+ ObjectStoreGraphWalker,
tree_lookup_path,
)
from dulwich.pack import (
@@ -300,3 +301,58 @@ self.assertRaises(NotTreeError, tree_lookup_path, self.get_object, self.tree_id, 'ad/b/j')
# TODO: MissingObjectFinderTests
+
+class ObjectStoreGraphWalkerTests(TestCase):
+
+ def get_walker(self, heads, parent_map):
+ return ObjectStoreGraphWalker(heads,
+ parent_map.__getitem__)
+
+ def test_empty(self):
+ gw = self.get_walker([], {})
+ self.assertIs(None, gw.next())
+ gw.ack("aa" * 20)
+ self.assertIs(None, gw.next())
+
+ def test_descends(self):
+ gw = self.get_walker(["a"], {"a": ["b"], "b": []})
+ self.assertEquals("a", gw.next())
+ self.assertEquals("b", gw.next())
+
+ def test_present(self):
+ gw = self.get_walker(["a"], {"a": ["b"], "b": []})
+ gw.ack("a")
+ self.assertIs(None, gw.next())
+
+ def test_parent_present(self):
+ gw = self.get_walker(["a"], {"a": ["b"], "b": []})
+ self.assertEquals("a", gw.next())
+ gw.ack("a")
+ self.assertIs(None, gw.next())
+
+ def test_child_ack_later(self):
+ gw = self.get_walker(["a"], {"a": ["b"], "b": ["c"], "c": []})
+ self.assertEquals("a", gw.next())
+ self.assertEquals("b", gw.next())
+ gw.ack("a")
+ self.assertIs(None, gw.next())
+
+ def test_only_once(self):
+ # a b
+ # | |
+ # c d
+ # \ /
+ # e
+ gw = self.get_walker(["a", "b"], {
+ "a": ["c"],
+ "b": ["d"],
+ "c": ["e"],
+ "d": ["e"],
+ "e": [],
+ })
+ self.assertEquals("a", gw.next())
+ self.assertEquals("c", gw.next())
+ gw.ack("a")
+ self.assertEquals("b", gw.next())
+ self.assertEquals("d", gw.next())
+ self.assertIs(None, gw.next())
|
||
Add a tag
Loading...