diff options
Diffstat (limited to 'vendor/github.com/golang/groupcache/consistenthash/consistenthash.go')
-rw-r--r-- | vendor/github.com/golang/groupcache/consistenthash/consistenthash.go | 81 |
1 files changed, 0 insertions, 81 deletions
diff --git a/vendor/github.com/golang/groupcache/consistenthash/consistenthash.go b/vendor/github.com/golang/groupcache/consistenthash/consistenthash.go deleted file mode 100644 index a9c56f076..000000000 --- a/vendor/github.com/golang/groupcache/consistenthash/consistenthash.go +++ /dev/null @@ -1,81 +0,0 @@ -/* -Copyright 2013 Google Inc. - -Licensed under the Apache License, Version 2.0 (the "License"); -you may not use this file except in compliance with the License. -You may obtain a copy of the License at - - http://www.apache.org/licenses/LICENSE-2.0 - -Unless required by applicable law or agreed to in writing, software -distributed under the License is distributed on an "AS IS" BASIS, -WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. -See the License for the specific language governing permissions and -limitations under the License. -*/ - -// Package consistenthash provides an implementation of a ring hash. -package consistenthash - -import ( - "hash/crc32" - "sort" - "strconv" -) - -type Hash func(data []byte) uint32 - -type Map struct { - hash Hash - replicas int - keys []int // Sorted - hashMap map[int]string -} - -func New(replicas int, fn Hash) *Map { - m := &Map{ - replicas: replicas, - hash: fn, - hashMap: make(map[int]string), - } - if m.hash == nil { - m.hash = crc32.ChecksumIEEE - } - return m -} - -// Returns true if there are no items available. -func (m *Map) IsEmpty() bool { - return len(m.keys) == 0 -} - -// Adds some keys to the hash. -func (m *Map) Add(keys ...string) { - for _, key := range keys { - for i := 0; i < m.replicas; i++ { - hash := int(m.hash([]byte(strconv.Itoa(i) + key))) - m.keys = append(m.keys, hash) - m.hashMap[hash] = key - } - } - sort.Ints(m.keys) -} - -// Gets the closest item in the hash to the provided key. -func (m *Map) Get(key string) string { - if m.IsEmpty() { - return "" - } - - hash := int(m.hash([]byte(key))) - - // Binary search for appropriate replica. - idx := sort.Search(len(m.keys), func(i int) bool { return m.keys[i] >= hash }) - - // Means we have cycled back to the first replica. - if idx == len(m.keys) { - idx = 0 - } - - return m.hashMap[m.keys[idx]] -} |