diff --git a/rhodecode/controllers/branches.py b/rhodecode/controllers/branches.py --- a/rhodecode/controllers/branches.py +++ b/rhodecode/controllers/branches.py @@ -29,7 +29,7 @@ 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__) diff --git a/rhodecode/controllers/changeset.py b/rhodecode/controllers/changeset.py --- a/rhodecode/controllers/changeset.py +++ b/rhodecode/controllers/changeset.py @@ -34,12 +34,12 @@ 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__) diff --git a/rhodecode/controllers/summary.py b/rhodecode/controllers/summary.py --- a/rhodecode/controllers/summary.py +++ b/rhodecode/controllers/summary.py @@ -38,7 +38,8 @@ 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, \ diff --git a/rhodecode/controllers/tags.py b/rhodecode/controllers/tags.py --- a/rhodecode/controllers/tags.py +++ b/rhodecode/controllers/tags.py @@ -28,7 +28,7 @@ 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__) diff --git a/rhodecode/lib/celerylib/tasks.py b/rhodecode/lib/celerylib/tasks.py --- a/rhodecode/lib/celerylib/tasks.py +++ b/rhodecode/lib/celerylib/tasks.py @@ -41,7 +41,8 @@ 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 diff --git a/rhodecode/lib/odict.py b/rhodecode/lib/odict.py new file mode 100644 --- /dev/null +++ b/rhodecode/lib/odict.py @@ -0,0 +1,291 @@ +# 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 diff --git a/rhodecode/lib/oset.py b/rhodecode/lib/oset.py new file mode 100644 --- /dev/null +++ b/rhodecode/lib/oset.py @@ -0,0 +1,64 @@ +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 + diff --git a/rhodecode/lib/utils.py b/rhodecode/lib/utils.py --- a/rhodecode/lib/utils.py +++ b/rhodecode/lib/utils.py @@ -405,107 +405,6 @@ 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}