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 ContainsOrAdd 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 PeekOrAdd doesn't update recent-ness 205func TestLRUPeekOrAdd(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 previous, contains, evict := l.PeekOrAdd(1, 1) 214 if !contains { 215 t.Errorf("1 should be contained") 216 } 217 if evict { 218 t.Errorf("nothing should be evicted here") 219 } 220 if previous != 1 { 221 t.Errorf("previous is not equal to 1") 222 } 223 224 l.Add(3, 3) 225 contains, evict = l.ContainsOrAdd(1, 1) 226 if contains { 227 t.Errorf("1 should not have been contained") 228 } 229 if !evict { 230 t.Errorf("an eviction should have occurred") 231 } 232 if !l.Contains(1) { 233 t.Errorf("now 1 should be contained") 234 } 235} 236 237// test that Peek doesn't update recent-ness 238func TestLRUPeek(t *testing.T) { 239 l, err := New(2) 240 if err != nil { 241 t.Fatalf("err: %v", err) 242 } 243 244 l.Add(1, 1) 245 l.Add(2, 2) 246 if v, ok := l.Peek(1); !ok || v != 1 { 247 t.Errorf("1 should be set to 1: %v, %v", v, ok) 248 } 249 250 l.Add(3, 3) 251 if l.Contains(1) { 252 t.Errorf("should not have updated recent-ness of 1") 253 } 254} 255 256// test that Resize can upsize and downsize 257func TestLRUResize(t *testing.T) { 258 onEvictCounter := 0 259 onEvicted := func(k interface{}, v interface{}) { 260 onEvictCounter++ 261 } 262 l, err := NewWithEvict(2, onEvicted) 263 if err != nil { 264 t.Fatalf("err: %v", err) 265 } 266 267 // Downsize 268 l.Add(1, 1) 269 l.Add(2, 2) 270 evicted := l.Resize(1) 271 if evicted != 1 { 272 t.Errorf("1 element should have been evicted: %v", evicted) 273 } 274 if onEvictCounter != 1 { 275 t.Errorf("onEvicted should have been called 1 time: %v", onEvictCounter) 276 } 277 278 l.Add(3, 3) 279 if l.Contains(1) { 280 t.Errorf("Element 1 should have been evicted") 281 } 282 283 // Upsize 284 evicted = l.Resize(2) 285 if evicted != 0 { 286 t.Errorf("0 elements should have been evicted: %v", evicted) 287 } 288 289 l.Add(4, 4) 290 if !l.Contains(3) || !l.Contains(4) { 291 t.Errorf("Cache should have contained 2 elements") 292 } 293} 294