3 files changed, 118 insertions, 0 deletions
diff --git a/dependencies/pkg/mod/github.com/dgryski/go-rendezvous@v0.0.0-20200823014737-9f7001d12a5f/LICENSE b/dependencies/pkg/mod/github.com/dgryski/go-rendezvous@v0.0.0-20200823014737-9f7001d12a5f/LICENSE
new file mode 100644
index 0000000..22080f7
--- /dev/null
+++ b/dependencies/pkg/mod/github.com/dgryski/go-rendezvous@v0.0.0-20200823014737-9f7001d12a5f/LICENSE
@@ -0,0 +1,21 @@
+The MIT License (MIT)
+
+Copyright (c) 2017-2020 Damian Gryski <damian@gryski.com>
+
+Permission is hereby granted, free of charge, to any person obtaining a copy
+of this software and associated documentation files (the "Software"), to deal
+in the Software without restriction, including without limitation the rights
+to use, copy, modify, merge, publish, distribute, sublicense, and/or sell
+copies of the Software, and to permit persons to whom the Software is
+furnished to do so, subject to the following conditions:
+
+The above copyright notice and this permission notice shall be included in
+all copies or substantial portions of the Software.
+
+THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS OR
+IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY,
+FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT. IN NO EVENT SHALL THE
+AUTHORS OR COPYRIGHT HOLDERS BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER
+LIABILITY, WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING FROM,
+OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN
+THE SOFTWARE.
diff --git a/dependencies/pkg/mod/github.com/dgryski/go-rendezvous@v0.0.0-20200823014737-9f7001d12a5f/rdv.go b/dependencies/pkg/mod/github.com/dgryski/go-rendezvous@v0.0.0-20200823014737-9f7001d12a5f/rdv.go
new file mode 100644
index 0000000..7a6f820
--- /dev/null
+++ b/dependencies/pkg/mod/github.com/dgryski/go-rendezvous@v0.0.0-20200823014737-9f7001d12a5f/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
+}
diff --git a/dependencies/pkg/mod/github.com/dgryski/go-rendezvous@v0.0.0-20200823014737-9f7001d12a5f/rdv_test.go b/dependencies/pkg/mod/github.com/dgryski/go-rendezvous@v0.0.0-20200823014737-9f7001d12a5f/rdv_test.go
new file mode 100644
index 0000000..f9c5583
--- /dev/null
+++ b/dependencies/pkg/mod/github.com/dgryski/go-rendezvous@v0.0.0-20200823014737-9f7001d12a5f/rdv_test.go
@@ -0,0 +1,18 @@
+package rendezvous
+
+import (
+	"hash/fnv"
+	"testing"
+)
+
+func hashString(s string) uint64 {
+	h := fnv.New64a()
+	h.Write([]byte(s))
+	return h.Sum64()
+}
+
+func TestEmpty(t *testing.T) {
+	r := New([]string{}, hashString)
+	r.Lookup("hello")
+
+}