Mercurial > hg
comparison contrib/shrink-revlog.py @ 10624:432eb853a2c6
shrink-revlog: add accounting of suboptimal nodes to the new algorithms.
author | Greg Ward <greg-hg@gerg.ca> |
---|---|
date | Tue, 09 Mar 2010 21:25:37 -0500 |
parents | 64e286c22f29 |
children | add562abc28a |
comparison
equal
deleted
inserted
replaced
10623:64e286c22f29 | 10624:432eb853a2c6 |
---|---|
109 ui.status(_('sorting revs\n')) | 109 ui.status(_('sorting revs\n')) |
110 result = [] | 110 result = [] |
111 visit = list(heads) | 111 visit = list(heads) |
112 visit.sort(reverse=True) | 112 visit.sort(reverse=True) |
113 finished = set() | 113 finished = set() |
114 suboptimal = 0 | |
114 | 115 |
115 while visit: | 116 while visit: |
116 cur = visit[-1] | 117 cur = visit[-1] |
117 for p in parents[cur]: | 118 for p in parents[cur]: |
118 if p not in finished: | 119 if p not in finished: |
119 visit.append(p) | 120 visit.append(p) |
120 break | 121 break |
121 else: | 122 else: |
123 curparents = rl.parentrevs(cur) | |
124 if result and result[-1] != curparents[0]: | |
125 suboptimal += 1 | |
126 | |
122 result.append(cur) | 127 result.append(cur) |
123 finished.add(cur) | 128 finished.add(cur) |
124 visit.pop() | 129 visit.pop() |
130 | |
131 ui.note(_('%d suboptimal nodes\n') % suboptimal) | |
132 | |
125 return result | 133 return result |
126 | 134 |
127 def toposort_postorderreverse(ui, rl): | 135 def toposort_postorderreverse(ui, rl): |
128 # reverse-postorder of the reverse directed graph | 136 # reverse-postorder of the reverse directed graph |
129 | 137 |
149 ui.status(_('sorting revs\n')) | 157 ui.status(_('sorting revs\n')) |
150 result = [] | 158 result = [] |
151 visit = list(roots) | 159 visit = list(roots) |
152 visit.sort() | 160 visit.sort() |
153 finished = set() | 161 finished = set() |
162 suboptimal = 0 | |
163 | |
154 while visit: | 164 while visit: |
155 cur = visit[-1] | 165 cur = visit[-1] |
156 for p in children[cur]: | 166 for p in children[cur]: |
157 if p not in finished: | 167 if p not in finished: |
158 visit.append(p) | 168 visit.append(p) |
159 break | 169 break |
160 else: | 170 else: |
171 # if cur is not the first parent of its successor, then the | |
172 # successor is a suboptimal node | |
173 if result: | |
174 succparents = rl.parentrevs(result[-1]) | |
175 if succparents[0] != cur: | |
176 suboptimal += 1 | |
177 | |
161 result.append(cur) | 178 result.append(cur) |
162 finished.add(cur) | 179 finished.add(cur) |
163 visit.pop() | 180 visit.pop() |
181 | |
182 ui.note(_('%d suboptimal nodes\n') % suboptimal) | |
183 | |
164 result.reverse() | 184 result.reverse() |
165 return result | 185 return result |
166 | 186 |
167 def writerevs(ui, r1, r2, order, tr): | 187 def writerevs(ui, r1, r2, order, tr): |
168 | 188 |