From 0b03163dbcd08e6327f8c143cf6d10916d47f49b Mon Sep 17 00:00:00 2001
From: "Eric S. Raymond" <esr@thyrsus.com>
Date: Thu, 13 Nov 2014 14:18:43 -0500
Subject: [PATCH] Avoid O(n**2) lookups via hashes. Regression test passes.

---
 src | 24 ++++++++++++------------
 1 file changed, 12 insertions(+), 12 deletions(-)

diff --git a/src b/src
index f78e342..a4af34c 100755
--- a/src
+++ b/src
@@ -178,6 +178,11 @@ class History:
         if not os.path.exists(backend.master(self.name)):
             croak("%s is not registered" % self.name)
         backend.parse(self)
+        self.by_revno_d = {}
+        self.by_native_d = {}
+        for item in self.revlist:
+            self.by_revno_d[item.revno] = item
+            self.by_native_d[item.revision] = item
     def __len__(self):
         return len(self.revlist)
     def current(self):
@@ -224,22 +229,17 @@ class History:
                 s = nxt
     def native_to_revno(self, revision):
         "Map a native ID to a revno"
-        for item in self.revlist:
-            if item.revision == revision:
-                return item.revno
-        return None
+        item = self.by_native_d.get(revision)
+        return item and item.revno
     def by_revno(self, revno):
         "Map a revno to a revision item."
-        for item in self.revlist:
-            if item.revno == revno:
-                return item
-        croak("{0} has no revno {1}".format(self.name, revno))
+        try:
+            return self.by_revno_d[revno]
+        except KeyError:
+            croak("{0} has no revno {1}".format(self.name, revno))
     def revno_to_native(self, revno):
         "Map a revno to a native ID"
-        for item in self.revlist:
-            if item.revno == revno:
-                return item.revision
-        croak("{0} has no revno {1}".format(self.name, revno))
+        return self.by_revno(revno).revision
 
 def help_method(*_args):
     "Summarize src commands, or (with argument) show help for a single command."
-- 
2.43.0