Mercurial > hg
diff contrib/shrink-revlog.py @ 10623:64e286c22f29
shrink-revlog: add "reverse postorder" and "postorder reverse" toposorts.
Based on a patch by Benoit Boissinot, adapted to the pluggable sort
algorithm design. toposort_reversepostorder() is a very good
performer; it's designed to recreate what the revlog would have looked
like if Mercurial had parent deltas now. toposort_postorderreverse()
is unstable and very inconsistent, but perhaps with some work it could
be made better.
author | Greg Ward <greg-hg@gerg.ca> |
---|---|
date | Tue, 09 Mar 2010 21:22:01 -0500 |
parents | bc81f126139f |
children | 432eb853a2c6 |
line wrap: on
line diff
--- a/contrib/shrink-revlog.py Thu Feb 25 09:16:39 2010 -0500 +++ b/contrib/shrink-revlog.py Tue Mar 09 21:22:01 2010 -0500 @@ -81,6 +81,89 @@ ui.note(_('%d suboptimal nodes\n') % suboptimal) return result +def toposort_reversepostorder(ui, rl): + # postorder of the reverse directed graph + + # map rev to list of parent revs (p2 first) + parents = {} + heads = set() + ui.status(_('reading revs\n')) + try: + for rev in rl: + ui.progress(_('reading'), rev, total=len(rl)) + (p1, p2) = rl.parentrevs(rev) + if p1 == p2 == node.nullrev: + parents[rev] = () # root node + elif p1 == p2 or p2 == node.nullrev: + 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() + + 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 + +def toposort_postorderreverse(ui, rl): + # reverse-postorder of the reverse directed graph + + children = {} + roots = set() + ui.status(_('reading revs\n')) + try: + for rev in rl: + ui.progress(_('reading'), rev, total=len(rl)) + (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: + children[p2].append(rev) + finally: + ui.progress(_('reading'), None, total=len(rl)) + + ui.status(_('sorting revs\n')) + result = [] + visit = list(roots) + visit.sort() + finished = set() + 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() + result.reverse() + return result + def writerevs(ui, r1, r2, order, tr): ui.status(_('writing revs\n'))