Show More
@@ -9,6 +9,62 b' import heapq' | |||||
9 | import util |
|
9 | import util | |
10 | from node import nullrev |
|
10 | from node import nullrev | |
11 |
|
11 | |||
|
12 | def commonancestorsheads(pfunc, *nodes): | |||
|
13 | """Returns a set with the heads of all common ancestors of all nodes, | |||
|
14 | heads(::nodes[0] and ::nodes[1] and ...) . | |||
|
15 | ||||
|
16 | pfunc must return a list of parent vertices for a given vertex. | |||
|
17 | """ | |||
|
18 | if not isinstance(nodes, set): | |||
|
19 | nodes = set(nodes) | |||
|
20 | if nullrev in nodes: | |||
|
21 | return set() | |||
|
22 | if len(nodes) <= 1: | |||
|
23 | return nodes | |||
|
24 | ||||
|
25 | allseen = (1 << len(nodes)) - 1 | |||
|
26 | seen = [0] * (max(nodes) + 1) | |||
|
27 | for i, n in enumerate(nodes): | |||
|
28 | seen[n] = 1 << i | |||
|
29 | poison = 1 << (i + 1) | |||
|
30 | ||||
|
31 | gca = set() | |||
|
32 | interesting = len(nodes) | |||
|
33 | nv = len(seen) - 1 | |||
|
34 | while nv >= 0 and interesting: | |||
|
35 | v = nv | |||
|
36 | nv -= 1 | |||
|
37 | if not seen[v]: | |||
|
38 | continue | |||
|
39 | sv = seen[v] | |||
|
40 | if sv < poison: | |||
|
41 | interesting -= 1 | |||
|
42 | if sv == allseen: | |||
|
43 | gca.add(v) | |||
|
44 | sv |= poison | |||
|
45 | if v in nodes: | |||
|
46 | # history is linear | |||
|
47 | return set([v]) | |||
|
48 | if sv < poison: | |||
|
49 | for p in pfunc(v): | |||
|
50 | sp = seen[p] | |||
|
51 | if p == nullrev: | |||
|
52 | continue | |||
|
53 | if sp == 0: | |||
|
54 | seen[p] = sv | |||
|
55 | interesting += 1 | |||
|
56 | elif sp != sv: | |||
|
57 | seen[p] |= sv | |||
|
58 | else: | |||
|
59 | for p in pfunc(v): | |||
|
60 | if p == nullrev: | |||
|
61 | continue | |||
|
62 | sp = seen[p] | |||
|
63 | if sp and sp < poison: | |||
|
64 | interesting -= 1 | |||
|
65 | seen[p] = sv | |||
|
66 | return gca | |||
|
67 | ||||
12 | def ancestors(pfunc, *orignodes): |
|
68 | def ancestors(pfunc, *orignodes): | |
13 | """ |
|
69 | """ | |
14 | Returns the common ancestors of a and b that are furthest from a |
|
70 | Returns the common ancestors of a and b that are furthest from a | |
@@ -16,57 +72,6 b' def ancestors(pfunc, *orignodes):' | |||||
16 |
|
72 | |||
17 | pfunc must return a list of parent vertices for a given vertex. |
|
73 | pfunc must return a list of parent vertices for a given vertex. | |
18 | """ |
|
74 | """ | |
19 | if not isinstance(orignodes, set): |
|
|||
20 | orignodes = set(orignodes) |
|
|||
21 | if nullrev in orignodes: |
|
|||
22 | return set() |
|
|||
23 | if len(orignodes) <= 1: |
|
|||
24 | return orignodes |
|
|||
25 |
|
||||
26 | def candidates(nodes): |
|
|||
27 | allseen = (1 << len(nodes)) - 1 |
|
|||
28 | seen = [0] * (max(nodes) + 1) |
|
|||
29 | for i, n in enumerate(nodes): |
|
|||
30 | seen[n] = 1 << i |
|
|||
31 | poison = 1 << (i + 1) |
|
|||
32 |
|
||||
33 | gca = set() |
|
|||
34 | interesting = len(nodes) |
|
|||
35 | nv = len(seen) - 1 |
|
|||
36 | while nv >= 0 and interesting: |
|
|||
37 | v = nv |
|
|||
38 | nv -= 1 |
|
|||
39 | if not seen[v]: |
|
|||
40 | continue |
|
|||
41 | sv = seen[v] |
|
|||
42 | if sv < poison: |
|
|||
43 | interesting -= 1 |
|
|||
44 | if sv == allseen: |
|
|||
45 | gca.add(v) |
|
|||
46 | sv |= poison |
|
|||
47 | if v in nodes: |
|
|||
48 | # history is linear |
|
|||
49 | return set([v]) |
|
|||
50 | if sv < poison: |
|
|||
51 | for p in pfunc(v): |
|
|||
52 | sp = seen[p] |
|
|||
53 | if p == nullrev: |
|
|||
54 | continue |
|
|||
55 | if sp == 0: |
|
|||
56 | seen[p] = sv |
|
|||
57 | interesting += 1 |
|
|||
58 | elif sp != sv: |
|
|||
59 | seen[p] |= sv |
|
|||
60 | else: |
|
|||
61 | for p in pfunc(v): |
|
|||
62 | if p == nullrev: |
|
|||
63 | continue |
|
|||
64 | sp = seen[p] |
|
|||
65 | if sp and sp < poison: |
|
|||
66 | interesting -= 1 |
|
|||
67 | seen[p] = sv |
|
|||
68 | return gca |
|
|||
69 |
|
||||
70 | def deepest(nodes): |
|
75 | def deepest(nodes): | |
71 | interesting = {} |
|
76 | interesting = {} | |
72 | count = max(nodes) + 1 |
|
77 | count = max(nodes) + 1 | |
@@ -123,7 +128,7 b' def ancestors(pfunc, *orignodes):' | |||||
123 | k |= i |
|
128 | k |= i | |
124 | return set(n for (i, n) in mapping if k & i) |
|
129 | return set(n for (i, n) in mapping if k & i) | |
125 |
|
130 | |||
126 |
gca = c |
|
131 | gca = commonancestorsheads(pfunc, *orignodes) | |
127 |
|
132 | |||
128 | if len(gca) <= 1: |
|
133 | if len(gca) <= 1: | |
129 | return gca |
|
134 | return gca |
General Comments 0
You need to be logged in to leave comments.
Login now