Mercurial > hg
comparison 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 |
comparison
equal
deleted
inserted
replaced
10622:bc81f126139f | 10623:64e286c22f29 |
---|---|
77 if p != node.nullrev and p in children] | 77 if p != node.nullrev and p in children] |
78 if len(parents_unseen) == 0: | 78 if len(parents_unseen) == 0: |
79 next.append(c) | 79 next.append(c) |
80 visit = next + visit | 80 visit = next + visit |
81 ui.note(_('%d suboptimal nodes\n') % suboptimal) | 81 ui.note(_('%d suboptimal nodes\n') % suboptimal) |
82 return result | |
83 | |
84 def toposort_reversepostorder(ui, rl): | |
85 # postorder of the reverse directed graph | |
86 | |
87 # map rev to list of parent revs (p2 first) | |
88 parents = {} | |
89 heads = set() | |
90 ui.status(_('reading revs\n')) | |
91 try: | |
92 for rev in rl: | |
93 ui.progress(_('reading'), rev, total=len(rl)) | |
94 (p1, p2) = rl.parentrevs(rev) | |
95 if p1 == p2 == node.nullrev: | |
96 parents[rev] = () # root node | |
97 elif p1 == p2 or p2 == node.nullrev: | |
98 parents[rev] = (p1,) # normal node | |
99 else: | |
100 parents[rev] = (p2, p1) # merge node | |
101 | |
102 heads.add(rev) | |
103 | |
104 for p in parents[rev]: | |
105 heads.discard(p) | |
106 finally: | |
107 ui.progress(_('reading'), None, total=len(rl)) | |
108 | |
109 ui.status(_('sorting revs\n')) | |
110 result = [] | |
111 visit = list(heads) | |
112 visit.sort(reverse=True) | |
113 finished = set() | |
114 | |
115 while visit: | |
116 cur = visit[-1] | |
117 for p in parents[cur]: | |
118 if p not in finished: | |
119 visit.append(p) | |
120 break | |
121 else: | |
122 result.append(cur) | |
123 finished.add(cur) | |
124 visit.pop() | |
125 return result | |
126 | |
127 def toposort_postorderreverse(ui, rl): | |
128 # reverse-postorder of the reverse directed graph | |
129 | |
130 children = {} | |
131 roots = set() | |
132 ui.status(_('reading revs\n')) | |
133 try: | |
134 for rev in rl: | |
135 ui.progress(_('reading'), rev, total=len(rl)) | |
136 (p1, p2) = rl.parentrevs(rev) | |
137 if p1 == p2 == node.nullrev: | |
138 roots.add(rev) | |
139 | |
140 children[rev] = [] | |
141 | |
142 if p1 != node.nullrev: | |
143 children[p1].append(rev) | |
144 if p2 != node.nullrev: | |
145 children[p2].append(rev) | |
146 finally: | |
147 ui.progress(_('reading'), None, total=len(rl)) | |
148 | |
149 ui.status(_('sorting revs\n')) | |
150 result = [] | |
151 visit = list(roots) | |
152 visit.sort() | |
153 finished = set() | |
154 while visit: | |
155 cur = visit[-1] | |
156 for p in children[cur]: | |
157 if p not in finished: | |
158 visit.append(p) | |
159 break | |
160 else: | |
161 result.append(cur) | |
162 finished.add(cur) | |
163 visit.pop() | |
164 result.reverse() | |
82 return result | 165 return result |
83 | 166 |
84 def writerevs(ui, r1, r2, order, tr): | 167 def writerevs(ui, r1, r2, order, tr): |
85 | 168 |
86 ui.status(_('writing revs\n')) | 169 ui.status(_('writing revs\n')) |