p2pool/util/expiring_dict.py

   1 from __future__ import division
   2
   3 import time
   4
   5 from twisted.internet import task
   6
   7 class Node(object):
   8     def __init__(self, contents, prev=None, next=None):
   9         self.contents, self.prev, self.next = contents, prev, next
  10
  11     def insert_before(self, contents):
  12         self.prev.next = self.prev = node = Node(contents, self.prev, self)
  13         return node
  14
  15     def insert_after(self, contents):
  16         self.next.prev = self.next = node = Node(contents, self, self.next)
  17         return node
  18
  19     @staticmethod
  20     def connect(prev, next):
  21         if prev.next is not None or next.prev is not None:
  22             raise ValueError('node already connected')
  23         prev.next, next.prev = next, prev
  24
  25     def replace(self, contents):
  26         self.contents = contents
  27
  28     def delete(self):
  29         if self.prev.next is None or self.next.prev is None:
  30             raise ValueError('node not connected')
  31         self.prev.next, self.next.prev = self.next, self.prev
  32         self.next = self.prev = None
  33
  34
  35 class LinkedList(object):
  36     def __init__(self, iterable=[]):
  37         self.start, self.end = Node(None), Node(None)
  38         Node.connect(self.start, self.end)
  39
  40         for item in iterable:
  41             self.append(item)
  42
  43     def __repr__(self):
  44         return 'LinkedList(%r)' % (list(self),)
  45
  46     def __len__(self):
  47         return sum(1 for x in self)
  48
  49     def __iter__(self):
  50         cur = self.start.next
  51         while cur is not self.end:
  52             cur2 = cur
  53             cur = cur.next
  54             yield cur2 # in case cur is deleted, but items inserted after are ignored
  55
  56     def __reversed__(self):
  57         cur = self.end.prev
  58         while cur is not self.start:
  59             cur2 = cur
  60             cur = cur.prev
  61             yield cur2
  62
  63     def __getitem__(self, index):
  64         if index < 0:
  65             cur = self.end
  66             for i in xrange(-index):
  67                 cur = cur.prev
  68                 if cur is self.start:
  69                     raise IndexError('index out of range')
  70         else:
  71             cur = self.start
  72             for i in xrange(index + 1):
  73                 cur = cur.next
  74                 if cur is self.end:
  75                     raise IndexError('index out of range')
  76         return cur
  77
  78     def appendleft(self, item):
  79         return self.start.insert_after(item)
  80
  81     def append(self, item):
  82         return self.end.insert_before(item)
  83
  84     def popleft(self):
  85         node = self.start.next
  86         if node is self.end:
  87             raise IndexError('popleft from empty')
  88         node.delete()
  89         return node.contents
  90
  91     def pop(self):
  92         node = self.end.prev
  93         if node is self.start:
  94             raise IndexError('pop from empty')
  95         node.delete()
  96         return node.contents
  97
  98
  99 class ExpiringDict(object):
 100     def __init__(self, expiry_time, get_touches=True):
 101         self.expiry_time = expiry_time
 102         self.get_touches = get_touches
 103
 104         self.expiry_deque = LinkedList()
 105         self.d = dict() # key -> node, value
 106         self._expire_loop = task.LoopingCall(self.expire)
 107         self._expire_loop.start(1) # XXX use inlinecallbacks and stop expiring at some point
 108
 109     def stop(self):
 110         self._expire_loop.stop()
 111
 112     def __repr__(self):
 113         return 'ExpiringDict' + repr(self.__dict__)
 114
 115     def __len__(self):
 116         return len(self.d)
 117
 118     _nothing = object()
 119     def touch(self, key, value=_nothing):
 120         'Updates expiry node, optionally replacing value, returning new value'
 121         if value is self._nothing or key in self.d:
 122             node, old_value = self.d[key]
 123             node.delete()
 124
 125         new_value = old_value if value is self._nothing else value
 126         self.d[key] = self.expiry_deque.append((time.time() + self.expiry_time, key)), new_value
 127         return new_value
 128
 129     def expire(self):
 130         t = time.time()
 131         for node in self.expiry_deque:
 132             timestamp, key = node.contents
 133             if timestamp > t:
 134                 break
 135             del self.d[key]
 136             node.delete()
 137
 138     def __contains__(self, key):
 139         return key in self.d
 140
 141     def __getitem__(self, key):
 142         if self.get_touches:
 143             value = self.touch(key)
 144         else:
 145             node, value = self.d[key]
 146         return value
 147
 148     def __setitem__(self, key, value):
 149         self.touch(key, value)
 150
 151     def __delitem__(self, key):
 152         node, value = self.d.pop(key)
 153         node.delete()
 154
 155     def get(self, key, default_value=None):
 156         if key in self.d:
 157             res = self[key]
 158         else:
 159             res = default_value
 160         return res
 161
 162     def setdefault(self, key, default_value):
 163         if key in self.d:
 164             return self[key]
 165         else:
 166             self[key] = default_value
 167             return default_value
 168
 169     def keys(self):
 170         return self.d.keys()
 171
 172     def values(self):
 173         return [value for node, value in self.d.itervalues()]
 174
 175     def itervalues(self):
 176         for node, value in self.d.itervalues():
 177             yield value
 178
 179 if __name__ == '__main__':
 180     x = ExpiringDict(5)
 181     print x
 182
 183     time.sleep(1)
 184
 185     x[1] = 2
 186     print 'x[1] = 2'
 187     print x
 188
 189     time.sleep(1)
 190
 191     x[1] = 3
 192     print 'x[1] = 3'
 193     print x
 194
 195     time.sleep(5)
 196
 197     print x