Show More
@@ -8,7 +8,7 b'' | |||||
8 | # This software may be used and distributed according to the terms |
|
8 | # This software may be used and distributed according to the terms | |
9 | # of the GNU General Public License, incorporated herein by reference. |
|
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 | from mercurial import mdiff |
|
12 | from mercurial import mdiff | |
13 |
|
13 | |||
14 | def hex(node): return binascii.hexlify(node) |
|
14 | def hex(node): return binascii.hexlify(node) | |
@@ -276,38 +276,42 b' class revlog:' | |||||
276 | return node |
|
276 | return node | |
277 |
|
277 | |||
278 | def ancestor(self, a, b): |
|
278 | def ancestor(self, a, b): | |
279 | def expand(list, map): |
|
279 | # calculate the distance of every node from root | |
280 | a = [] |
|
280 | dist = {nullid: 0} | |
281 | while list: |
|
281 | for i in xrange(self.count()): | |
282 |
|
|
282 | n = self.node(i) | |
283 | map[n] = 1 |
|
283 | p1, p2 = self.parents(n) | |
284 | yield n |
|
284 | dist[n] = max(dist[p1], dist[p2]) + 1 | |
285 | for p in self.parents(n): |
|
|||
286 | if p != nullid and p not in map: |
|
|||
287 | list.append(p) |
|
|||
288 | yield nullid |
|
|||
289 |
|
285 | |||
290 | amap = {} |
|
286 | # traverse ancestors in order of decreasing distance from root | |
291 | bmap = {} |
|
287 | def ancestors(node): | |
292 | ag = expand([a], amap) |
|
288 | # we store negative distances because heap returns smallest member | |
293 | bg = expand([b], bmap) |
|
289 | h = [(-dist[node], node)] | |
294 | adone = bdone = 0 |
|
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)) | |||
295 |
|
300 | |||
296 | while not adone or not bdone: |
|
301 | x = ancestors(a) | |
297 | if not adone: |
|
302 | y = ancestors(b) | |
298 |
|
|
303 | lx = x.next() | |
299 | if an == nullid: |
|
304 | ly = y.next() | |
300 | adone = 1 |
|
|||
301 | elif an in bmap: |
|
|||
302 | return an |
|
|||
303 | if not bdone: |
|
|||
304 | bn = bg.next() |
|
|||
305 | if bn == nullid: |
|
|||
306 | bdone = 1 |
|
|||
307 | elif bn in amap: |
|
|||
308 | return bn |
|
|||
309 |
|
305 | |||
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 | def group(self, linkmap): |
|
316 | def group(self, linkmap): | |
313 | # given a list of changeset revs, return a set of deltas and |
|
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