7 from p2pool.util import skiplist, variable
10 class TrackerSkipList(skiplist.SkipList):
11 def __init__(self, tracker):
12 skiplist.SkipList.__init__(self)
13 self.tracker = tracker
15 self.tracker.removed.watch_weakref(self, lambda self, item: self.forget_item(item.hash))
17 def previous(self, element):
18 return self.tracker._delta_type.from_element(self.tracker.items[element]).tail
21 class DistanceSkipList(TrackerSkipList):
22 def get_delta(self, element):
23 return element, 1, self.previous(element)
25 def combine_deltas(self, (from_hash1, dist1, to_hash1), (from_hash2, dist2, to_hash2)):
26 if to_hash1 != from_hash2:
27 raise AssertionError()
28 return from_hash1, dist1 + dist2, to_hash2
30 def initial_solution(self, start, (n,)):
33 def apply_delta(self, (dist1, to_hash1), (from_hash2, dist2, to_hash2), (n,)):
34 if to_hash1 != from_hash2:
35 raise AssertionError()
36 return dist1 + dist2, to_hash2
38 def judge(self, (dist, hash), (n,)):
46 def finalize(self, (dist, hash), (n,)):
50 def get_attributedelta_type(attrs): # attrs: {name: func}
51 class ProtoAttributeDelta(object):
52 __slots__ = ['head', 'tail'] + attrs.keys()
55 def get_none(cls, element_id):
56 return cls(element_id, element_id, **dict((k, 0) for k in attrs))
59 def from_element(cls, item):
60 return cls(item.hash, item.previous_hash, **dict((k, v(item)) for k, v in attrs.iteritems()))
62 def __init__(self, head, tail, **kwargs):
63 self.head, self.tail = head, tail
64 for k, v in kwargs.iteritems():
67 def __add__(self, other):
68 assert self.tail == other.head
69 return self.__class__(self.head, other.tail, **dict((k, getattr(self, k) + getattr(other, k)) for k in attrs))
71 def __sub__(self, other):
72 if self.head == other.head:
73 return self.__class__(other.tail, self.tail, **dict((k, getattr(self, k) - getattr(other, k)) for k in attrs))
74 elif self.tail == other.tail:
75 return self.__class__(self.head, other.head, **dict((k, getattr(self, k) - getattr(other, k)) for k in attrs))
77 raise AssertionError()
80 return '%s(%r, %r%s)' % (self.__class__, self.head, self.tail, ''.join(', %s=%r' % (k, getattr(self, k)) for k in attrs))
81 ProtoAttributeDelta.attrs = attrs
82 return ProtoAttributeDelta
84 AttributeDelta = get_attributedelta_type(dict(
85 height=lambda item: 1,
88 class TrackerView(object):
89 def __init__(self, tracker, delta_type):
90 self._tracker = tracker
91 self._delta_type = delta_type
93 self._deltas = {} # item_hash -> delta, ref
94 self._reverse_deltas = {} # ref -> set of item_hashes
96 self._ref_generator = itertools.count()
97 self._delta_refs = {} # ref -> delta
98 self._reverse_delta_refs = {} # delta.tail -> ref
100 self._tracker.remove_special.watch_weakref(self, lambda self, item: self._handle_remove_special(item))
101 self._tracker.remove_special2.watch_weakref(self, lambda self, item: self._handle_remove_special2(item))
102 self._tracker.removed.watch_weakref(self, lambda self, item: self._handle_removed(item))
104 def _handle_remove_special(self, item):
105 delta = self._delta_type.from_element(item)
107 if delta.tail not in self._reverse_delta_refs:
110 # move delta refs referencing children down to this, so they can be moved up in one step
111 for x in list(self._reverse_deltas.get(self._reverse_delta_refs.get(delta.head, object()), set())):
114 assert delta.head not in self._reverse_delta_refs, list(self._reverse_deltas.get(self._reverse_delta_refs.get(delta.head, object()), set()))
116 if delta.tail not in self._reverse_delta_refs:
119 # move ref pointing to this up
121 ref = self._reverse_delta_refs[delta.tail]
122 cur_delta = self._delta_refs[ref]
123 assert cur_delta.tail == delta.tail
124 self._delta_refs[ref] = cur_delta - self._delta_type.from_element(item)
125 assert self._delta_refs[ref].tail == delta.head
126 del self._reverse_delta_refs[delta.tail]
127 self._reverse_delta_refs[delta.head] = ref
129 def _handle_remove_special2(self, item):
130 delta = self._delta_type.from_element(item)
132 if delta.tail not in self._reverse_delta_refs:
135 ref = self._reverse_delta_refs.pop(delta.tail)
136 del self._delta_refs[ref]
138 for x in self._reverse_deltas.pop(ref):
141 def _handle_removed(self, item):
142 delta = self._delta_type.from_element(item)
144 # delete delta entry and ref if it is empty
145 if delta.head in self._deltas:
146 delta1, ref = self._deltas.pop(delta.head)
147 self._reverse_deltas[ref].remove(delta.head)
148 if not self._reverse_deltas[ref]:
149 del self._reverse_deltas[ref]
150 delta2 = self._delta_refs.pop(ref)
151 del self._reverse_delta_refs[delta2.tail]
154 def get_height(self, item_hash):
155 return self.get_delta_to_last(item_hash).height
157 def get_work(self, item_hash):
158 return self.get_delta_to_last(item_hash).work
160 def get_last(self, item_hash):
161 return self.get_delta_to_last(item_hash).tail
163 def get_height_and_last(self, item_hash):
164 delta = self.get_delta_to_last(item_hash)
165 return delta.height, delta.tail
167 def _get_delta(self, item_hash):
168 if item_hash in self._deltas:
169 delta1, ref = self._deltas[item_hash]
170 delta2 = self._delta_refs[ref]
171 res = delta1 + delta2
173 res = self._delta_type.from_element(self._tracker.items[item_hash])
174 assert res.head == item_hash
177 def _set_delta(self, item_hash, delta):
178 other_item_hash = delta.tail
179 if other_item_hash not in self._reverse_delta_refs:
180 ref = self._ref_generator.next()
181 assert ref not in self._delta_refs
182 self._delta_refs[ref] = self._delta_type.get_none(other_item_hash)
183 self._reverse_delta_refs[other_item_hash] = ref
186 ref = self._reverse_delta_refs[other_item_hash]
187 ref_delta = self._delta_refs[ref]
188 assert ref_delta.tail == other_item_hash
190 if item_hash in self._deltas:
191 prev_ref = self._deltas[item_hash][1]
192 self._reverse_deltas[prev_ref].remove(item_hash)
193 if not self._reverse_deltas[prev_ref] and prev_ref != ref:
194 self._reverse_deltas.pop(prev_ref)
195 x = self._delta_refs.pop(prev_ref)
196 self._reverse_delta_refs.pop(x.tail)
197 self._deltas[item_hash] = delta - ref_delta, ref
198 self._reverse_deltas.setdefault(ref, set()).add(item_hash)
200 def get_delta_to_last(self, item_hash):
201 assert isinstance(item_hash, (int, long, type(None)))
202 delta = self._delta_type.get_none(item_hash)
204 while delta.tail in self._tracker.items:
205 updates.append((delta.tail, delta))
206 this_delta = self._get_delta(delta.tail)
208 for update_hash, delta_then in updates:
209 self._set_delta(update_hash, delta - delta_then)
212 def get_delta(self, item, ancestor):
213 assert self._tracker.is_child_of(ancestor, item)
214 return self.get_delta_to_last(item) - self.get_delta_to_last(ancestor)
216 class Tracker(object):
217 def __init__(self, items=[], delta_type=AttributeDelta):
218 self.items = {} # hash -> item
219 self.reverse = {} # delta.tail -> set of item_hashes
221 self.heads = {} # head hash -> tail_hash
222 self.tails = {} # tail hash -> set of head hashes
224 self.added = variable.Event()
225 self.remove_special = variable.Event()
226 self.remove_special2 = variable.Event()
227 self.removed = variable.Event()
229 self.get_nth_parent_hash = DistanceSkipList(self)
231 self._delta_type = delta_type
232 self._default_view = TrackerView(self, delta_type)
237 def __getattr__(self, name):
238 attr = getattr(self._default_view, name)
239 setattr(self, name, attr)
243 assert not isinstance(item, (int, long, type(None)))
244 delta = self._delta_type.from_element(item)
246 if delta.head in self.items:
247 raise ValueError('item already present')
249 if delta.head in self.tails:
250 heads = self.tails.pop(delta.head)
252 heads = set([delta.head])
254 if delta.tail in self.heads:
255 tail = self.heads.pop(delta.tail)
257 tail = self.get_last(delta.tail)
259 self.items[delta.head] = item
260 self.reverse.setdefault(delta.tail, set()).add(delta.head)
262 self.tails.setdefault(tail, set()).update(heads)
263 if delta.tail in self.tails[tail]:
264 self.tails[tail].remove(delta.tail)
267 self.heads[head] = tail
269 self.added.happened(item)
271 def remove(self, item_hash):
272 assert isinstance(item_hash, (int, long, type(None)))
273 if item_hash not in self.items:
276 item = self.items[item_hash]
279 delta = self._delta_type.from_element(item)
281 children = self.reverse.get(delta.head, set())
283 if delta.head in self.heads and delta.tail in self.tails:
284 tail = self.heads.pop(delta.head)
285 self.tails[tail].remove(delta.head)
286 if not self.tails[delta.tail]:
287 self.tails.pop(delta.tail)
288 elif delta.head in self.heads:
289 tail = self.heads.pop(delta.head)
290 self.tails[tail].remove(delta.head)
291 if self.reverse[delta.tail] != set([delta.head]):
294 self.tails[tail].add(delta.tail)
295 self.heads[delta.tail] = tail
296 elif delta.tail in self.tails and len(self.reverse[delta.tail]) <= 1:
297 heads = self.tails.pop(delta.tail)
299 self.heads[head] = delta.head
300 self.tails[delta.head] = set(heads)
302 self.remove_special.happened(item)
303 elif delta.tail in self.tails and len(self.reverse[delta.tail]) > 1:
304 heads = [x for x in self.tails[delta.tail] if self.is_child_of(delta.head, x)]
305 self.tails[delta.tail] -= set(heads)
306 if not self.tails[delta.tail]:
307 self.tails.pop(delta.tail)
309 self.heads[head] = delta.head
310 assert delta.head not in self.tails
311 self.tails[delta.head] = set(heads)
313 self.remove_special2.happened(item)
315 raise NotImplementedError()
317 self.items.pop(delta.head)
318 self.reverse[delta.tail].remove(delta.head)
319 if not self.reverse[delta.tail]:
320 self.reverse.pop(delta.tail)
322 self.removed.happened(item)
324 def get_chain(self, start_hash, length):
325 assert length <= self.get_height(start_hash)
326 for i in xrange(length):
327 yield self.items[start_hash]
328 start_hash = self._delta_type.from_element(self.items[start_hash]).tail
330 def is_child_of(self, item_hash, possible_child_hash):
331 height, last = self.get_height_and_last(item_hash)
332 child_height, child_last = self.get_height_and_last(possible_child_hash)
333 if child_last != last:
334 return None # not connected, so can't be determined
335 height_up = child_height - height
336 return height_up >= 0 and self.get_nth_parent_hash(possible_child_hash, height_up) == item_hash
338 class SubsetTracker(Tracker):
339 def __init__(self, subset_of, **kwargs):
340 Tracker.__init__(self, **kwargs)
341 self.get_nth_parent_hash = subset_of.get_nth_parent_hash # overwrites Tracker.__init__'s
342 self._subset_of = subset_of
345 delta = self._delta_type.from_element(item)
346 if self._subset_of is not None:
347 assert delta.head in self._subset_of.items
348 Tracker.add(self, item)
350 def remove(self, item_hash):
351 if self._subset_of is not None:
352 assert item_hash in self._subset_of.items
353 Tracker.remove(self, item_hash)