Show More
@@ -8,7 +8,7 b'' | |||
|
8 | 8 | # This software may be used and distributed according to the terms |
|
9 | 9 | # of the GNU General Public License, incorporated herein by reference. |
|
10 | 10 | |
|
11 | import zlib, struct, sha, os, tempfile, binascii | |
|
11 | import zlib, struct, sha, os, tempfile, binascii, heapq | |
|
12 | 12 | from mercurial import mdiff |
|
13 | 13 | |
|
14 | 14 | def hex(node): return binascii.hexlify(node) |
@@ -276,38 +276,42 b' class revlog:' | |||
|
276 | 276 | return node |
|
277 | 277 | |
|
278 | 278 | def ancestor(self, a, b): |
|
279 | def expand(list, map): | |
|
280 | a = [] | |
|
281 | while list: | |
|
282 |
|
|
|
283 | map[n] = 1 | |
|
284 | yield n | |
|
285 | for p in self.parents(n): | |
|
286 | if p != nullid and p not in map: | |
|
287 | list.append(p) | |
|
288 | yield nullid | |
|
279 | # calculate the distance of every node from root | |
|
280 | dist = {nullid: 0} | |
|
281 | for i in xrange(self.count()): | |
|
282 | n = self.node(i) | |
|
283 | p1, p2 = self.parents(n) | |
|
284 | dist[n] = max(dist[p1], dist[p2]) + 1 | |
|
285 | ||
|
286 | # traverse ancestors in order of decreasing distance from root | |
|
287 | def ancestors(node): | |
|
288 | # we store negative distances because heap returns smallest member | |
|
289 | h = [(-dist[node], node)] | |
|
290 | seen = {} | |
|
291 | earliest = self.count() | |
|
292 | while h: | |
|
293 | d, n = heapq.heappop(h) | |
|
294 | r = self.rev(n) | |
|
295 | if n not in seen: | |
|
296 | seen[n] = 1 | |
|
297 | yield (-d, n) | |
|
298 | for p in self.parents(n): | |
|
299 | heapq.heappush(h, (-dist[p], p)) | |
|
289 | 300 | |
|
290 | amap = {} | |
|
291 | bmap = {} | |
|
292 | ag = expand([a], amap) | |
|
293 | bg = expand([b], bmap) | |
|
294 | adone = bdone = 0 | |
|
301 | x = ancestors(a) | |
|
302 | y = ancestors(b) | |
|
303 | lx = x.next() | |
|
304 | ly = y.next() | |
|
295 | 305 | |
|
296 | while not adone or not bdone: | |
|
297 | if not adone: | |
|
298 | an = ag.next() | |
|
299 |
|
|
|
300 |
|
|
|
301 |
|
|
|
302 |
|
|
|
303 |
if |
|
|
304 |
|
|
|
305 | if bn == nullid: | |
|
306 | bdone = 1 | |
|
307 | elif bn in amap: | |
|
308 | return bn | |
|
309 | ||
|
310 | return nullid | |
|
306 | # increment each ancestor list until it is closer to root than | |
|
307 | # the other, or they match | |
|
308 | while 1: | |
|
309 | if lx == ly: | |
|
310 | return lx[1] | |
|
311 | elif lx < ly: | |
|
312 | ly = y.next() | |
|
313 | elif lx > ly: | |
|
314 | lx = x.next() | |
|
311 | 315 | |
|
312 | 316 | def group(self, linkmap): |
|
313 | 317 | # given a list of changeset revs, return a set of deltas and |
General Comments 0
You need to be logged in to leave comments.
Login now