p2pool/util/skiplist.py

   1 from p2pool.util import math, expiring_dict
   2
   3 class Base(object):
   4     def finalize(self, sol):
   5         return sol
   6
   7 class SkipList(Base):
   8     def __init__(self):
   9         self.skips = expiring_dict.ExpiringDict(600)
  10
  11     def __call__(self, start, *args, **kwargs):
  12         updates = {}
  13         pos = start
  14         sol = self.initial_solution(start, args)
  15         if self.judge(sol, args) == 0:
  16             return self.finalize(sol)
  17         while True:
  18             if pos not in self.skips:
  19                 self.skips[pos] = math.geometric(.5), [(self.previous(pos), self.get_delta(pos))]
  20             skip_length, skip = self.skips[pos]
  21
  22             # fill previous updates
  23             for i in xrange(skip_length):
  24                 if i in updates:
  25                     that_hash, delta = updates.pop(i)
  26                     x, y = self.skips[that_hash]
  27                     assert len(y) == i
  28                     y.append((pos, delta))
  29
  30             # put desired skip nodes in updates
  31             for i in xrange(len(skip), skip_length):
  32                 updates[i] = pos, None
  33
  34             #if skip_length + 1 in updates:
  35             #    updates[skip_length + 1] = self.combine(updates[skip_length + 1], updates[skip_length])
  36
  37             for jump, delta in reversed(skip):
  38                 sol_if = self.apply_delta(sol, delta, args)
  39                 decision = self.judge(sol_if, args)
  40                 #print pos, sol, jump, delta, sol_if, decision
  41                 if decision == 0:
  42                     return self.finalize(sol_if)
  43                 elif decision < 0:
  44                     sol = sol_if
  45                     break
  46             else:
  47                 raise AssertionError()
  48
  49             sol = sol_if
  50             pos = jump
  51
  52             # XXX could be better by combining updates
  53             for x in updates:
  54                 updates[x] = updates[x][0], self.combine_deltas(updates[x][1], delta) if updates[x][1] is not None else delta
  55
  56
  57         return item_hash
  58
  59 class DumbSkipList(Base):
  60     def __call__(self, start, *args):
  61         pos = start
  62         sol = self.initial_solution(start, args)
  63         while True:
  64             decision = self.judge(sol, args)
  65             if decision > 0:
  66                 raise AssertionError()
  67             elif decision == 0:
  68                 return self.finalize(sol)
  69
  70             delta = self.get_delta(pos)
  71             sol = self.apply_delta(sol, delta, args)
  72
  73             pos = self.previous(pos)
  74
  75 class DistanceSkipList(SkipList):
  76     def __init__(self, tracker):
  77         SkipList.__init__(self)
  78         self.tracker = tracker
  79
  80     def previous(self, element):
  81         return self.tracker.shares[element].previous_hash
  82
  83     def get_delta(self, element):
  84         return element, 1, self.tracker.shares[element].previous_hash
  85
  86     def combine_deltas(self, (from_hash1, dist1, to_hash1), (from_hash2, dist2, to_hash2)):
  87         if to_hash1 != from_hash2:
  88             raise AssertionError()
  89         return from_hash1, dist1 + dist2, to_hash2
  90
  91     def initial_solution(self, start, (n,)):
  92         return 0, start
  93
  94     def apply_delta(self, (dist1, to_hash1), (from_hash2, dist2, to_hash2), (n,)):
  95         if to_hash1 != from_hash2:
  96             raise AssertionError()
  97         return dist1 + dist2, to_hash2
  98
  99     def judge(self, (dist, hash), (n,)):
 100         if dist > n:
 101             return 1
 102         elif dist == n:
 103             return 0
 104         else:
 105             return -1
 106
 107     def finalize(self, (dist, hash)):
 108         return hash
 109
 110 if __name__ == '__main__':
 111     import random
 112     from p2pool.bitcoin import data
 113     t = data.Tracker()
 114     d = DistanceSkipList(t)
 115     for i in xrange(2000):
 116         t.add(data.FakeShare(hash=i, previous_hash=i - 1 if i > 0 else None))
 117     for i in xrange(2000):
 118         a = random.randrange(2000)
 119         b = random.randrange(a + 1)
 120         res = d(a, b)
 121         assert res == a - b, (a, b, res)
 122
 123 class WeightsSkipList(SkipList):
 124     # share_count, weights, total_weight
 125
 126     def __init__(self, tracker):
 127         SkipList.__init__(self)
 128         self.tracker = tracker
 129
 130     def previous(self, element):
 131         return self.tracker.shares[element].previous_hash
 132
 133     def get_delta(self, element):
 134         from p2pool.bitcoin import data as bitcoin_data
 135         if element is None:
 136             return (2**256, {}, 0) # XXX
 137         share = self.tracker.shares[element]
 138         att = bitcoin_data.target_to_average_attempts(share.target)
 139         return 1, {share.new_script: att}, att
 140
 141     def combine_deltas(self, (share_count1, weights1, total_weight1), (share_count2, weights2, total_weight2)):
 142         return share_count1 + share_count2, math.add_dicts([weights1, weights2]), total_weight1 + total_weight2
 143
 144     def initial_solution(self, start, (max_shares, desired_weight)):
 145         return 0, {}, 0
 146
 147     def apply_delta(self, (share_count1, weights1, total_weight1), (share_count2, weights2, total_weight2), (max_shares, desired_weight)):
 148         if total_weight1 + total_weight2 > desired_weight and len(weights2) == 1:
 149             script, = weights2.iterkeys()
 150             new_weights = dict(weights1)
 151             new_weights[script] = new_weights.get(script, 0) + desired_weight - total_weight1
 152             return share_count1 + share_count2, new_weights, desired_weight
 153         return share_count1 + share_count2, math.add_dicts([weights1, weights2]), total_weight1 + total_weight2
 154
 155     def judge(self, (share_count, weights, total_weight), (max_shares, desired_weight)):
 156         if share_count > max_shares or total_weight > desired_weight:
 157             return 1
 158         elif share_count == max_shares or total_weight == desired_weight:
 159             return 0
 160         else:
 161             return -1
 162
 163     def finalize(self, (share_count, weights, total_weight)):
 164         return weights, total_weight
 165
 166 class CountsSkipList(SkipList):
 167     # share_count, counts, total_count
 168
 169     def __init__(self, tracker, run_identifier):
 170         SkipList.__init__(self)
 171         self.tracker = tracker
 172         self.run_identifier = run_identifier
 173
 174     def previous(self, element):
 175         return self.tracker.shares[element].previous_hash
 176
 177     def get_delta(self, element):
 178         from p2pool.bitcoin import data as bitcoin_data
 179         if element is None:
 180             return 0 # XXX
 181         share = self.tracker.shares[element]
 182         weight = 1 if share.nonce[:8] == self.run_identifier else 0
 183         return 1, weight, 1
 184
 185     def combine_deltas(self, (share_count1, weights1, total_weight1), (share_count2, weights2, total_weight2)):
 186         return share_count1 + share_count2, weights1 + weights2, total_weight1 + total_weight2
 187
 188     def initial_solution(self, start, (max_shares, desired_weight)):
 189         return 0, 0, 0
 190
 191
 192     def apply_delta(self, (share_count1, weights1, total_weight1), (share_count2, weights2, total_weight2), (max_shares, desired_weight)):
 193         return share_count1 + share_count2, weights1 + weights2, total_weight1 + total_weight2
 194
 195     def judge(self, (share_count, weights, total_weight), (max_shares, desired_weight)):
 196         if share_count > max_shares or total_weight > desired_weight:
 197             return 1
 198         elif share_count == max_shares or total_weight == desired_weight:
 199             return 0
 200         else:
 201             return -1
 202
 203     def finalize(self, (share_count, weights, total_weight)):
 204         if share_count != total_weight:
 205             raise AssertionError()
 206         return weights
 207
 208 if __name__ == '__main__':
 209     import random
 210     from p2pool.bitcoin import data
 211     t = data.Tracker()
 212     d = WeightsSkipList(t)
 213     for i in xrange(2000):
 214         t.add(data.FakeShare(hash=i, previous_hash=i - 1 if i > 0 else None, new_script=i, target=random.randrange(2**249, 2**250)))
 215     for i in xrange(2000):
 216         #a = random.randrange(2000)
 217         a = 1999
 218         print d(a, a, 1000000)[1]