Mercurial: hgext/hbisect.py comparison

bisect: switch individual ancestor lists from dict to list This saves quite a lot of memory and increases performance

comparison

equal deleted inserted replaced

-:8114d4c915a7
+:19cbe2aea2bc
 if not self.goodnodes:
 self.ui.warn(_("No good revision given\n"))
 self.ui.warn(_("Marking the first revision as good\n"))
 # build ancestors array
-ancestors = [{}] * (cl.count() + 1) # an extra for [-1]
+ancestors = [[]] * (cl.count() + 1) # an extra for [-1]
 # clear goodnodes from array
 for good in self.goodnodes:
 ancestors[cl.rev(good)] = None
 for rev in xrange(cl.count(), -1, -1):
 raise util.Abort(_("Inconsistent state, %s:%s is good and bad")
 % (badrev, hg.short(bad)))
 # accumulate ancestor lists
 for rev in xrange(badrev + 1):
-if ancestors[rev] == {}:
+if ancestors[rev] == []:
-ancestors[rev] = {rev: 1}
+p1, p2 = clparents(rev)
-for p in clparents(rev):
+a1, a2 = ancestors[p1], ancestors[p2]
-if ancestors[p]:
+if a1:
-# add parent ancestors to our ancestors
+if a2:
-ancestors[rev].update(ancestors[p])
+# merge ancestor lists
+a = dict.fromkeys(a2)
+a.update(dict.fromkeys(a1))
+a[rev] = None
+ancestors[rev] = a.keys()
+else:
+ancestors[rev] = a1 + [rev]
+elif a2:
+ancestors[rev] = a2 + [rev]
+else:
+ancestors[rev] = [rev]
 if badrev not in ancestors[badrev]:
 raise util.Abort(_("Could not find the first bad revision"))
 # have we narrowed it down to one entry?

Mercurial > hg