1package kademlia
 2
 3import (
 4	"math/bits"
 5	"strconv"
 6)
 7
 8const (
 9	alpha       = 3  // 'alpha', max parallalel calls
10	B           = 20 // 'B', 160 bits, ID length
11	KBucketSize = 20 // 'K', bucket size
12)
13
14type ListedNode struct {
15	ID   ID
16	Addr string
17}
18
19type Kademlia struct {
20	ID       ID
21	KBuckets [B * 8][]ListedNode
22}
23
24func NewKademliaTable(id ID) *Kademlia {
25	return &Kademlia{
26		ID: id,
27	}
28}
29
30func (kad Kademlia) String() string {
31	r := "Node ID: " + kad.ID.String() + ", KBuckets:\n"
32	for i, kb := range kad.KBuckets {
33		if len(kb) > 0 {
34			r += "	KBucket " + strconv.Itoa(i) + "\n"
35			for _, e := range kb {
36				r += "		" + e.ID.String() + "\n"
37			}
38		}
39	}
40	return r
41}
42
43func (kad Kademlia) KBucket(o ID) int {
44	d := kad.ID.Distance(o)
45	return kBucketByDistance(d[:])
46
47}
48
49func kBucketByDistance(b []byte) int {
50	for i := 0; i < B; i++ {
51		for a := b[i] ^ 0; a != 0; a &= a - 1 {
52			return (B-1-i)*8 + (7 - bits.TrailingZeros8(bits.Reverse8(uint8(a))))
53		}
54	}
55	return (B*8 - 1) - (B*8 - 1)
56}
57
58func (kad *Kademlia) Update(o ListedNode) {
59	k := kad.KBucket(o.ID)
60	kb := kad.KBuckets[k]
61	if len(kb) >= KBucketSize {
62		// if n.KBuckets[k] is alrady full, perform ping of the first element
63		kad.Ping(k, o)
64		return
65	}
66	// check that is not already in the list
67	exist, pos := existsInListedNodes(kad.KBuckets[k], o)
68	if exist {
69		// update position of o to the bottom
70		kad.KBuckets[k] = moveToBottom(kad.KBuckets[k], pos)
71		return
72	}
73	// not exists, add it to the kBucket
74	kad.KBuckets[k] = append(kad.KBuckets[k], o)
75	return
76}
77
78func (kad *Kademlia) Ping(k int, o ListedNode) {
79	// TODO when rpc layer is done
80	// ping the n.KBuckets[k][0] (using goroutine)
81	// if no response (timeout), delete it and add 'o'
82	// n.KBuckets[k][0] = o
83}
84
85func existsInListedNodes(lns []ListedNode, ln ListedNode) (bool, int) {
86	for i, v := range lns {
87		if v.ID.Equal(ln.ID) {
88			return true, i
89		}
90	}
91	return false, 0
92}
93
94func moveToBottom(kb []ListedNode, k int) []ListedNode {
95	e := kb[k]
96	kb = append(kb[:k], kb[k+1:]...)
97	kb = append(kb[:], e)
98	return kb
99}