diff options
author | Christopher Speller <crspeller@gmail.com> | 2016-09-23 10:17:51 -0400 |
---|---|---|
committer | GitHub <noreply@github.com> | 2016-09-23 10:17:51 -0400 |
commit | 2ca0e8f9a0f9863555a26e984cde15efff9ef8f8 (patch) | |
tree | daae1ee67b14a3d0a84424f2a304885d9e75ce2b /vendor/github.com/golang/groupcache/consistenthash | |
parent | 6d62d65b2dc85855aabea036cbd44f6059e19d13 (diff) | |
download | chat-2ca0e8f9a0f9863555a26e984cde15efff9ef8f8.tar.gz chat-2ca0e8f9a0f9863555a26e984cde15efff9ef8f8.tar.bz2 chat-2ca0e8f9a0f9863555a26e984cde15efff9ef8f8.zip |
Updating golang dependancies (#4075)
Diffstat (limited to 'vendor/github.com/golang/groupcache/consistenthash')
-rw-r--r-- | vendor/github.com/golang/groupcache/consistenthash/consistenthash.go | 81 | ||||
-rw-r--r-- | vendor/github.com/golang/groupcache/consistenthash/consistenthash_test.go | 110 |
2 files changed, 0 insertions, 191 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]] -} diff --git a/vendor/github.com/golang/groupcache/consistenthash/consistenthash_test.go b/vendor/github.com/golang/groupcache/consistenthash/consistenthash_test.go deleted file mode 100644 index 1a37fd7ff..000000000 --- a/vendor/github.com/golang/groupcache/consistenthash/consistenthash_test.go +++ /dev/null @@ -1,110 +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 - -import ( - "fmt" - "strconv" - "testing" -) - -func TestHashing(t *testing.T) { - - // Override the hash function to return easier to reason about values. Assumes - // the keys can be converted to an integer. - hash := New(3, func(key []byte) uint32 { - i, err := strconv.Atoi(string(key)) - if err != nil { - panic(err) - } - return uint32(i) - }) - - // Given the above hash function, this will give replicas with "hashes": - // 2, 4, 6, 12, 14, 16, 22, 24, 26 - hash.Add("6", "4", "2") - - testCases := map[string]string{ - "2": "2", - "11": "2", - "23": "4", - "27": "2", - } - - for k, v := range testCases { - if hash.Get(k) != v { - t.Errorf("Asking for %s, should have yielded %s", k, v) - } - } - - // Adds 8, 18, 28 - hash.Add("8") - - // 27 should now map to 8. - testCases["27"] = "8" - - for k, v := range testCases { - if hash.Get(k) != v { - t.Errorf("Asking for %s, should have yielded %s", k, v) - } - } - -} - -func TestConsistency(t *testing.T) { - hash1 := New(1, nil) - hash2 := New(1, nil) - - hash1.Add("Bill", "Bob", "Bonny") - hash2.Add("Bob", "Bonny", "Bill") - - if hash1.Get("Ben") != hash2.Get("Ben") { - t.Errorf("Fetching 'Ben' from both hashes should be the same") - } - - hash2.Add("Becky", "Ben", "Bobby") - - if hash1.Get("Ben") != hash2.Get("Ben") || - hash1.Get("Bob") != hash2.Get("Bob") || - hash1.Get("Bonny") != hash2.Get("Bonny") { - t.Errorf("Direct matches should always return the same entry") - } - -} - -func BenchmarkGet8(b *testing.B) { benchmarkGet(b, 8) } -func BenchmarkGet32(b *testing.B) { benchmarkGet(b, 32) } -func BenchmarkGet128(b *testing.B) { benchmarkGet(b, 128) } -func BenchmarkGet512(b *testing.B) { benchmarkGet(b, 512) } - -func benchmarkGet(b *testing.B, shards int) { - - hash := New(50, nil) - - var buckets []string - for i := 0; i < shards; i++ { - buckets = append(buckets, fmt.Sprintf("shard-%d", i)) - } - - hash.Add(buckets...) - - b.ResetTimer() - - for i := 0; i < b.N; i++ { - hash.Get(buckets[i&(shards-1)]) - } -} |