1package lru 2 3import ( 4 "math/rand" 5 "testing" 6) 7 8func BenchmarkLRU_Rand(b *testing.B) { 9 l, err := New(8192) 10 if err != nil { 11 b.Fatalf("err: %v", err) 12 } 13 14 trace := make([]int64, b.N*2) 15 for i := 0; i < b.N*2; i++ { 16 trace[i] = rand.Int63() % 32768 17 } 18 19 b.ResetTimer() 20 21 var hit, miss int 22 for i := 0; i < 2*b.N; i++ { 23 if i%2 == 0 { 24 l.Add(trace[i], trace[i]) 25 } else { 26 _, ok := l.Get(trace[i]) 27 if ok { 28 hit++ 29 } else { 30 miss++ 31 } 32 } 33 } 34 b.Logf("hit: %d miss: %d ratio: %f", hit, miss, float64(hit)/float64(miss)) 35} 36 37func BenchmarkLRU_Freq(b *testing.B) { 38 l, err := New(8192) 39 if err != nil { 40 b.Fatalf("err: %v", err) 41 } 42 43 trace := make([]int64, b.N*2) 44 for i := 0; i < b.N*2; i++ { 45 if i%2 == 0 { 46 trace[i] = rand.Int63() % 16384 47 } else { 48 trace[i] = rand.Int63() % 32768 49 } 50 } 51 52 b.ResetTimer() 53 54 for i := 0; i < b.N; i++ { 55 l.Add(trace[i], trace[i]) 56 } 57 var hit, miss int 58 for i := 0; i < b.N; i++ { 59 _, ok := l.Get(trace[i]) 60 if ok { 61 hit++ 62 } else { 63 miss++ 64 } 65 } 66 b.Logf("hit: %d miss: %d ratio: %f", hit, miss, float64(hit)/float64(miss)) 67} 68 69func TestLRU(t *testing.T) { 70 evictCounter := 0 71 onEvicted := func(k interface{}, v interface{}) { 72 if k != v { 73 t.Fatalf("Evict values not equal (%v!=%v)", k, v) 74 } 75 evictCounter++ 76 } 77 l, err := NewWithEvict(128, onEvicted) 78 if err != nil { 79 t.Fatalf("err: %v", err) 80 } 81 82 for i := 0; i < 256; i++ { 83 l.Add(i, i) 84 } 85 if l.Len() != 128 { 86 t.Fatalf("bad len: %v", l.Len()) 87 } 88 89 if evictCounter != 128 { 90 t.Fatalf("bad evict count: %v", evictCounter) 91 } 92 93 for i, k := range l.Keys() { 94 if v, ok := l.Get(k); !ok || v != k || v != i+128 { 95 t.Fatalf("bad key: %v", k) 96 } 97 } 98 for i := 0; i < 128; i++ { 99 _, ok := l.Get(i) 100 if ok { 101 t.Fatalf("should be evicted") 102 } 103 } 104 for i := 128; i < 256; i++ { 105 _, ok := l.Get(i) 106 if !ok { 107 t.Fatalf("should not be evicted") 108 } 109 } 110 for i := 128; i < 192; i++ { 111 l.Remove(i) 112 _, ok := l.Get(i) 113 if ok { 114 t.Fatalf("should be deleted") 115 } 116 } 117 118 l.Get(192) // expect 192 to be last key in l.Keys() 119 120 for i, k := range l.Keys() { 121 if (i < 63 && k != i+193) || (i == 63 && k != 192) { 122 t.Fatalf("out of order key: %v", k) 123 } 124 } 125 126 l.Purge() 127 if l.Len() != 0 { 128 t.Fatalf("bad len: %v", l.Len()) 129 } 130 if _, ok := l.Get(200); ok { 131 t.Fatalf("should contain nothing") 132 } 133} 134 135// test that Add returns true/false if an eviction occurred 136func TestLRUAdd(t *testing.T) { 137 evictCounter := 0 138 onEvicted := func(k interface{}, v interface{}) { 139 evictCounter++ 140 } 141 142 l, err := NewWithEvict(1, onEvicted) 143 if err != nil { 144 t.Fatalf("err: %v", err) 145 } 146 147 if l.Add(1, 1) == true || evictCounter != 0 { 148 t.Errorf("should not have an eviction") 149 } 150 if l.Add(2, 2) == false || evictCounter != 1 { 151 t.Errorf("should have an eviction") 152 } 153} 154 155// test that Contains doesn't update recent-ness 156func TestLRUContains(t *testing.T) { 157 l, err := New(2) 158 if err != nil { 159 t.Fatalf("err: %v", err) 160 } 161 162 l.Add(1, 1) 163 l.Add(2, 2) 164 if !l.Contains(1) { 165 t.Errorf("1 should be contained") 166 } 167 168 l.Add(3, 3) 169 if l.Contains(1) { 170 t.Errorf("Contains should not have updated recent-ness of 1") 171 } 172} 173 174// test that Contains doesn't update recent-ness 175func TestLRUContainsOrAdd(t *testing.T) { 176 l, err := New(2) 177 if err != nil { 178 t.Fatalf("err: %v", err) 179 } 180 181 l.Add(1, 1) 182 l.Add(2, 2) 183 contains, evict := l.ContainsOrAdd(1, 1) 184 if !contains { 185 t.Errorf("1 should be contained") 186 } 187 if evict { 188 t.Errorf("nothing should be evicted here") 189 } 190 191 l.Add(3, 3) 192 contains, evict = l.ContainsOrAdd(1, 1) 193 if contains { 194 t.Errorf("1 should not have been contained") 195 } 196 if !evict { 197 t.Errorf("an eviction should have occurred") 198 } 199 if !l.Contains(1) { 200 t.Errorf("now 1 should be contained") 201 } 202} 203 204// test that Peek doesn't update recent-ness 205func TestLRUPeek(t *testing.T) { 206 l, err := New(2) 207 if err != nil { 208 t.Fatalf("err: %v", err) 209 } 210 211 l.Add(1, 1) 212 l.Add(2, 2) 213 if v, ok := l.Peek(1); !ok || v != 1 { 214 t.Errorf("1 should be set to 1: %v, %v", v, ok) 215 } 216 217 l.Add(3, 3) 218 if l.Contains(1) { 219 t.Errorf("should not have updated recent-ness of 1") 220 } 221} 222