1 from __future__ import division
6 from p2pool.util import deferral
9 def __init__(self, contents, prev=None, next=None):
10 self.contents, self.prev, self.next = contents, prev, next
12 def insert_before(self, contents):
13 self.prev.next = self.prev = node = Node(contents, self.prev, self)
16 def insert_after(self, contents):
17 self.next.prev = self.next = node = Node(contents, self, self.next)
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
26 def replace(self, contents):
27 self.contents = contents
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
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)
45 return 'LinkedList(%r)' % (list(self),)
48 return sum(1 for x in self)
52 while cur is not self.end:
55 yield cur2 # in case cur is deleted, but items inserted after are ignored
57 def __reversed__(self):
59 while cur is not self.start:
64 def __getitem__(self, index):
67 for i in xrange(-index):
70 raise IndexError('index out of range')
73 for i in xrange(index + 1):
76 raise IndexError('index out of range')
79 def appendleft(self, item):
80 return self.start.insert_after(item)
82 def append(self, item):
83 return self.end.insert_before(item)
86 node = self.start.next
88 raise IndexError('popleft from empty')
94 if node is self.start:
95 raise IndexError('pop from empty')
100 class ExpiringDict(object):
101 def __init__(self, expiry_time, get_touches=True):
102 self.expiry_time = expiry_time
103 self.get_touches = get_touches
105 self.expiry_deque = LinkedList()
106 self.d = dict() # key -> node, value
108 self_ref = weakref.ref(self, lambda _: expire_loop.stop() if expire_loop.running else None)
109 self._expire_loop = expire_loop = deferral.RobustLoopingCall(lambda: self_ref().expire())
113 self._expire_loop.stop()
116 return 'ExpiringDict' + repr(self.__dict__)
122 def touch(self, key, value=_nothing):
123 'Updates expiry node, optionally replacing value, returning new value'
124 if value is self._nothing or key in self.d:
125 node, old_value = self.d[key]
128 new_value = old_value if value is self._nothing else value
129 self.d[key] = self.expiry_deque.append((time.time() + self.expiry_time, key)), new_value
134 for node in self.expiry_deque:
135 timestamp, key = node.contents
141 def __contains__(self, key):
144 def __getitem__(self, key):
146 value = self.touch(key)
148 node, value = self.d[key]
151 def __setitem__(self, key, value):
152 self.touch(key, value)
154 def __delitem__(self, key):
155 node, value = self.d.pop(key)
158 def get(self, key, default_value=None):
165 def setdefault(self, key, default_value):
169 self[key] = default_value
176 return [value for node, value in self.d.itervalues()]
178 def itervalues(self):
179 for node, value in self.d.itervalues():