openerp/tools/lru.py

   1 # -*- coding: utf-8 -*-
   2 # taken from http://code.activestate.com/recipes/252524-length-limited-o1-lru-cache-implementation/
   3 import threading
   4 from func import synchronized
   5
   6 __all__ = ['LRU']
   7
   8 class LRUNode(object):
   9     __slots__ = ['prev', 'next', 'me']
  10     def __init__(self, prev, me):
  11         self.prev = prev
  12         self.me = me
  13         self.next = None
  14
  15 class LRU(object):
  16     """
  17     Implementation of a length-limited O(1) LRU queue.
  18     Built for and used by PyPE:
  19     http://pype.sourceforge.net
  20     Copyright 2003 Josiah Carlson.
  21     """
  22     def __init__(self, count, pairs=[]):
  23         self._lock = threading.RLock()
  24         self.count = max(count, 1)
  25         self.d = {}
  26         self.first = None
  27         self.last = None
  28         for key, value in pairs:
  29             self[key] = value
  30
  31     @synchronized()
  32     def __contains__(self, obj):
  33         return obj in self.d
  34
  35     @synchronized()
  36     def __getitem__(self, obj):
  37         a = self.d[obj].me
  38         self[a[0]] = a[1]
  39         return a[1]
  40
  41     @synchronized()
  42     def __setitem__(self, obj, val):
  43         if obj in self.d:
  44             del self[obj]
  45         nobj = LRUNode(self.last, (obj, val))
  46         if self.first is None:
  47             self.first = nobj
  48         if self.last:
  49             self.last.next = nobj
  50         self.last = nobj
  51         self.d[obj] = nobj
  52         if len(self.d) > self.count:
  53             if self.first == self.last:
  54                 self.first = None
  55                 self.last = None
  56                 return
  57             a = self.first
  58             a.next.prev = None
  59             self.first = a.next
  60             a.next = None
  61             del self.d[a.me[0]]
  62             del a
  63
  64     @synchronized()
  65     def __delitem__(self, obj):
  66         nobj = self.d[obj]
  67         if nobj.prev:
  68             nobj.prev.next = nobj.next
  69         else:
  70             self.first = nobj.next
  71         if nobj.next:
  72             nobj.next.prev = nobj.prev
  73         else:
  74             self.last = nobj.prev
  75         del self.d[obj]
  76
  77     @synchronized()
  78     def __iter__(self):
  79         cur = self.first
  80         while cur is not None:
  81             cur2 = cur.next
  82             yield cur.me[1]
  83             cur = cur2
  84
  85     @synchronized()
  86     def __len__(self):
  87         return len(self.d)
  88
  89     @synchronized()
  90     def iteritems(self):
  91         cur = self.first
  92         while cur is not None:
  93             cur2 = cur.next
  94             yield cur.me
  95             cur = cur2
  96
  97     @synchronized()
  98     def iterkeys(self):
  99         return iter(self.d)
 100
 101     @synchronized()
 102     def itervalues(self):
 103         for i,j in self.iteritems():
 104             yield j
 105
 106     @synchronized()
 107     def keys(self):
 108         return self.d.keys()
 109
 110     @synchronized()
 111     def pop(self,key):
 112         v=self[key]
 113         del self[key]
 114         return v
 115
 116     @synchronized()
 117     def clear(self):
 118         self.d = {}
 119         self.first = None
 120         self.last = None
 121
 122 # vim:expandtab:smartindent:tabstop=4:softtabstop=4:shiftwidth=4: