Patchwork [2,of,6] dagop: use heap to compute max rev in filectxancestors()

login
register
mail settings
Submitter Yuya Nishihara
Date Dec. 7, 2017, 3:09 p.m.
Message ID <06c09a740d66aa3e7abc.1512659360@mimosa>
Download mbox | patch
Permalink /patch/25997/
State Accepted
Headers show

Comments

Yuya Nishihara - Dec. 7, 2017, 3:09 p.m.
# HG changeset patch
# User Yuya Nishihara <yuya@tcha.org>
# Date 1474537311 -32400
#      Thu Sep 22 18:41:51 2016 +0900
# Node ID 06c09a740d66aa3e7abcf3104b84803c8b48ecad
# Parent  33687d121e08c716d8e41e0135b14c75c78c3fda
dagop: use heap to compute max rev in filectxancestors()

Patch

diff --git a/mercurial/dagop.py b/mercurial/dagop.py
--- a/mercurial/dagop.py
+++ b/mercurial/dagop.py
@@ -82,10 +82,12 @@  def filectxancestors(fctxs, followfirst=
     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 @@  def filectxancestors(fctxs, followfirst=
     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,