Mercurial > public > mercurial-scm > hg-stable

comparison mercurial/revlog.py @ 38517:6db38c9d7e00

Find changesets by keywords (author, files, the commit message), revision number or hash, or revset expression.
revlog: efficient implementation of 'descendant' Iterating over descendants is costly, because there are no "parent -> children" pointers. Walking the other way around is much more efficient, especially on large repositories, where descendant walks can cost seconds. And the other hand, common ancestors code follows links in the right direction and has a compiled implementation. In real life usage, this saved up to 80s during some pull operations, where descendant test happens in extension code.
author Boris Feld <boris.feld@octobus.net>
date Fri, 22 Jun 2018 00:05:20 +0100
parents 99f864b34451
children cc3543c87de5
comparison
equal deleted inserted replaced
38516:99f864b34451 38517:6db38c9d7e00
1374 elif p == nullrev: 1374 elif p == nullrev:
1375 c.append(self.node(r)) 1375 c.append(self.node(r))
1376 return c 1376 return c
1377 1377
1378 def descendant(self, start, end): 1378 def descendant(self, start, end):
1379 """True if revision 'end' is an descendant of revision 'start'
1380
1381 A revision is considered as a descendant of itself."""
1379 if start == nullrev: 1382 if start == nullrev:
1380 return True 1383 return True
1381 elif start == end: 1384 elif start == end:
1382 return True 1385 return True
1383 for i in self.descendants([start]): 1386 return start in self._commonancestorsheads(start, end)
1384 if i == end:
1385 return True
1386 elif i > end:
1387 break
1388 return False
1389 1387
1390 def commonancestorsheads(self, a, b): 1388 def commonancestorsheads(self, a, b):
1391 """calculate all the heads of the common ancestors of nodes a and b""" 1389 """calculate all the heads of the common ancestors of nodes a and b"""
1392 a, b = self.rev(a), self.rev(b) 1390 a, b = self.rev(a), self.rev(b)
1393 ancs = self._commonancestorsheads(a, b) 1391 ancs = self._commonancestorsheads(a, b)