Changed OrderedDict implementation to pypy odict, in general it's the fastest and most reliable solution. Added OrderedTuple from python foundation.

rhodecode/lib/odict.py

@@ -0,0 +1,291 b''
+# Python Software Foundation License
+
+# XXX: it feels like using the class with "is" and "is not" instead of "==" and
+# "!=" should be faster.
+class _Nil(object):
+
+    def __repr__(self):
+        return "nil"
+
+    def __eq__(self, other):
+        if (isinstance(other, _Nil)):
+            return True
+        else:
+            return NotImplemented
+
+    def __ne__(self, other):
+        if (isinstance(other, _Nil)):
+            return False
+        else:
+            return NotImplemented
+
+_nil = _Nil()
+
+class _odict(object):
+    """Ordered dict data structure, with O(1) complexity for dict operations
+    that modify one element.
+    
+    Overwriting values doesn't change their original sequential order.
+    """
+
+    def _dict_impl(self):
+        return None
+
+    def __init__(self, data=(), **kwds):
+        """This doesn't accept keyword initialization as normal dicts to avoid
+        a trap - inside a function or method the keyword args are accessible
+        only as a dict, without a defined order, so their original order is
+        lost.
+        """
+        if kwds:
+            raise TypeError("__init__() of ordered dict takes no keyword "
+                            "arguments to avoid an ordering trap.")
+        self._dict_impl().__init__(self)
+        # If you give a normal dict, then the order of elements is undefined
+        if hasattr(data, "iteritems"):
+            for key, val in data.iteritems():
+                self[key] = val
+        else:
+            for key, val in data:
+                self[key] = val
+
+    # Double-linked list header
+    def _get_lh(self):
+        dict_impl = self._dict_impl()
+        if not hasattr(self, '_lh'):
+            dict_impl.__setattr__(self, '_lh', _nil)
+        return dict_impl.__getattribute__(self, '_lh')
+
+    def _set_lh(self, val):
+        self._dict_impl().__setattr__(self, '_lh', val)
+
+    lh = property(_get_lh, _set_lh)
+
+    # Double-linked list tail
+    def _get_lt(self):
+        dict_impl = self._dict_impl()
+        if not hasattr(self, '_lt'):
+            dict_impl.__setattr__(self, '_lt', _nil)
+        return dict_impl.__getattribute__(self, '_lt')
+
+    def _set_lt(self, val):
+        self._dict_impl().__setattr__(self, '_lt', val)
+
+    lt = property(_get_lt, _set_lt)
+
+    def __getitem__(self, key):
+        return self._dict_impl().__getitem__(self, key)[1]
+
+    def __setitem__(self, key, val):
+        dict_impl = self._dict_impl()
+        try:
+            dict_impl.__getitem__(self, key)[1] = val
+        except KeyError, e:
+            new = [dict_impl.__getattribute__(self, 'lt'), val, _nil]
+            dict_impl.__setitem__(self, key, new)
+            if dict_impl.__getattribute__(self, 'lt') == _nil:
+                dict_impl.__setattr__(self, 'lh', key)
+            else:
+                dict_impl.__getitem__(
+                    self, dict_impl.__getattribute__(self, 'lt'))[2] = key
+            dict_impl.__setattr__(self, 'lt', key)
+
+    def __delitem__(self, key):
+        dict_impl = self._dict_impl()
+        pred, _ , succ = self._dict_impl().__getitem__(self, key)
+        if pred == _nil:
+            dict_impl.__setattr__(self, 'lh', succ)
+        else:
+            dict_impl.__getitem__(self, pred)[2] = succ
+        if succ == _nil:
+            dict_impl.__setattr__(self, 'lt', pred)
+        else:
+            dict_impl.__getitem__(self, succ)[0] = pred
+        dict_impl.__delitem__(self, key)
+
+    def __contains__(self, key):
+        return key in self.keys()
+
+    def __len__(self):
+        return len(self.keys())
+
+    def __str__(self):
+        pairs = ("%r: %r" % (k, v) for k, v in self.iteritems())
+        return "{%s}" % ", ".join(pairs)
+
+    def __repr__(self):
+        if self:
+            pairs = ("(%r, %r)" % (k, v) for k, v in self.iteritems())
+            return "odict([%s])" % ", ".join(pairs)
+        else:
+            return "odict()"
+
+    def get(self, k, x=None):
+        if k in self:
+            return self._dict_impl().__getitem__(self, k)[1]
+        else:
+            return x
+
+    def __iter__(self):
+        dict_impl = self._dict_impl()
+        curr_key = dict_impl.__getattribute__(self, 'lh')
+        while curr_key != _nil:
+            yield curr_key
+            curr_key = dict_impl.__getitem__(self, curr_key)[2]
+
+    iterkeys = __iter__
+
+    def keys(self):
+        return list(self.iterkeys())
+
+    def itervalues(self):
+        dict_impl = self._dict_impl()
+        curr_key = dict_impl.__getattribute__(self, 'lh')
+        while curr_key != _nil:
+            _, val, curr_key = dict_impl.__getitem__(self, curr_key)
+            yield val
+
+    def values(self):
+        return list(self.itervalues())
+
+    def iteritems(self):
+        dict_impl = self._dict_impl()
+        curr_key = dict_impl.__getattribute__(self, 'lh')
+        while curr_key != _nil:
+            _, val, next_key = dict_impl.__getitem__(self, curr_key)
+            yield curr_key, val
+            curr_key = next_key
+
+    def items(self):
+        return list(self.iteritems())
+
+    def sort(self, cmp=None, key=None, reverse=False):
+        items = [(k, v) for k, v in self.items()]
+        if cmp is not None:
+            items = sorted(items, cmp=cmp)
+        elif key is not None:
+            items = sorted(items, key=key)
+        else:
+            items = sorted(items, key=lambda x: x[1])
+        if reverse:
+            items.reverse()
+        self.clear()
+        self.__init__(items)
+
+    def clear(self):
+        dict_impl = self._dict_impl()
+        dict_impl.clear(self)
+        dict_impl.__setattr__(self, 'lh', _nil)
+        dict_impl.__setattr__(self, 'lt', _nil)
+
+    def copy(self):
+        return self.__class__(self)
+
+    def update(self, data=(), **kwds):
+        if kwds:
+            raise TypeError("update() of ordered dict takes no keyword "
+                            "arguments to avoid an ordering trap.")
+        if hasattr(data, "iteritems"):
+            data = data.iteritems()
+        for key, val in data:
+            self[key] = val
+
+    def setdefault(self, k, x=None):
+        try:
+            return self[k]
+        except KeyError:
+            self[k] = x
+            return x
+
+    def pop(self, k, x=_nil):
+        try:
+            val = self[k]
+            del self[k]
+            return val
+        except KeyError:
+            if x == _nil:
+                raise
+            return x
+
+    def popitem(self):
+        try:
+            dict_impl = self._dict_impl()
+            key = dict_impl.__getattribute__(self, 'lt')
+            return key, self.pop(key)
+        except KeyError:
+            raise KeyError("'popitem(): ordered dictionary is empty'")
+
+    def riterkeys(self):
+        """To iterate on keys in reversed order.
+        """
+        dict_impl = self._dict_impl()
+        curr_key = dict_impl.__getattribute__(self, 'lt')
+        while curr_key != _nil:
+            yield curr_key
+            curr_key = dict_impl.__getitem__(self, curr_key)[0]
+
+    __reversed__ = riterkeys
+
+    def rkeys(self):
+        """List of the keys in reversed order.
+        """
+        return list(self.riterkeys())
+
+    def ritervalues(self):
+        """To iterate on values in reversed order.
+        """
+        dict_impl = self._dict_impl()
+        curr_key = dict_impl.__getattribute__(self, 'lt')
+        while curr_key != _nil:
+            curr_key, val, _ = dict_impl.__getitem__(self, curr_key)
+            yield val
+
+    def rvalues(self):
+        """List of the values in reversed order.
+        """
+        return list(self.ritervalues())
+
+    def riteritems(self):
+        """To iterate on (key, value) in reversed order.
+        """
+        dict_impl = self._dict_impl()
+        curr_key = dict_impl.__getattribute__(self, 'lt')
+        while curr_key != _nil:
+            pred_key, val, _ = dict_impl.__getitem__(self, curr_key)
+            yield curr_key, val
+            curr_key = pred_key
+
+    def ritems(self):
+        """List of the (key, value) in reversed order.
+        """
+        return list(self.riteritems())
+
+    def firstkey(self):
+        if self:
+            return self._dict_impl().__getattribute__(self, 'lh')
+        else:
+            raise KeyError("'firstkey(): ordered dictionary is empty'")
+
+    def lastkey(self):
+        if self:
+            return self._dict_impl().__getattribute__(self, 'lt')
+        else:
+            raise KeyError("'lastkey(): ordered dictionary is empty'")
+
+    def as_dict(self):
+        return self._dict_impl()(self.items())
+
+    def _repr(self):
+        """_repr(): low level repr of the whole data contained in the odict.
+        Useful for debugging.
+        """
+        dict_impl = self._dict_impl()
+        form = "odict low level repr lh,lt,data: %r, %r, %s"
+        return form % (dict_impl.__getattribute__(self, 'lh'),
+                       dict_impl.__getattribute__(self, 'lt'),
+                       dict_impl.__repr__(self))
+
+class OrderedDict(_odict, dict):
+
+    def _dict_impl(self):
+        return dict

rhodecode/lib/oset.py

@@ -0,0 +1,64 b''
+KEY, PREV, NEXT = range(3)
+import collections
+
+class OrderedSet(collections.MutableSet):
+
+    def __init__(self, iterable=None):
+        self.end = end = []
+        end += [None, end, end]         # sentinel node for doubly linked list
+        self.map = {}                   # key --> [key, prev, next]
+        if iterable is not None:
+            self |= iterable
+
+    def __len__(self):
+        return len(self.map)
+
+    def __contains__(self, key):
+        return key in self.map
+
+    def add(self, key):
+        if key not in self.map:
+            end = self.end
+            curr = end[PREV]
+            curr[NEXT] = end[PREV] = self.map[key] = [key, curr, end]
+
+    def discard(self, key):
+        if key in self.map:
+            key, prev, next = self.map.pop(key)
+            prev[NEXT] = next
+            next[PREV] = prev
+
+    def __iter__(self):
+        end = self.end
+        curr = end[NEXT]
+        while curr is not end:
+            yield curr[KEY]
+            curr = curr[NEXT]
+
+    def __reversed__(self):
+        end = self.end
+        curr = end[PREV]
+        while curr is not end:
+            yield curr[KEY]
+            curr = curr[PREV]
+
+    def pop(self, last=True):
+        if not self:
+            raise KeyError('set is empty')
+        key = next(reversed(self)) if last else next(iter(self))
+        self.discard(key)
+        return key
+
+    def __repr__(self):
+        if not self:
+            return '%s()' % (self.__class__.__name__,)
+        return '%s(%r)' % (self.__class__.__name__, list(self))
+
+    def __eq__(self, other):
+        if isinstance(other, OrderedSet):
+            return len(self) == len(other) and list(self) == list(other)
+        return set(self) == set(other)
+
+    def __del__(self):
+        self.clear()                    # remove circular references
+

rhodecode/controllers/branches.py

@@ -29,7 +29,7 b' from pylons import tmpl_context as c'
 
 from rhodecode.lib.auth import LoginRequired, HasRepoPermissionAnyDecorator
 from rhodecode.lib.base import BaseRepoController, render
-from rhodecode.lib.utils import OrderedDict
+from rhodecode.lib.odict import OrderedDict
 
 log = logging.getLogger(__name__)
 

rhodecode/controllers/changeset.py

@@ -34,12 +34,12 b' import rhodecode.lib.helpers as h'
 from rhodecode.lib.auth import LoginRequired, HasRepoPermissionAnyDecorator
 from rhodecode.lib.base import BaseRepoController, render
 from rhodecode.lib.utils import EmptyChangeset
+from rhodecode.lib.odict import OrderedDict
 
 from vcs.exceptions import RepositoryError, ChangesetError, \
 ChangesetDoesNotExistError
 from vcs.nodes import FileNode
 from vcs.utils import diffs as differ
-from vcs.utils.ordered_dict import OrderedDict
 
 log = logging.getLogger(__name__)
 

rhodecode/controllers/summary.py

@@ -38,7 +38,8 b' from rhodecode.model.repo import RepoMod'
 
 from rhodecode.lib.auth import LoginRequired, HasRepoPermissionAnyDecorator
 from rhodecode.lib.base import BaseRepoController, render
-from rhodecode.lib.utils import OrderedDict, EmptyChangeset
+from rhodecode.lib.utils import EmptyChangeset
+from rhodecode.lib.odict import OrderedDict
 
 from rhodecode.lib.celerylib import run_task
 from rhodecode.lib.celerylib.tasks import get_commits_stats, \

rhodecode/controllers/tags.py

@@ -28,7 +28,7 b' from pylons import tmpl_context as c'
 
 from rhodecode.lib.auth import LoginRequired, HasRepoPermissionAnyDecorator
 from rhodecode.lib.base import BaseRepoController, render
-from rhodecode.lib.utils import OrderedDict
+from rhodecode.lib.odict import OrderedDict
 
 log = logging.getLogger(__name__)
 

rhodecode/lib/celerylib/tasks.py

@@ -41,7 +41,8 b' from rhodecode.lib.celerylib import run_'
     __get_lockkey, LockHeld, DaemonLock
 from rhodecode.lib.helpers import person
 from rhodecode.lib.smtp_mailer import SmtpMailer
-from rhodecode.lib.utils import OrderedDict, add_cache
+from rhodecode.lib.utils import add_cache
+from rhodecode.lib.odict import OrderedDict
 from rhodecode.model import init_model
 from rhodecode.model import meta
 from rhodecode.model.db import RhodeCodeUi, Statistics, Repository

rhodecode/lib/utils.py

@@ -405,107 +405,6 b' def repo2db_mapper(initial_repo_list, re'
 
     return added, removed
 
-
-class OrderedDict(dict, DictMixin):
-
-    def __init__(self, *args, **kwds):
-        if len(args) > 1:
-            raise TypeError('expected at most 1 arguments, got %d' % len(args))
-        try:
-            self.__end
-        except AttributeError:
-            self.clear()
-        self.update(*args, **kwds)
-
-    def clear(self):
-        self.__end = end = []
-        end += [None, end, end]         # sentinel node for doubly linked list
-        self.__map = {}                 # key --> [key, prev, next]
-        dict.clear(self)
-
-    def __setitem__(self, key, value):
-        if key not in self:
-            end = self.__end
-            curr = end[1]
-            curr[2] = end[1] = self.__map[key] = [key, curr, end]
-        dict.__setitem__(self, key, value)
-
-    def __delitem__(self, key):
-        dict.__delitem__(self, key)
-        key, prev, next = self.__map.pop(key)
-        prev[2] = next
-        next[1] = prev
-
-    def __iter__(self):
-        end = self.__end
-        curr = end[2]
-        while curr is not end:
-            yield curr[0]
-            curr = curr[2]
-
-    def __reversed__(self):
-        end = self.__end
-        curr = end[1]
-        while curr is not end:
-            yield curr[0]
-            curr = curr[1]
-
-    def popitem(self, last=True):
-        if not self:
-            raise KeyError('dictionary is empty')
-        if last:
-            key = reversed(self).next()
-        else:
-            key = iter(self).next()
-        value = self.pop(key)
-        return key, value
-
-    def __reduce__(self):
-        items = [[k, self[k]] for k in self]
-        tmp = self.__map, self.__end
-        del self.__map, self.__end
-        inst_dict = vars(self).copy()
-        self.__map, self.__end = tmp
-        if inst_dict:
-            return (self.__class__, (items,), inst_dict)
-        return self.__class__, (items,)
-
-    def keys(self):
-        return list(self)
-
-    setdefault = DictMixin.setdefault
-    update = DictMixin.update
-    pop = DictMixin.pop
-    values = DictMixin.values
-    items = DictMixin.items
-    iterkeys = DictMixin.iterkeys
-    itervalues = DictMixin.itervalues
-    iteritems = DictMixin.iteritems
-
-    def __repr__(self):
-        if not self:
-            return '%s()' % (self.__class__.__name__,)
-        return '%s(%r)' % (self.__class__.__name__, self.items())
-
-    def copy(self):
-        return self.__class__(self)
-
-    @classmethod
-    def fromkeys(cls, iterable, value=None):
-        d = cls()
-        for key in iterable:
-            d[key] = value
-        return d
-
-    def __eq__(self, other):
-        if isinstance(other, OrderedDict):
-            return len(self) == len(other) and self.items() == other.items()
-        return dict.__eq__(self, other)
-
-    def __ne__(self, other):
-        return not self == other
-
-
 #set cache regions for beaker so celery can utilise it
 def add_cache(settings):
     cache_settings = {'regions': None}