1
package chord
2
 
3
import (
4
	"math/rand"
5
 
6
	"github.com/zeebo/xxh3"
7
)
8
 
9
const (
10
	MaxFingerEntries         int    = 48 // Also known as m in the original paper
11
	ExtendedSuccessorEntries int    = 4  // Also known as L in the second paper
12
	MaxIdentitifer           uint64 = 1 << MaxFingerEntries
13
)
14
 
15
func Hash(b []byte) uint64 {
16
	return xxh3.Hash(b) % MaxIdentitifer
17
}
18
 
19
func ModuloSum(x, y uint64) uint64 {
20
	// split (x + y) % m into (x % m + y % m) % m to avoid overflow
21
	return (x%MaxIdentitifer + y%MaxIdentitifer) % MaxIdentitifer
22
}
23
 
24
func Random() uint64 {
25
	return rand.Uint64() % MaxIdentitifer
26
}
27
 
28
func Between(low, target, high uint64, inclusive bool) bool {
29
	// account for loop around
30
	if high > low {
31
		return (low < target && target < high) || (inclusive && target == high)
32
	} else {
33
		return low < target || target < high || (inclusive && target == high)
34
	}
35
}
36
 
37
// make successor list that will not have duplicate VNodes
38
func MakeSuccListByID(immediate VNode, successors []VNode, maxLen int) []VNode {
39
	succList := []VNode{immediate}
40
	seen := make(map[uint64]bool)
41
	seen[immediate.ID()] = true
42
 
43
	for _, succ := range successors {
44
		if len(succList) >= maxLen {
45
			break
46
		}
47
		if succ == nil || seen[succ.ID()] {
48
			continue
49
		}
50
		seen[succ.ID()] = true
51
		succList = append(succList, succ)
52
	}
53
	return succList
54
}
55
 
56
// make successor list that will not have duplicate VNodes
57
func MakeSuccListByAddress(immediate VNode, successors []VNode, maxLen int) []VNode {
58
	succList := []VNode{immediate}
59
	seen := make(map[string]bool)
60
	seen[immediate.Identity().GetAddress()] = true
61
 
62
	for _, succ := range successors {
63
		if len(succList) >= maxLen {
64
			break
65
		}
66
		if succ == nil || seen[succ.Identity().GetAddress()] {
67
			continue
68
		}
69
		seen[succ.Identity().GetAddress()] = true
70
		succList = append(succList, succ)
71
	}
72
	return succList
73
}