blob: 7a6f8203c67810356a413b9f56abf30a0429de59 [file] [log] [blame]
Joey Armstrong903c69d2024-02-01 19:46:39 -05001package rendezvous
2
3type Rendezvous struct {
4 nodes map[string]int
5 nstr []string
6 nhash []uint64
7 hash Hasher
8}
9
10type Hasher func(s string) uint64
11
12func New(nodes []string, hash Hasher) *Rendezvous {
13 r := &Rendezvous{
14 nodes: make(map[string]int, len(nodes)),
15 nstr: make([]string, len(nodes)),
16 nhash: make([]uint64, len(nodes)),
17 hash: hash,
18 }
19
20 for i, n := range nodes {
21 r.nodes[n] = i
22 r.nstr[i] = n
23 r.nhash[i] = hash(n)
24 }
25
26 return r
27}
28
29func (r *Rendezvous) Lookup(k string) string {
30 // short-circuit if we're empty
31 if len(r.nodes) == 0 {
32 return ""
33 }
34
35 khash := r.hash(k)
36
37 var midx int
38 var mhash = xorshiftMult64(khash ^ r.nhash[0])
39
40 for i, nhash := range r.nhash[1:] {
41 if h := xorshiftMult64(khash ^ nhash); h > mhash {
42 midx = i + 1
43 mhash = h
44 }
45 }
46
47 return r.nstr[midx]
48}
49
50func (r *Rendezvous) Add(node string) {
51 r.nodes[node] = len(r.nstr)
52 r.nstr = append(r.nstr, node)
53 r.nhash = append(r.nhash, r.hash(node))
54}
55
56func (r *Rendezvous) Remove(node string) {
57 // find index of node to remove
58 nidx := r.nodes[node]
59
60 // remove from the slices
61 l := len(r.nstr)
62 r.nstr[nidx] = r.nstr[l]
63 r.nstr = r.nstr[:l]
64
65 r.nhash[nidx] = r.nhash[l]
66 r.nhash = r.nhash[:l]
67
68 // update the map
69 delete(r.nodes, node)
70 moved := r.nstr[nidx]
71 r.nodes[moved] = nidx
72}
73
74func xorshiftMult64(x uint64) uint64 {
75 x ^= x >> 12 // a
76 x ^= x << 25 // b
77 x ^= x >> 27 // c
78 return x * 2685821657736338717
79}