# HG changeset patch
# User Matt Mackall <mpm@selenic.com>
# Date 2011-01-12 03:52:03
# Node ID 3b616dfa4b17eec254ff9828128142f731f6b868
# Parent  c2661863f16f35c00c81726a9d055e773246682e

revlog: do revlog node->rev mapping by scanning

Now that the nodemap is lazily created, we use linear scanning back
from tip for typical node to rev mapping. Given that nodemap creation
is O(n log n) and revisions searched for are usually very close to
tip, this is often a significant performance win for a small number of
searches.

When we do end up building a nodemap for bulk lookups, the scanning
function is replaced with a hash lookup.

diff --git a/mercurial/revlog.py b/mercurial/revlog.py
--- a/mercurial/revlog.py
+++ b/mercurial/revlog.py
@@ -283,6 +283,7 @@ class revlog(object):
         i = self.index
         for r in xrange(len(i) - 1):
             n[i[r][7]] = r
+        self.rev = self._revmap
         return n
 
     def tip(self):
@@ -292,11 +293,20 @@ class revlog(object):
     def __iter__(self):
         for i in xrange(len(self)):
             yield i
-    def rev(self, node):
+    def _revmap(self, node):
         try:
             return self.nodemap[node]
         except KeyError:
             raise LookupError(node, self.indexfile, _('no node'))
+
+    def rev(self, node):
+        if node == nullid:
+            return nullrev
+        i = self.index
+        for r in xrange(len(i) - 2, -1, -1):
+            if i[r][7] == node:
+                return r
+        raise LookupError(node, self.indexfile, _('no node'))
     def node(self, rev):
         return self.index[rev][7]
     def linkrev(self, rev):
@@ -711,8 +721,8 @@ class revlog(object):
             try:
                 # hex(node)[:...]
                 l = len(id) // 2  # grab an even number of digits
-                bin_id = bin(id[:l * 2])
-                nl = [n for n in self.nodemap if n[:l] == bin_id]
+                prefix = bin(id[:l * 2])
+                nl = [e[7] for e in self.index if e[7].startswith(prefix)]
                 nl = [n for n in nl if hex(n).startswith(id)]
                 if len(nl) > 0:
                     if len(nl) == 1: