changeset 5726:19cbe2aea2bc

bisect: switch individual ancestor lists from dict to list

This saves quite a lot of memory and increases performance

--- a/hgext/hbisect.py	Thu Dec 27 23:55:39 2007 -0600
+++ b/hgext/hbisect.py	Thu Dec 27 23:55:39 2007 -0600
@@ -79,7 +79,7 @@
             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:
@@ -95,12 +95,22 @@
 
         # accumulate ancestor lists
         for rev in xrange(badrev + 1):
-            if ancestors[rev] == {}:
-                ancestors[rev] = {rev: 1}
-                for p in clparents(rev):
-                    if ancestors[p]:
-                        # add parent ancestors to our ancestors
-                        ancestors[rev].update(ancestors[p])
+            if ancestors[rev] == []:
+                p1, p2 = clparents(rev)
+                a1, a2 = ancestors[p1], ancestors[p2]
+                if a1:
+                    if a2:
+                        # 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"))