From b09c6d56832eb1718c07d74abf3bc6ae3fe4e030 Mon Sep 17 00:00:00 2001 From: Daniel Baumann Date: Sun, 28 Apr 2024 14:36:04 +0200 Subject: Adding upstream version 1.1.0. Signed-off-by: Daniel Baumann --- .../LICENSE | 21 ++++++ .../rdv.go | 79 ++++++++++++++++++++++ .../rdv_test.go | 18 +++++ 3 files changed, 118 insertions(+) create mode 100644 dependencies/pkg/mod/github.com/dgryski/go-rendezvous@v0.0.0-20200823014737-9f7001d12a5f/LICENSE create mode 100644 dependencies/pkg/mod/github.com/dgryski/go-rendezvous@v0.0.0-20200823014737-9f7001d12a5f/rdv.go create mode 100644 dependencies/pkg/mod/github.com/dgryski/go-rendezvous@v0.0.0-20200823014737-9f7001d12a5f/rdv_test.go (limited to 'dependencies/pkg/mod/github.com/dgryski') 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 + +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") + +} -- cgit v1.2.3