home *** CD-ROM | disk | FTP | other *** search
/ Maximum CD 2011 October / maximum-cd-2011-10.iso / DiscContents / digsby_setup.exe / lib / util / lrucache.pyo (.txt) < prev    next >
Encoding:
Python Compiled Bytecode  |  2011-06-22  |  5.9 KB  |  252 lines
  1. # Source Generated with Decompyle++
  2. # File: in.pyo (Python 2.6)
  3.  
  4. from __future__ import with_statement
  5. from collections import deque
  6. from threading import RLock
  7. from functools import wraps
  8. from pprint import pformat
  9. from timeit import default_timer
  10.  
  11. def lru_cache(maxsize):
  12.     lck = RLock()
  13.     
  14.     def decorating_function(f):
  15.         cache = { }
  16.         queue = deque()
  17.         refcount = { }
  18.         
  19.         def wrapper(*args, **kwargs):
  20.             lck.__enter__()
  21.             
  22.             try:
  23.                 _cache = cache
  24.                 _len = len
  25.                 _refcount = refcount
  26.                 _maxsize = maxsize
  27.                 queue_append = queue.append
  28.                 queue_popleft = queue.popleft
  29.                 key = args
  30.                 
  31.                 try:
  32.                     result = _cache[key]
  33.                 except KeyError:
  34.                     lck.__exit__
  35.                     lck.__exit__
  36.                     lck
  37.                     result = _cache[key] = f(*args, **kwargs)
  38.                 except:
  39.                     lck.__exit__
  40.  
  41.                 queue_append(key)
  42.                 _refcount[key] = _refcount.get(key, 0) + 1
  43.                 while _len(_cache) > _maxsize:
  44.                     k = queue_popleft()
  45.                     _refcount[k] -= 1
  46.                     if not _refcount[k]:
  47.                         del _cache[k]
  48.                         del _refcount[k]
  49.                         continue
  50.                     lck.__exit__
  51.                     continue
  52.                     lck
  53.                 if _len(queue) > _maxsize * 4:
  54.                     for i in [
  55.                         None] * _len(queue):
  56.                         k = queue_popleft()
  57.                         if _refcount[k] == 1:
  58.                             queue_append(k)
  59.                             continue
  60.                         _refcount[k] -= 1
  61.                     
  62.             finally:
  63.                 pass
  64.  
  65.             return result
  66.  
  67.         wrapper = (None, None, None, None, None, wraps(f))(wrapper)
  68.         return wrapper
  69.  
  70.     return decorating_function
  71.  
  72.  
  73. class MyDoublyLinkedListNode(object):
  74.     __slots__ = [
  75.         'data',
  76.         'prev',
  77.         'next']
  78.     
  79.     def __init__(self, data, prev = None, next = None):
  80.         self.data = data
  81.         self.prev = prev
  82.         self.next = next
  83.  
  84.     
  85.     def remove(self):
  86.         if self.prev is not None:
  87.             self.prev.next = self.next
  88.         
  89.         self.next.prev = self.prev
  90.  
  91.     
  92.     def append(self, node):
  93.         if self.next is not None:
  94.             raise NotImplementedError("I don't have use for real insertion")
  95.         self.next is not None
  96.         self.next = node
  97.         node.prev = self
  98.  
  99.     
  100.     def __repr__(self):
  101.         return '%s(%r, %r)' % (self.__class__.__name__, self.data, self.next)
  102.  
  103.  
  104.  
  105. class LRU(dict):
  106.     node_class = MyDoublyLinkedListNode
  107.     
  108.     def __init__(self, limit):
  109.         self._limit = limit
  110.         self._init()
  111.  
  112.     
  113.     def _init(self):
  114.         self._ll_head = self._ll_last = self.node_class(None)
  115.         self._ll_mapping = { }
  116.         self.lock = RLock()
  117.  
  118.     
  119.     def __setitem__(self, key, value):
  120.         self.lock.__enter__()
  121.         
  122.         try:
  123.             if self._ll_last.data == key:
  124.                 return dict.__setitem__(self, key, value)
  125.             if key in self:
  126.                 self._ll_mapping[key].remove()
  127.             elif len(self) == self._limit:
  128.                 self.pop_lru_key()
  129.             
  130.             new_node = self.node_class(key)
  131.             self._ll_last.append(new_node)
  132.             self._ll_last = new_node
  133.             self._ll_mapping[key] = new_node
  134.             dict.__setitem__(self, key, value)
  135.         finally:
  136.             pass
  137.  
  138.  
  139.     
  140.     def pop_lru_key(self):
  141.         key = self._ll_head.next.data
  142.         
  143.         try:
  144.             dict.__delitem__(self, key)
  145.         except KeyError:
  146.             pass
  147.  
  148.         
  149.         try:
  150.             del self._ll_mapping[key]
  151.         except KeyError:
  152.             pass
  153.  
  154.         self._ll_head.next.remove()
  155.         return key
  156.  
  157.     
  158.     def __delitem__(self, key):
  159.         raise NotImplementedError('Not necessary for LRU Cache')
  160.  
  161.  
  162.  
  163. class MyTimedDoublyLinkedListNode(MyDoublyLinkedListNode):
  164.     __slots__ = MyDoublyLinkedListNode.__slots__ + [
  165.         'created']
  166.     
  167.     def __init__(self, data, prev = None, next = None):
  168.         super(MyTimedDoublyLinkedListNode, self).__init__(data, prev, next)
  169.         self.created = default_timer()
  170.  
  171.  
  172.  
  173. class ExpiringLRU(LRU):
  174.     node_class = MyTimedDoublyLinkedListNode
  175.     
  176.     def __init__(self, time_limit):
  177.         self.time_limit = time_limit
  178.         self._init()
  179.  
  180.     
  181.     def _limit(self):
  182.         return len(self)
  183.  
  184.     _limit = property(_limit)
  185.     
  186.     def pop_lru_key(self):
  187.         while len(self) > 1:
  188.             key = self._ll_head.next.data
  189.             
  190.             try:
  191.                 val = self[key]
  192.             except KeyError:
  193.                 pass
  194.  
  195.             if self._ll_head.next.created + self.time_limit >= default_timer():
  196.                 return None
  197.             
  198.             try:
  199.                 dict.__delitem__(self, key)
  200.             except KeyError:
  201.                 self._ll_head.next.created + self.time_limit >= default_timer()
  202.                 self._ll_head.next.created + self.time_limit >= default_timer()
  203.             except:
  204.                 self._ll_head.next.created + self.time_limit >= default_timer()
  205.  
  206.             
  207.             try:
  208.                 del self._ll_mapping[key]
  209.             except KeyError:
  210.                 self._ll_head.next.created + self.time_limit >= default_timer()
  211.                 self._ll_head.next.created + self.time_limit >= default_timer()
  212.             except:
  213.                 self._ll_head.next.created + self.time_limit >= default_timer()
  214.  
  215.             self._ll_head.next.remove()
  216.             continue
  217.             self._ll_head.next.created + self.time_limit >= default_timer()
  218.  
  219.  
  220. if __name__ == '__main__':
  221.     c = LRU(3)
  222.     print c
  223.     c['a'] = 1
  224.     c['b'] = 2
  225.     c['c'] = 3
  226.     print c
  227.     c['c'] = 5
  228.     print c
  229.     c['a'] = 6
  230.     print c
  231.     print '####################'
  232.     d = ExpiringLRU(1)
  233.     d['a'] = 1
  234.     d['b'] = 2
  235.     print d
  236.     import time
  237.     print 'sleeping'
  238.     time.sleep(1.5)
  239.     print d
  240.     d['c'] = 3
  241.     d['d'] = 4
  242.     print d
  243.     print 'sleeping'
  244.     time.sleep(1.5)
  245.     print d
  246.     d['e'] = 5
  247.     d['c'] = 7
  248.     print d
  249.     d['f'] = 6
  250.     print d
  251.  
  252.