changeset 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 c1d940d31aea
children e97dd3a8e8d7
files mercurial/revlog.py
diffstat 1 files changed, 10 insertions(+), 1 deletions(-) [+]
line wrap: on
line diff
--- a/mercurial/revlog.py	Tue Dec 01 16:19:53 2009 -0500
+++ b/mercurial/revlog.py	Thu Dec 03 01:01:49 2009 +0100
@@ -1118,10 +1118,19 @@
     def ancestor(self, a, b):
         """calculate the least common ancestor of nodes a and b"""
 
+        # fast path, check if it is a descendant
+        a, b = self.rev(a), self.rev(b)
+        start, end = sorted((a, b))
+        for i in self.descendants(start):
+            if i == end:
+                return self.node(start)
+            elif i > end:
+                break
+
         def parents(rev):
             return [p for p in self.parentrevs(rev) if p != nullrev]
 
-        c = ancestor.ancestor(self.rev(a), self.rev(b), parents)
+        c = ancestor.ancestor(a, b, parents)
         if c is None:
             return nullid