kallithea Changeset - 37625d304a16

Changeset - 37625d304a16

Parent rev.

Child rev.

[Not reviewed]

beta

0 6 2

Marcin Kuzminski - 15 years ago 2011-05-15 18:18:00
marcin@python-works.com

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

8 files changed with 362 insertions and 106 deletions:

rhodecode/controllers/branches.py

rhodecode/controllers/changeset.py

rhodecode/controllers/summary.py

rhodecode/controllers/tags.py

rhodecode/lib/celerylib/tasks.py

rhodecode/lib/odict.py

291

rhodecode/lib/oset.py

rhodecode/lib/utils.py

101

0 comments (0 inline, 0 general)

rhodecode/controllers/branches.py

➞

Show inline comments

@@ @@ -26,13 +26,13 @@ @@
 import logging
 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__)
 class BranchesController(BaseRepoController):

rhodecode/controllers/changeset.py

➞

Show inline comments

@@ @@ -31,18 +31,18 @@ from pylons.i18n.translation import _ @@
 from pylons.controllers.util import redirect
 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__)
 class ChangesetController(BaseRepoController):

rhodecode/controllers/summary.py

➞

Show inline comments

@@ @@ -35,13 +35,14 @@ from pylons.i18n.translation import _ @@
 from rhodecode.model.db import Statistics, Repository
 from rhodecode.model.repo import RepoModel
 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, \
     LANGUAGES_EXTENSIONS_MAP
 from rhodecode.lib.helpers import RepoPage

rhodecode/controllers/tags.py

➞

Show inline comments

@@ @@ -25,13 +25,13 @@ @@
 import logging
 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__)
 class TagsController(BaseRepoController):

rhodecode/lib/celerylib/tasks.py

➞

Show inline comments

@@ @@ -38,13 +38,14 @@ from pylons.i18n.translation import _ @@
 from rhodecode.lib import LANGUAGES_EXTENSIONS_MAP
 from rhodecode.lib.celerylib import run_task, locked_task, str2bool, \
     __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
 from vcs.backends import get_repo

rhodecode/lib/odict.py

➞

Show inline comments

@@ new file 100644 @@
 # 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

➞

Show inline comments

@@ new file 100644 @@
 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/lib/utils.py

➞

Show inline comments

@@ @@ -402,113 +402,12 @@ def repo2db_mapper(initial_repo_list, re @@
                 removed.append(repo.repo_name)
                 sa.delete(repo)
                 sa.commit()
     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}
     for key in settings.keys():
         for prefix in ['beaker.cache.', 'cache.']:
             if key.startswith(prefix):

0 comments (0 inline, 0 general)