changeset 35306:c9144396099b

dagop: use heap to compute max rev in filectxancestors()
author Yuya Nishihara <yuya@tcha.org>
date Thu, 22 Sep 2016 18:41:51 +0900
parents 2cb05e6043be
children 921680c3e2ea
files mercurial/dagop.py
diffstat 1 files changed, 4 insertions(+), 1 deletions(-) [+]
line wrap: on
line diff
--- a/mercurial/dagop.py	Sun Oct 22 18:57:42 2017 +0900
+++ b/mercurial/dagop.py	Thu Sep 22 18:41:51 2016 +0900
@@ -82,10 +82,12 @@
     Yields (rev, {fctx, ...}) pairs in descending order.
     """
     visit = {}
+    visitheap = []
     def addvisit(fctx):
         rev = fctx.rev()
         if rev not in visit:
             visit[rev] = set()
+            heapq.heappush(visitheap, -rev)  # max heap
         visit[rev].add(fctx)
 
     if followfirst:
@@ -96,12 +98,13 @@
     for c in fctxs:
         addvisit(c)
     while visit:
-        currev = max(visit)
+        currev = -heapq.heappop(visitheap)
         curfctxs = visit.pop(currev)
         yield currev, curfctxs
         for c in curfctxs:
             for parent in c.parents()[:cut]:
                 addvisit(parent)
+    assert not visitheap
 
 def filerevancestors(fctxs, followfirst=False):
     """Like filectx.ancestors(), but can walk from multiple files/revisions,