Mercurial > public > mercurial-scm > hg
comparison mercurial/revlog.py @ 2081:416d8b2a75b8
Speedup revlog.ancestors for the linear case
revlog.ancestors can be expensive on big repos. This cuts down the overall
time for hg update by ~19% by short cutting revlog.ancestors when one of the
revisions is reachable from another.
| author | Chris Mason <mason@suse.com> |
|---|---|
| date | Thu, 06 Apr 2006 20:13:09 -0400 |
| parents | 1cbb14c048cb |
| children | 856f0ba200bc |
comparison
equal
deleted
inserted
replaced
| 2080:1cbb14c048cb | 2081:416d8b2a75b8 |
|---|---|
| 938 self.cache = (node, n, text) | 938 self.cache = (node, n, text) |
| 939 return node | 939 return node |
| 940 | 940 |
| 941 def ancestor(self, a, b): | 941 def ancestor(self, a, b): |
| 942 """calculate the least common ancestor of nodes a and b""" | 942 """calculate the least common ancestor of nodes a and b""" |
| 943 | |
| 944 # start with some short cuts for the linear cases | |
| 945 if a == b: | |
| 946 return a | |
| 947 ra = self.rev(a) | |
| 948 rb = self.rev(b) | |
| 949 if ra < rb: | |
| 950 last = b | |
| 951 first = a | |
| 952 else: | |
| 953 last = a | |
| 954 first = b | |
| 955 | |
| 956 # reachable won't include stop in the list, so we have to use a parent | |
| 957 reachable = self.reachable(last, stop=self.parents(first)[0]) | |
| 958 if first in reachable: | |
| 959 return first | |
| 960 | |
| 943 # calculate the distance of every node from root | 961 # calculate the distance of every node from root |
| 944 dist = {nullid: 0} | 962 dist = {nullid: 0} |
| 945 for i in xrange(self.count()): | 963 for i in xrange(self.count()): |
| 946 n = self.node(i) | 964 n = self.node(i) |
| 947 p1, p2 = self.parents(n) | 965 p1, p2 = self.parents(n) |