p2pool/util/skiplist.py

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