Intermediate changes

1 files changed, 79 insertions, 0 deletions

diff --git a/vendor/github.com/dgryski/go-rendezvous/rdv.go b/vendor/github.com/dgryski/go-rendezvous/rdv.go
new file mode 100644
index 0000000000..7a6f8203c6
--- /dev/null
+++ b/vendor/github.com/dgryski/go-rendezvous/rdv.go
@@ -0,0 +1,79 @@
+package rendezvous
+
+type Rendezvous struct {
+	nodes map[string]int
+	nstr  []string
+	nhash []uint64
+	hash  Hasher
+}
+
+type Hasher func(s string) uint64
+
+func New(nodes []string, hash Hasher) *Rendezvous {
+	r := &Rendezvous{
+		nodes: make(map[string]int, len(nodes)),
+		nstr:  make([]string, len(nodes)),
+		nhash: make([]uint64, len(nodes)),
+		hash:  hash,
+	}
+
+	for i, n := range nodes {
+		r.nodes[n] = i
+		r.nstr[i] = n
+		r.nhash[i] = hash(n)
+	}
+
+	return r
+}
+
+func (r *Rendezvous) Lookup(k string) string {
+	// short-circuit if we're empty
+	if len(r.nodes) == 0 {
+		return ""
+	}
+
+	khash := r.hash(k)
+
+	var midx int
+	var mhash = xorshiftMult64(khash ^ r.nhash[0])
+
+	for i, nhash := range r.nhash[1:] {
+		if h := xorshiftMult64(khash ^ nhash); h > mhash {
+			midx = i + 1
+			mhash = h
+		}
+	}
+
+	return r.nstr[midx]
+}
+
+func (r *Rendezvous) Add(node string) {
+	r.nodes[node] = len(r.nstr)
+	r.nstr = append(r.nstr, node)
+	r.nhash = append(r.nhash, r.hash(node))
+}
+
+func (r *Rendezvous) Remove(node string) {
+	// find index of node to remove
+	nidx := r.nodes[node]
+
+	// remove from the slices
+	l := len(r.nstr)
+	r.nstr[nidx] = r.nstr[l]
+	r.nstr = r.nstr[:l]
+
+	r.nhash[nidx] = r.nhash[l]
+	r.nhash = r.nhash[:l]
+
+	// update the map
+	delete(r.nodes, node)
+	moved := r.nstr[nidx]
+	r.nodes[moved] = nidx
+}
+
+func xorshiftMult64(x uint64) uint64 {
+	x ^= x >> 12 // a
+	x ^= x << 25 // b
+	x ^= x >> 27 // c
+	return x * 2685821657736338717
+}