From 473acc61c8392dc7ae303d91568e179c4f105a76 Mon Sep 17 00:00:00 2001 From: Dimitri Sokolyuk Date: Tue, 2 Jul 2019 12:12:53 +0200 Subject: add black list --- vendor/github.com/hashicorp/golang-lru/arc_test.go | 377 --------------------- 1 file changed, 377 deletions(-) delete mode 100644 vendor/github.com/hashicorp/golang-lru/arc_test.go (limited to 'vendor/github.com/hashicorp/golang-lru/arc_test.go') diff --git a/vendor/github.com/hashicorp/golang-lru/arc_test.go b/vendor/github.com/hashicorp/golang-lru/arc_test.go deleted file mode 100644 index e2d9b68..0000000 --- a/vendor/github.com/hashicorp/golang-lru/arc_test.go +++ /dev/null @@ -1,377 +0,0 @@ -package lru - -import ( - "math/rand" - "testing" - "time" -) - -func init() { - rand.Seed(time.Now().Unix()) -} - -func BenchmarkARC_Rand(b *testing.B) { - l, err := NewARC(8192) - if err != nil { - b.Fatalf("err: %v", err) - } - - trace := make([]int64, b.N*2) - for i := 0; i < b.N*2; i++ { - trace[i] = rand.Int63() % 32768 - } - - b.ResetTimer() - - var hit, miss int - for i := 0; i < 2*b.N; i++ { - if i%2 == 0 { - l.Add(trace[i], trace[i]) - } else { - _, ok := l.Get(trace[i]) - if ok { - hit++ - } else { - miss++ - } - } - } - b.Logf("hit: %d miss: %d ratio: %f", hit, miss, float64(hit)/float64(miss)) -} - -func BenchmarkARC_Freq(b *testing.B) { - l, err := NewARC(8192) - if err != nil { - b.Fatalf("err: %v", err) - } - - trace := make([]int64, b.N*2) - for i := 0; i < b.N*2; i++ { - if i%2 == 0 { - trace[i] = rand.Int63() % 16384 - } else { - trace[i] = rand.Int63() % 32768 - } - } - - b.ResetTimer() - - for i := 0; i < b.N; i++ { - l.Add(trace[i], trace[i]) - } - var hit, miss int - for i := 0; i < b.N; i++ { - _, ok := l.Get(trace[i]) - if ok { - hit++ - } else { - miss++ - } - } - b.Logf("hit: %d miss: %d ratio: %f", hit, miss, float64(hit)/float64(miss)) -} - -func TestARC_RandomOps(t *testing.T) { - size := 128 - l, err := NewARC(128) - if err != nil { - t.Fatalf("err: %v", err) - } - - n := 200000 - for i := 0; i < n; i++ { - key := rand.Int63() % 512 - r := rand.Int63() - switch r % 3 { - case 0: - l.Add(key, key) - case 1: - l.Get(key) - case 2: - l.Remove(key) - } - - if l.t1.Len()+l.t2.Len() > size { - t.Fatalf("bad: t1: %d t2: %d b1: %d b2: %d p: %d", - l.t1.Len(), l.t2.Len(), l.b1.Len(), l.b2.Len(), l.p) - } - if l.b1.Len()+l.b2.Len() > size { - t.Fatalf("bad: t1: %d t2: %d b1: %d b2: %d p: %d", - l.t1.Len(), l.t2.Len(), l.b1.Len(), l.b2.Len(), l.p) - } - } -} - -func TestARC_Get_RecentToFrequent(t *testing.T) { - l, err := NewARC(128) - if err != nil { - t.Fatalf("err: %v", err) - } - - // Touch all the entries, should be in t1 - for i := 0; i < 128; i++ { - l.Add(i, i) - } - if n := l.t1.Len(); n != 128 { - t.Fatalf("bad: %d", n) - } - if n := l.t2.Len(); n != 0 { - t.Fatalf("bad: %d", n) - } - - // Get should upgrade to t2 - for i := 0; i < 128; i++ { - _, ok := l.Get(i) - if !ok { - t.Fatalf("missing: %d", i) - } - } - if n := l.t1.Len(); n != 0 { - t.Fatalf("bad: %d", n) - } - if n := l.t2.Len(); n != 128 { - t.Fatalf("bad: %d", n) - } - - // Get be from t2 - for i := 0; i < 128; i++ { - _, ok := l.Get(i) - if !ok { - t.Fatalf("missing: %d", i) - } - } - if n := l.t1.Len(); n != 0 { - t.Fatalf("bad: %d", n) - } - if n := l.t2.Len(); n != 128 { - t.Fatalf("bad: %d", n) - } -} - -func TestARC_Add_RecentToFrequent(t *testing.T) { - l, err := NewARC(128) - if err != nil { - t.Fatalf("err: %v", err) - } - - // Add initially to t1 - l.Add(1, 1) - if n := l.t1.Len(); n != 1 { - t.Fatalf("bad: %d", n) - } - if n := l.t2.Len(); n != 0 { - t.Fatalf("bad: %d", n) - } - - // Add should upgrade to t2 - l.Add(1, 1) - if n := l.t1.Len(); n != 0 { - t.Fatalf("bad: %d", n) - } - if n := l.t2.Len(); n != 1 { - t.Fatalf("bad: %d", n) - } - - // Add should remain in t2 - l.Add(1, 1) - if n := l.t1.Len(); n != 0 { - t.Fatalf("bad: %d", n) - } - if n := l.t2.Len(); n != 1 { - t.Fatalf("bad: %d", n) - } -} - -func TestARC_Adaptive(t *testing.T) { - l, err := NewARC(4) - if err != nil { - t.Fatalf("err: %v", err) - } - - // Fill t1 - for i := 0; i < 4; i++ { - l.Add(i, i) - } - if n := l.t1.Len(); n != 4 { - t.Fatalf("bad: %d", n) - } - - // Move to t2 - l.Get(0) - l.Get(1) - if n := l.t2.Len(); n != 2 { - t.Fatalf("bad: %d", n) - } - - // Evict from t1 - l.Add(4, 4) - if n := l.b1.Len(); n != 1 { - t.Fatalf("bad: %d", n) - } - - // Current state - // t1 : (MRU) [4, 3] (LRU) - // t2 : (MRU) [1, 0] (LRU) - // b1 : (MRU) [2] (LRU) - // b2 : (MRU) [] (LRU) - - // Add 2, should cause hit on b1 - l.Add(2, 2) - if n := l.b1.Len(); n != 1 { - t.Fatalf("bad: %d", n) - } - if l.p != 1 { - t.Fatalf("bad: %d", l.p) - } - if n := l.t2.Len(); n != 3 { - t.Fatalf("bad: %d", n) - } - - // Current state - // t1 : (MRU) [4] (LRU) - // t2 : (MRU) [2, 1, 0] (LRU) - // b1 : (MRU) [3] (LRU) - // b2 : (MRU) [] (LRU) - - // Add 4, should migrate to t2 - l.Add(4, 4) - if n := l.t1.Len(); n != 0 { - t.Fatalf("bad: %d", n) - } - if n := l.t2.Len(); n != 4 { - t.Fatalf("bad: %d", n) - } - - // Current state - // t1 : (MRU) [] (LRU) - // t2 : (MRU) [4, 2, 1, 0] (LRU) - // b1 : (MRU) [3] (LRU) - // b2 : (MRU) [] (LRU) - - // Add 4, should evict to b2 - l.Add(5, 5) - if n := l.t1.Len(); n != 1 { - t.Fatalf("bad: %d", n) - } - if n := l.t2.Len(); n != 3 { - t.Fatalf("bad: %d", n) - } - if n := l.b2.Len(); n != 1 { - t.Fatalf("bad: %d", n) - } - - // Current state - // t1 : (MRU) [5] (LRU) - // t2 : (MRU) [4, 2, 1] (LRU) - // b1 : (MRU) [3] (LRU) - // b2 : (MRU) [0] (LRU) - - // Add 0, should decrease p - l.Add(0, 0) - if n := l.t1.Len(); n != 0 { - t.Fatalf("bad: %d", n) - } - if n := l.t2.Len(); n != 4 { - t.Fatalf("bad: %d", n) - } - if n := l.b1.Len(); n != 2 { - t.Fatalf("bad: %d", n) - } - if n := l.b2.Len(); n != 0 { - t.Fatalf("bad: %d", n) - } - if l.p != 0 { - t.Fatalf("bad: %d", l.p) - } - - // Current state - // t1 : (MRU) [] (LRU) - // t2 : (MRU) [0, 4, 2, 1] (LRU) - // b1 : (MRU) [5, 3] (LRU) - // b2 : (MRU) [0] (LRU) -} - -func TestARC(t *testing.T) { - l, err := NewARC(128) - if err != nil { - t.Fatalf("err: %v", err) - } - - for i := 0; i < 256; i++ { - l.Add(i, i) - } - if l.Len() != 128 { - t.Fatalf("bad len: %v", l.Len()) - } - - for i, k := range l.Keys() { - if v, ok := l.Get(k); !ok || v != k || v != i+128 { - t.Fatalf("bad key: %v", k) - } - } - for i := 0; i < 128; i++ { - _, ok := l.Get(i) - if ok { - t.Fatalf("should be evicted") - } - } - for i := 128; i < 256; i++ { - _, ok := l.Get(i) - if !ok { - t.Fatalf("should not be evicted") - } - } - for i := 128; i < 192; i++ { - l.Remove(i) - _, ok := l.Get(i) - if ok { - t.Fatalf("should be deleted") - } - } - - l.Purge() - if l.Len() != 0 { - t.Fatalf("bad len: %v", l.Len()) - } - if _, ok := l.Get(200); ok { - t.Fatalf("should contain nothing") - } -} - -// Test that Contains doesn't update recent-ness -func TestARC_Contains(t *testing.T) { - l, err := NewARC(2) - if err != nil { - t.Fatalf("err: %v", err) - } - - l.Add(1, 1) - l.Add(2, 2) - if !l.Contains(1) { - t.Errorf("1 should be contained") - } - - l.Add(3, 3) - if l.Contains(1) { - t.Errorf("Contains should not have updated recent-ness of 1") - } -} - -// Test that Peek doesn't update recent-ness -func TestARC_Peek(t *testing.T) { - l, err := NewARC(2) - if err != nil { - t.Fatalf("err: %v", err) - } - - l.Add(1, 1) - l.Add(2, 2) - if v, ok := l.Peek(1); !ok || v != 1 { - t.Errorf("1 should be set to 1: %v, %v", v, ok) - } - - l.Add(3, 3) - if l.Contains(1) { - t.Errorf("should not have updated recent-ness of 1") - } -} -- cgit v1.2.3