p2pool/util/expiring_dict.py

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