Mercurial > public > mercurial-scm > hg-stable
comparison mercurial/revlog.py @ 9991:a7d11deb47dd
revlog: add fast path to ancestor
| author | Benoit Boissinot <benoit.boissinot@ens-lyon.org> |
|---|---|
| date | Thu, 03 Dec 2009 01:01:49 +0100 |
| parents | a1943c2a4661 |
| children | 5b9709f81986 |
comparison
equal
deleted
inserted
replaced
| 9990:c1d940d31aea | 9991:a7d11deb47dd |
|---|---|
| 1116 return node | 1116 return node |
| 1117 | 1117 |
| 1118 def ancestor(self, a, b): | 1118 def ancestor(self, a, b): |
| 1119 """calculate the least common ancestor of nodes a and b""" | 1119 """calculate the least common ancestor of nodes a and b""" |
| 1120 | 1120 |
| 1121 # fast path, check if it is a descendant | |
| 1122 a, b = self.rev(a), self.rev(b) | |
| 1123 start, end = sorted((a, b)) | |
| 1124 for i in self.descendants(start): | |
| 1125 if i == end: | |
| 1126 return self.node(start) | |
| 1127 elif i > end: | |
| 1128 break | |
| 1129 | |
| 1121 def parents(rev): | 1130 def parents(rev): |
| 1122 return [p for p in self.parentrevs(rev) if p != nullrev] | 1131 return [p for p in self.parentrevs(rev) if p != nullrev] |
| 1123 | 1132 |
| 1124 c = ancestor.ancestor(self.rev(a), self.rev(b), parents) | 1133 c = ancestor.ancestor(a, b, parents) |
| 1125 if c is None: | 1134 if c is None: |
| 1126 return nullid | 1135 return nullid |
| 1127 | 1136 |
| 1128 return self.node(c) | 1137 return self.node(c) |
| 1129 | 1138 |