1 ## Copyright 2002 Andrew Loewenstern, All Rights Reserved
10 # The all-powerful, magical Kademlia "k" constant, bucket depth
13 # how many bits wide is our hash?
17 # the local routing table for a kademlia like distributed hash table
19 def __init__(self, node):
20 # this is the root node, a.k.a. US!
22 self.buckets = [KBucket([], 0L, 2L**HASH_LENGTH)]
25 def _bucketIndexForInt(self, int):
26 """returns the index of the bucket that should hold int"""
27 return bisect_left(self.buckets, int)
29 def findNodes(self, id):
30 """ return k nodes in our own local table closest to the ID
31 ignoreSelf means we will return K closest nodes to ourself if we search for our own ID
32 note, K closest nodes may actually include ourself, it's the callers responsibilty to
33 not send messages to itself if it matters
35 if type(id) == StringType:
37 elif type(id) == InstanceType:
39 elif type(id) == IntType or type(id) == LongType:
42 raise TypeError, "findLocalNodes requires an int, string, or Node instance type"
46 def sort(a, b, int=int):
47 """ this function is for sorting nodes relative to the ID we are looking for """
48 x, y = int ^ a.int, int ^ b.int
55 i = self._bucketIndexForInt(int)
57 ## see if this node is already in our table and return it
59 index = self.buckets[i].l.index(int)
63 self.buckets[i].touch()
64 return [self.buckets[i].l[index]]
66 nodes = nodes + self.buckets[i].l
74 while (len(nodes) < K and (min >= 0 and max < len(self.buckets))):
76 nodes = nodes + self.buckets[min].l
77 self.buckets[min].touch()
78 if max < len(self.buckets):
79 nodes = nodes + self.buckets[max].l
80 self.buckets[max].touch()
85 def _splitBucket(self, a):
86 diff = (a.max - a.min) / 2
87 b = KBucket([], a.max - diff, a.max)
88 self.buckets.insert(self.buckets.index(a.min) + 1, b)
90 # transfer nodes to new bucket
92 if anode.int >= a.max:
96 def replaceStaleNode(self, stale, new):
97 """ this is used by clients to replace a node returned by insertNode after
98 it fails to respond to a Pong message
100 i = self._bucketIndexForInt(stale.int)
102 it = self.buckets[i].l.index(stale.int)
106 del(self.buckets[i].l[it])
107 self.buckets[i].l.append(new)
109 def insertNode(self, node):
111 this insert the node, returning None if successful, returns the oldest node in the bucket if it's full
112 the caller responsible for pinging the returned node and calling replaceStaleNode if it is found to be stale!!
114 assert(node.id != " "*20)
115 # get the bucket for this node
116 i = self. _bucketIndexForInt(node.int)
117 ## check to see if node is in the bucket already
119 it = self.buckets[i].l.index(node.int)
124 node.updateLastSeen()
125 # move node to end of bucket
126 del(self.buckets[i].l[it])
127 self.buckets[i].l.append(node)
128 self.buckets[i].touch()
131 # we don't have this node, check to see if the bucket is full
132 if len(self.buckets[i].l) < K:
133 # no, append this node and return
134 self.buckets[i].l.append(node)
135 self.buckets[i].touch()
138 # bucket is full, check to see if self.node is in the bucket
140 me = self.buckets[i].l.index(self.node)
142 return self.buckets[i].l[0]
144 ## this bucket is full and contains our node, split the bucket
145 if len(self.buckets) >= HASH_LENGTH:
147 print "Hash Table is FULL! Increase K!"
150 self._splitBucket(self.buckets[i])
152 ## now that the bucket is split and balanced, try to insert the node again
153 return self.insertNode(node)
155 def justSeenNode(self, node):
156 """ call this any time you get a message from a node, to update it in the table if it's there """
158 n = self.findNodes(node.int)[0]
168 __slots = ['min', 'max', 'lastAccessed']
169 def __init__(self, contents, min, max):
173 self.lastAccessed = time.time()
176 self.lastAccessed = time.time()
178 def getNodeWithInt(self, int):
180 return self.l[self.l.index(int)]
186 return "<KBucket items: %d min: %d\tmax: %d>" % (len(self.l), self.min, self.max)
188 ## comparators, necessary for bisecting list of buckets with a hash expressed as an integer or a distance
189 ## compares integer or node object with the bucket's range
191 if type(a) == InstanceType:
195 if type(a) == InstanceType:
199 if type(a) == InstanceType:
203 if type(a) == InstanceType:
207 if type(a) == InstanceType:
209 return self.min <= a and self.max > a
211 if type(a) == InstanceType:
213 return self.min >= a or self.max < a
220 class TestKTable(unittest.TestCase):
222 self.a = Node(hash.newID(), 'localhost', 2002)
223 self.t = KTable(self.a)
225 def test_replace_stale_node(self):
226 self.b = Node(hash.newID(), 'localhost', 2003)
227 self.t.replaceStaleNode(self.a, self.b)
228 assert(len(self.t.buckets[0].l) == 1)
229 assert(self.t.buckets[0].l[0].id == self.b.id)
231 if __name__ == "__main__":