1package main
  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 Node struct {
 20	ID       ID
 21	KBuckets [B * 8][]ListedNode
 22}
 23
 24func (n Node) String() string {
 25	r := "Node ID: " + n.ID.String() + ", KBuckets:\n"
 26	for i, kb := range n.KBuckets {
 27		if len(kb) > 0 {
 28			r += "	KBucket " + strconv.Itoa(i) + "\n"
 29			for _, e := range kb {
 30				r += "		" + e.ID.String() + "\n"
 31			}
 32		}
 33	}
 34	return r
 35}
 36
 37func NewNode() (Node, error) {
 38	// TODO if node already has id, import it
 39	id, err := NewID()
 40	if err != nil {
 41		return Node{}, err
 42	}
 43
 44	var n Node
 45	n.ID = id
 46	return n, nil
 47}
 48
 49func LoadNode(idStr string) (Node, error) {
 50	id, err := IDFromString("0fd85ddddf15aeec2d5d8b01b013dbca030a18d7")
 51	if err != nil {
 52		return Node{}, err
 53	}
 54	var n Node
 55	n.ID = id
 56	return n, nil
 57}
 58
 59func (n Node) KBucket(o ID) int {
 60	d := n.ID.Distance(o)
 61	return kBucketByDistance(d[:])
 62
 63}
 64
 65func kBucketByDistance(b []byte) int {
 66	for i := 0; i < B; i++ {
 67		for a := b[i] ^ 0; a != 0; a &= a - 1 {
 68			return (B-1-i)*8 + (7 - bits.TrailingZeros8(bits.Reverse8(uint8(a))))
 69		}
 70	}
 71	return (B*8 - 1) - (B*8 - 1)
 72}
 73
 74func (n *Node) Update(o ListedNode) {
 75	k := n.KBucket(o.ID)
 76	kb := n.KBuckets[k]
 77	if len(kb) >= KBucketSize {
 78		// if n.KBuckets[k] is alrady full, perform ping of the first element
 79		n.Ping(k, o)
 80		return
 81	}
 82	// check that is not already in the list
 83	exist, pos := existsInListedNodes(n.KBuckets[k], o)
 84	if exist {
 85		// update position of o to the bottom
 86		n.KBuckets[k] = moveToBottom(n.KBuckets[k], pos)
 87		return
 88	}
 89	// not exists, add it to the kBucket
 90	n.KBuckets[k] = append(n.KBuckets[k], o)
 91	return
 92}
 93
 94func (n *Node) Ping(k int, o ListedNode) {
 95	// TODO when rpc layer is done
 96	// ping the n.KBuckets[k][0] (using goroutine)
 97	// if no response (timeout), delete it and add 'o'
 98	// n.KBuckets[k][0] = o
 99}
100
101func existsInListedNodes(lns []ListedNode, ln ListedNode) (bool, int) {
102	for i, v := range lns {
103		if v.ID.Equal(ln.ID) {
104			return true, i
105		}
106	}
107	return false, 0
108}
109
110func moveToBottom(kb []ListedNode, k int) []ListedNode {
111	e := kb[k]
112	kb = append(kb[:k], kb[k+1:]...)
113	kb = append(kb[:], e)
114	return kb
115}