Mercurial > hg
diff contrib/shrink-revlog.py @ 10627:adcd5bcb37ab
shrink-revlog: factor out postorder algorithm
author | Benoit Boissinot <benoit.boissinot@ens-lyon.org> |
---|---|
date | Wed, 10 Mar 2010 09:52:16 +0100 |
parents | 3fc95c3bc3ba |
children | f63fb5c0cf67 |
line wrap: on
line diff
--- 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