changeset 10627:adcd5bcb37ab

shrink-revlog: factor out postorder algorithm

--- a/contrib/shrink-revlog.py	Wed Mar 10 09:51:07 2010 +0100
+++ b/contrib/shrink-revlog.py	Wed Mar 10 09:52:16 2010 +0100
@@ -25,6 +25,23 @@
 from mercurial.i18n import _
 
 
+def postorder(start, edges):
+    result = []
+    visit = list(start)
+    finished = set()
+
+    while visit:
+        cur = visit[-1]
+        for p in edges[cur]:
+            if p not in finished:
+                visit.append(p)
+                break
+        else:
+            result.append(cur)
+            finished.add(cur)
+            visit.pop()
+
+    return result
 
 def toposort_reversepostorder(ui, rl):
     # postorder of the reverse directed graph
@@ -43,32 +60,17 @@
                 parents[rev] = (p1,)    # normal node
             else:
                 parents[rev] = (p2, p1) # merge node
-
             heads.add(rev)
-
             for p in parents[rev]:
                 heads.discard(p)
     finally:
         ui.progress(_('reading'), None, total=len(rl))
 
-    ui.status(_('sorting revs\n'))
-    result = []
-    visit = list(heads)
-    visit.sort(reverse=True)
-    finished = set()
+    heads = list(heads)
+    heads.sort(reverse=True)
 
-    while visit:
-        cur = visit[-1]
-        for p in parents[cur]:
-            if p not in finished:
-                visit.append(p)
-                break
-        else:
-            result.append(cur)
-            finished.add(cur)
-            visit.pop()
-
-    return result
+    ui.status(_('sorting revs\n'))
+    return postorder(heads, parents)
 
 def toposort_postorderreverse(ui, rl):
     # reverse-postorder of the reverse directed graph
@@ -82,9 +84,7 @@
             (p1, p2) = rl.parentrevs(rev)
             if p1 == p2 == node.nullrev:
                 roots.add(rev)
-
             children[rev] = []
-
             if p1 != node.nullrev:
                 children[p1].append(rev)
             if p2 != node.nullrev:
@@ -92,23 +92,11 @@
     finally:
         ui.progress(_('reading'), None, total=len(rl))
 
-    ui.status(_('sorting revs\n'))
-    result = []
-    visit = list(roots)
-    visit.sort()
-    finished = set()
+    root = list(roots)
+    roots.sort()
 
-    while visit:
-        cur = visit[-1]
-        for p in children[cur]:
-            if p not in finished:
-                visit.append(p)
-                break
-        else:
-            result.append(cur)
-            finished.add(cur)
-            visit.pop()
-
+    ui.status(_('sorting revs\n'))
+    result = postorder(roots, children)
     result.reverse()
     return result