## Copyright 2002-2003 Andrew Loewenstern, All Rights Reserved
# see LICENSE.txt for license information
-from time import time
+from datetime import datetime
from bisect import bisect_left
+from twisted.python import log
+from twisted.trial import unittest
+
import khash
from node import Node, NULL_ID
"""local routing table for a kademlia like distributed hash table"""
def __init__(self, node, config):
# this is the root node, a.k.a. US!
+ assert node.id != NULL_ID
self.node = node
self.config = config
self.buckets = [KBucket([], 0L, 2L**self.config['HASH_LENGTH'])]
- self.insertNode(node)
def _bucketIndexForInt(self, num):
"""the index of the bucket that should hold int"""
# don't have the node, get the K closest nodes
nodes = nodes + self.buckets[i].l
- if len(nodes) < K:
+ if len(nodes) < self.config['K']:
# need more nodes
min = i - 1
max = i + 1
- while len(nodes) < K and (min >= 0 or max < len(self.buckets)):
+ while len(nodes) < self.config['K'] and (min >= 0 or max < len(self.buckets)):
#ASw: note that this requires K be even
if min >= 0:
nodes = nodes + self.buckets[min].l
max = max + 1
nodes.sort(lambda a, b, num=num: cmp(num ^ a.num, num ^ b.num))
- return nodes[:K]
+ return nodes[:self.config['K']]
def _splitBucket(self, a):
diff = (a.max - a.min) / 2
# this bucket is full and contains our node, split the bucket
if len(self.buckets) >= self.config['HASH_LENGTH']:
# our table is FULL, this is really unlikely
- print "Hash Table is FULL! Increase K!"
+ log.err("Hash Table is FULL! Increase K!")
return
self._splitBucket(self.buckets[i])
self.l = contents
self.min = min
self.max = max
- self.lastAccessed = time()
+ self.lastAccessed = datetime.now()
def touch(self):
- self.lastAccessed = time()
+ self.lastAccessed = datetime.now()
def getNodeWithInt(self, num):
if num in self.l: return num
if isinstance(a, Node): a = a.num
return self.min >= a or self.max < a
-
-### UNIT TESTS ###
-import unittest
-
class TestKTable(unittest.TestCase):
def setUp(self):
- self.a = Node().init(khash.newID(), 'localhost', 2002)
- self.t = KTable(self.a)
+ self.a = Node(khash.newID(), 'localhost', 2002)
+ self.t = KTable(self.a, {'HASH_LENGTH': 160, 'K': 8, 'MAX_FAILURES': 3})
def testAddNode(self):
- self.b = Node().init(khash.newID(), 'localhost', 2003)
+ self.b = Node(khash.newID(), 'localhost', 2003)
self.t.insertNode(self.b)
- self.assertEqual(len(self.t.buckets[0].l), 1)
- self.assertEqual(self.t.buckets[0].l[0], self.b)
+ self.failUnlessEqual(len(self.t.buckets[0].l), 1)
+ self.failUnlessEqual(self.t.buckets[0].l[0], self.b)
def testRemove(self):
self.testAddNode()
self.t.invalidateNode(self.b)
- self.assertEqual(len(self.t.buckets[0].l), 0)
+ self.failUnlessEqual(len(self.t.buckets[0].l), 0)
def testFail(self):
self.testAddNode()
- for i in range(const.MAX_FAILURES - 1):
+ for i in range(self.t.config['MAX_FAILURES'] - 1):
self.t.nodeFailed(self.b)
- self.assertEqual(len(self.t.buckets[0].l), 1)
- self.assertEqual(self.t.buckets[0].l[0], self.b)
+ self.failUnlessEqual(len(self.t.buckets[0].l), 1)
+ self.failUnlessEqual(self.t.buckets[0].l[0], self.b)
self.t.nodeFailed(self.b)
- self.assertEqual(len(self.t.buckets[0].l), 0)
-
-
-if __name__ == "__main__":
- unittest.main()
+ self.failUnlessEqual(len(self.t.buckets[0].l), 0)