p2pool/util/skiplist.py

   1 from p2pool.util import math, expiring_dict, memoize
   2
   3 class Base(object):
   4     def finalize(self, sol):
   5         return sol
   6
   7 class SkipList(Base):
   8     P = .5
   9
  10     def __init__(self):
  11         self.skips = expiring_dict.ExpiringDict(600)
  12
  13     @memoize.memoize_with_backing(expiring_dict.ExpiringDict(5))
  14     def __call__(self, start, *args, **kwargs):
  15         updates = {}
  16         pos = start
  17         sol = self.initial_solution(start, args)
  18         if self.judge(sol, args) == 0:
  19             return self.finalize(sol)
  20         while True:
  21             if pos not in self.skips:
  22                 self.skips[pos] = math.geometric(self.P), [(self.previous(pos), self.get_delta(pos))]
  23             skip_length, skip = self.skips[pos]
  24
  25             # fill previous updates
  26             for i in xrange(skip_length):
  27                 if i in updates:
  28                     that_hash, delta = updates.pop(i)
  29                     x, y = self.skips[that_hash]
  30                     assert len(y) == i
  31                     y.append((pos, delta))
  32
  33             # put desired skip nodes in updates
  34             for i in xrange(len(skip), skip_length):
  35                 updates[i] = pos, None
  36
  37             #if skip_length + 1 in updates:
  38             #    updates[skip_length + 1] = self.combine(updates[skip_length + 1], updates[skip_length])
  39
  40             for jump, delta in reversed(skip):
  41                 sol_if = self.apply_delta(sol, delta, args)
  42                 decision = self.judge(sol_if, args)
  43                 #print pos, sol, jump, delta, sol_if, decision
  44                 if decision == 0:
  45                     return self.finalize(sol_if)
  46                 elif decision < 0:
  47                     sol = sol_if
  48                     break
  49             else:
  50                 raise AssertionError()
  51
  52             sol = sol_if
  53             pos = jump
  54
  55             # XXX could be better by combining updates
  56             for x in updates:
  57                 updates[x] = updates[x][0], self.combine_deltas(updates[x][1], delta) if updates[x][1] is not None else delta
  58
  59
  60         return item_hash
  61
  62 class NotSkipList(Base):
  63     def __call__(self, start, *args):
  64         pos = start
  65         sol = self.initial_solution(start, args)
  66         while True:
  67             decision = self.judge(sol, args)
  68             if decision > 0:
  69                 raise AssertionError()
  70             elif decision == 0:
  71                 return self.finalize(sol)
  72
  73             delta = self.get_delta(pos)
  74             sol = self.apply_delta(sol, delta, args)
  75
  76             pos = self.previous(pos)