scmutil: add a dirs class

This encapsulates the "multiset of directories" structures that are
currently open-coded (and duplicated) in both the dirstate and
context modules.

This will be used, and optionally replaced by a C implementation,
in upcoming changes.

mercurial/scmutil.py

@@ -891,6 +891,42 b' class filecache(object):'
         except KeyError:
             raise AttributeError(self.name)
 
+class dirs(object):
+    '''a multiset of directory names from a dirstate or manifest'''
+
+    def __init__(self, map, skip=None):
+        self._dirs = {}
+        addpath = self.addpath
+        if util.safehasattr(map, 'iteritems') and skip is not None:
+            for f, s in map.iteritems():
+                if s[0] != skip:
+                    addpath(f)
+        else:
+            for f in map:
+                addpath(f)
+
+    def addpath(self, path):
+        dirs = self._dirs
+        for base in finddirs(path):
+            if base in dirs:
+                dirs[base] += 1
+                return
+            dirs[base] = 1
+
+    def delpath(self, path):
+        dirs = self._dirs
+        for base in finddirs(path):
+            if dirs[base] > 1:
+                dirs[base] -= 1
+                return
+            del dirs[base]
+
+    def __iter__(self):
+        return self._dirs.iterkeys()
+
+    def __contains__(self, d):
+        return d in self._dirs
+
 def finddirs(path):
     pos = path.rfind('/')
     while pos != -1: