Mercurial > hg
comparison contrib/shrink-revlog.py @ 10626:3fc95c3bc3ba
shrink-revlog: factor out suboptimal computation
author | Benoit Boissinot <benoit.boissinot@ens-lyon.org> |
---|---|
date | Wed, 10 Mar 2010 09:51:07 +0100 |
parents | add562abc28a |
children | adcd5bcb37ab |
comparison
equal
deleted
inserted
replaced
10625:add562abc28a | 10626:3fc95c3bc3ba |
---|---|
54 ui.status(_('sorting revs\n')) | 54 ui.status(_('sorting revs\n')) |
55 result = [] | 55 result = [] |
56 visit = list(heads) | 56 visit = list(heads) |
57 visit.sort(reverse=True) | 57 visit.sort(reverse=True) |
58 finished = set() | 58 finished = set() |
59 suboptimal = 0 | |
60 | 59 |
61 while visit: | 60 while visit: |
62 cur = visit[-1] | 61 cur = visit[-1] |
63 for p in parents[cur]: | 62 for p in parents[cur]: |
64 if p not in finished: | 63 if p not in finished: |
65 visit.append(p) | 64 visit.append(p) |
66 break | 65 break |
67 else: | 66 else: |
68 curparents = rl.parentrevs(cur) | |
69 if result and result[-1] != curparents[0]: | |
70 suboptimal += 1 | |
71 | |
72 result.append(cur) | 67 result.append(cur) |
73 finished.add(cur) | 68 finished.add(cur) |
74 visit.pop() | 69 visit.pop() |
75 | |
76 ui.note(_('%d suboptimal nodes\n') % suboptimal) | |
77 | 70 |
78 return result | 71 return result |
79 | 72 |
80 def toposort_postorderreverse(ui, rl): | 73 def toposort_postorderreverse(ui, rl): |
81 # reverse-postorder of the reverse directed graph | 74 # reverse-postorder of the reverse directed graph |
102 ui.status(_('sorting revs\n')) | 95 ui.status(_('sorting revs\n')) |
103 result = [] | 96 result = [] |
104 visit = list(roots) | 97 visit = list(roots) |
105 visit.sort() | 98 visit.sort() |
106 finished = set() | 99 finished = set() |
107 suboptimal = 0 | |
108 | 100 |
109 while visit: | 101 while visit: |
110 cur = visit[-1] | 102 cur = visit[-1] |
111 for p in children[cur]: | 103 for p in children[cur]: |
112 if p not in finished: | 104 if p not in finished: |
113 visit.append(p) | 105 visit.append(p) |
114 break | 106 break |
115 else: | 107 else: |
116 # if cur is not the first parent of its successor, then the | |
117 # successor is a suboptimal node | |
118 if result: | |
119 succparents = rl.parentrevs(result[-1]) | |
120 if succparents[0] != cur: | |
121 suboptimal += 1 | |
122 | |
123 result.append(cur) | 108 result.append(cur) |
124 finished.add(cur) | 109 finished.add(cur) |
125 visit.pop() | 110 visit.pop() |
126 | |
127 ui.note(_('%d suboptimal nodes\n') % suboptimal) | |
128 | 111 |
129 result.reverse() | 112 result.reverse() |
130 return result | 113 return result |
131 | 114 |
132 def writerevs(ui, r1, r2, order, tr): | 115 def writerevs(ui, r1, r2, order, tr): |
257 return f | 240 return f |
258 | 241 |
259 try: | 242 try: |
260 try: | 243 try: |
261 order = toposort(ui, r1) | 244 order = toposort(ui, r1) |
245 | |
246 suboptimal = 0 | |
247 for i in xrange(1, len(order)): | |
248 parents = [p for p in r1.parentrevs(order[i]) | |
249 if p != node.nullrev] | |
250 if parents and order[i-1] not in parents: | |
251 suboptimal += 1 | |
252 ui.note(_('%d suboptimal nodes\n') % suboptimal) | |
253 | |
262 writerevs(ui, r1, r2, order, tr) | 254 writerevs(ui, r1, r2, order, tr) |
263 report(ui, r1, r2) | 255 report(ui, r1, r2) |
264 tr.close() | 256 tr.close() |
265 except: | 257 except: |
266 # Abort transaction first, so we truncate the files before | 258 # Abort transaction first, so we truncate the files before |