p2pool/util/skiplist.py

   1 class SkipList(object):
   2     def query(self, start, *args, **kwargs):
   3         updates = {}
   4         pos = start
   5         while True:
   6             if pos not in self.skips:
   7                 self.skips[pos] = math.geometric(.5), [self.base(pos)]
   8             skip_length, skip = self.skips[pos]
   9
  10             for i in xrange(skip_length):
  11                 if i in updates:
  12                     n_then, that_hash = updates.pop(i)
  13                     x, y = self.skips[that_hash]
  14                     assert len(y) == i
  15                     y.append((n_then - n, pos))
  16
  17             for i in xrange(len(skip), skip_length):
  18                 updates[i] = n, item_hash
  19
  20             if skip_length + 1 in updates:
  21                 updates[skip_length + 1] = self.combine(updates[skip_length + 1], updates[skip_length])
  22
  23             for delta, jump in reversed(skip):
  24                 sol_if = self.combine(sol, delta)
  25                 decision = self.judge(sol_if)
  26                 if decision == 0:
  27                     return sol_if
  28                 elif decision < 0:
  29                     break
  30             else:
  31                 raise AssertionError()
  32
  33         return item_hash
  34
  35 class DistanceSkipList(SkipList):
  36     def combine(self, a, b):
  37         return a + b
  38
  39     def base(self, element):
  40         return 1, self.tracker.shares[element].previous_hash
  41
  42 class WeightsList(SkipList):
  43     # share_count, weights, total_weight
  44     def combine(self, (ac, a, at), (bc, b, bt)):
  45         return ac + bc, dict((k, a.get(k, 0) + b.get(k, 0)) for k in set(a.keys() + b.keys())), at + bt
  46
  47     def base(self, element):
  48         share = self.tracker.shares[element]
  49         att = target_to_average_attempts(share.target2)
  50         return (1, {share.new_script: att}, att), self.tracker.shares[element].previous_hash
  51
  52     def judge(self, (share_count, weights, total_weight), max_shares, desired_weight):
  53         if share_count > max_shares:
  54             return 1