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