fix graph traversal in commands.bundle (it wasn't O(n))
authorBenoit Boissinot <benoit.boissinot@ens-lyon.org>
Wed, 25 Oct 2006 18:22:04 +0200
changeset 3512 630e0b216192
parent 3511 aa8f086cb141
child 3513 9383af6f236d
fix graph traversal in commands.bundle (it wasn't O(n))
mercurial/commands.py
--- a/mercurial/commands.py	Wed Oct 25 17:20:39 2006 +0200
+++ b/mercurial/commands.py	Wed Oct 25 18:22:04 2006 +0200
@@ -839,6 +839,7 @@
             visit = list(revs)
         else:
             visit = repo.changelog.heads()
+        seen = sets.Set(visit)
         while visit:
             n = visit.pop(0)
             parents = [p for p in repo.changelog.parents(n)
@@ -846,7 +847,10 @@
             if len(parents) == 0:
                 o.insert(0, n)
             else:
-                visit.extend(parents)
+                for p in parents:
+                    if p not in seen:
+                        seen.add(p)
+                        visit.append(p)
     else:
         setremoteconfig(ui, opts)
         dest = ui.expandpath(dest or 'default-push', dest or 'default')