[PATCH 4 of 6 v2] dirstate: add _sortedfiles as groundwork for perf optimization

[Joshua Redstone]

# HG changeset patch
# User Joshua Redstone <joshua.redstone at fb.com>
# Date 1340635046 25200
# Node ID 8435841e0e7fc4bd06f28c881b4fd74a666f9688
# Parent  11fcee84922b9c121cfd69a96887f1bc813d9a47
dirstate: add _sortedfiles as groundwork for perf optimization

Add a dirstate._sortedfiles which is a sorted list of files currently in the
repository (not including removed files).  This will be used in future
patches to speed up hg-add.

diff --git a/mercurial/dirstate.py b/mercurial/dirstate.py
--- a/mercurial/dirstate.py
+++ b/mercurial/dirstate.py
@@ -11,6 +11,7 @@
 import scmutil, util, ignore, osutil, parsers, encoding
 import struct, os, stat, errno
 import cStringIO
+import bisect
 
 _format = ">cllll"
 propertycache = util.propertycache
@@ -147,6 +148,15 @@
     def _checkcase(self):
         return not util.checkcase(self._join('.hg'))
 
+    @propertycache
+    def _sortedfiles(self):
+        slist = [f for f in self._map if self._map[f][0] != 'r']
+        slist.sort()
+        return slist
+
+    def sortedfiles(self):
+        return self._sortedfiles
+
     def _join(self, f):
         # much faster than os.path.join()
         # it's safe because f is always a relative path
@@ -309,8 +319,13 @@
         return self._copymap
 
     def _droppath(self, f):
-        if self[f] not in "?r" and "_dirs" in self.__dict__:
-            _decdirs(self._dirs, f)
+        if self[f] not in "?r":
+            if "_dirs" in self.__dict__:
+                _decdirs(self._dirs, f)
+            if "_sortedfiles" in self.__dict__:
+                idx = bisect.bisect_left(self._sortedfiles, f)
+                assert self._sortedfiles[idx] == f
+                self._sortedfiles.pop(idx)
 
     def _addpath(self, f, state, mode, size, mtime, check=False):
         assert state not in "?r"
@@ -327,6 +342,8 @@
         if oldstate in "?r" and "_dirs" in self.__dict__:
             _incdirs(self._dirs, f)
         self._dirty = True
+        if self[f] not in "?r":
+            bisect.insort(self._sortedfiles, f)
         self._map[f] = (state, mode, size, mtime)
 
     def normal(self, f):
@@ -469,6 +486,8 @@
         self._map = {}
         if "_dirs" in self.__dict__:
             delattr(self, "_dirs")
+        if "_sortedfiles" in self.__dict__:
+            delattr(self, "_sortedfiles")
         self._copymap = {}
         self._pl = [nullid, nullid]
         self._lastnormaltime = 0