# HG changeset patch
# User Matt Mackall <mpm@selenic.com>
# Date 1190655398 18000
# Node ID 319c09685f30bd58fe0d130ed5e6cadee7b5b7b6
# Parent  5971cfc0a56a9ff9b324c8fa32f77b9ba21b0423
dirstate: make dir collision logic faster

- shortcircuit decpath if we haven't built the _dirs map
- increment only for leafnodes of directory tree
  (this should make construction more like O(nlog n) than O(n^2))

diff --git a/mercurial/dirstate.py b/mercurial/dirstate.py
--- a/mercurial/dirstate.py
+++ b/mercurial/dirstate.py
@@ -175,16 +175,27 @@ class dirstate(object):
         return self._copymap
 
     def _incpath(self, path):
-        for c in strutil.findall(path, '/'):
-            pc = path[:c]
-            self._dirs.setdefault(pc, 0)
-            self._dirs[pc] += 1
+        c = path.rfind('/')
+        if c >= 0:
+            dirs = self._dirs
+            base = path[:c]
+            if base not in dirs:
+                self._incpath(base)
+                dirs[base] = 1
+            else:
+                dirs[base] += 1
 
     def _decpath(self, path):
-        for c in strutil.findall(path, '/'):
-            pc = path[:c]
-            self._dirs.setdefault(pc, 0)
-            self._dirs[pc] -= 1
+        if "_dirs" in self.__dict__:
+            c = path.rfind('/')
+            if c >= 0:
+                base = path[:c]
+                dirs = self._dirs
+                if dirs[base] == 1:
+                    del dirs[base]
+                    self._decpath(base)
+                else:
+                    dirs[base] -= 1
 
     def _incpathcheck(self, f):
         if '\r' in f or '\n' in f: