1
2
3
4 package lru
5
6 import (
7 "reflect"
8 "testing"
9 )
10
11 func BenchmarkLRU_Rand(b *testing.B) {
12 l, err := New[int64, int64](8192)
13 if err != nil {
14 b.Fatalf("err: %v", err)
15 }
16
17 trace := make([]int64, b.N*2)
18 for i := 0; i < b.N*2; i++ {
19 trace[i] = getRand(b) % 32768
20 }
21
22 b.ResetTimer()
23
24 var hit, miss int
25 for i := 0; i < 2*b.N; i++ {
26 if i%2 == 0 {
27 l.Add(trace[i], trace[i])
28 } else {
29 if _, ok := l.Get(trace[i]); ok {
30 hit++
31 } else {
32 miss++
33 }
34 }
35 }
36 b.Logf("hit: %d miss: %d ratio: %f", hit, miss, float64(hit)/float64(hit+miss))
37 }
38
39 func BenchmarkLRU_Freq(b *testing.B) {
40 l, err := New[int64, int64](8192)
41 if err != nil {
42 b.Fatalf("err: %v", err)
43 }
44
45 trace := make([]int64, b.N*2)
46 for i := 0; i < b.N*2; i++ {
47 if i%2 == 0 {
48 trace[i] = getRand(b) % 16384
49 } else {
50 trace[i] = getRand(b) % 32768
51 }
52 }
53
54 b.ResetTimer()
55
56 for i := 0; i < b.N; i++ {
57 l.Add(trace[i], trace[i])
58 }
59 var hit, miss int
60 for i := 0; i < b.N; i++ {
61 if _, ok := l.Get(trace[i]); ok {
62 hit++
63 } else {
64 miss++
65 }
66 }
67 b.Logf("hit: %d miss: %d ratio: %f", hit, miss, float64(hit)/float64(hit+miss))
68 }
69
70 func TestLRU(t *testing.T) {
71 evictCounter := 0
72 onEvicted := func(k int, v int) {
73 if k != v {
74 t.Fatalf("Evict values not equal (%v!=%v)", k, v)
75 }
76 evictCounter++
77 }
78 l, err := NewWithEvict(128, onEvicted)
79 if err != nil {
80 t.Fatalf("err: %v", err)
81 }
82
83 for i := 0; i < 256; i++ {
84 l.Add(i, i)
85 }
86 if l.Len() != 128 {
87 t.Fatalf("bad len: %v", l.Len())
88 }
89
90 if evictCounter != 128 {
91 t.Fatalf("bad evict count: %v", evictCounter)
92 }
93
94 for i, k := range l.Keys() {
95 if v, ok := l.Get(k); !ok || v != k || v != i+128 {
96 t.Fatalf("bad key: %v", k)
97 }
98 }
99 for i, v := range l.Values() {
100 if v != i+128 {
101 t.Fatalf("bad value: %v", v)
102 }
103 }
104 for i := 0; i < 128; i++ {
105 if _, ok := l.Get(i); ok {
106 t.Fatalf("should be evicted")
107 }
108 }
109 for i := 128; i < 256; i++ {
110 if _, ok := l.Get(i); !ok {
111 t.Fatalf("should not be evicted")
112 }
113 }
114 for i := 128; i < 192; i++ {
115 l.Remove(i)
116 if _, ok := l.Get(i); ok {
117 t.Fatalf("should be deleted")
118 }
119 }
120
121 l.Get(192)
122
123 for i, k := range l.Keys() {
124 if (i < 63 && k != i+193) || (i == 63 && k != 192) {
125 t.Fatalf("out of order key: %v", k)
126 }
127 }
128
129 l.Purge()
130 if l.Len() != 0 {
131 t.Fatalf("bad len: %v", l.Len())
132 }
133 if _, ok := l.Get(200); ok {
134 t.Fatalf("should contain nothing")
135 }
136 }
137
138
139 func TestLRUAdd(t *testing.T) {
140 evictCounter := 0
141 onEvicted := func(k int, v int) {
142 evictCounter++
143 }
144
145 l, err := NewWithEvict(1, onEvicted)
146 if err != nil {
147 t.Fatalf("err: %v", err)
148 }
149
150 if l.Add(1, 1) == true || evictCounter != 0 {
151 t.Errorf("should not have an eviction")
152 }
153 if l.Add(2, 2) == false || evictCounter != 1 {
154 t.Errorf("should have an eviction")
155 }
156 }
157
158
159 func TestLRUContains(t *testing.T) {
160 l, err := New[int, int](2)
161 if err != nil {
162 t.Fatalf("err: %v", err)
163 }
164
165 l.Add(1, 1)
166 l.Add(2, 2)
167 if !l.Contains(1) {
168 t.Errorf("1 should be contained")
169 }
170
171 l.Add(3, 3)
172 if l.Contains(1) {
173 t.Errorf("Contains should not have updated recent-ness of 1")
174 }
175 }
176
177
178 func TestLRUContainsOrAdd(t *testing.T) {
179 l, err := New[int, int](2)
180 if err != nil {
181 t.Fatalf("err: %v", err)
182 }
183
184 l.Add(1, 1)
185 l.Add(2, 2)
186 contains, evict := l.ContainsOrAdd(1, 1)
187 if !contains {
188 t.Errorf("1 should be contained")
189 }
190 if evict {
191 t.Errorf("nothing should be evicted here")
192 }
193
194 l.Add(3, 3)
195 contains, evict = l.ContainsOrAdd(1, 1)
196 if contains {
197 t.Errorf("1 should not have been contained")
198 }
199 if !evict {
200 t.Errorf("an eviction should have occurred")
201 }
202 if !l.Contains(1) {
203 t.Errorf("now 1 should be contained")
204 }
205 }
206
207
208 func TestLRUPeekOrAdd(t *testing.T) {
209 l, err := New[int, int](2)
210 if err != nil {
211 t.Fatalf("err: %v", err)
212 }
213
214 l.Add(1, 1)
215 l.Add(2, 2)
216 previous, contains, evict := l.PeekOrAdd(1, 1)
217 if !contains {
218 t.Errorf("1 should be contained")
219 }
220 if evict {
221 t.Errorf("nothing should be evicted here")
222 }
223 if previous != 1 {
224 t.Errorf("previous is not equal to 1")
225 }
226
227 l.Add(3, 3)
228 contains, evict = l.ContainsOrAdd(1, 1)
229 if contains {
230 t.Errorf("1 should not have been contained")
231 }
232 if !evict {
233 t.Errorf("an eviction should have occurred")
234 }
235 if !l.Contains(1) {
236 t.Errorf("now 1 should be contained")
237 }
238 }
239
240
241 func TestLRUPeek(t *testing.T) {
242 l, err := New[int, int](2)
243 if err != nil {
244 t.Fatalf("err: %v", err)
245 }
246
247 l.Add(1, 1)
248 l.Add(2, 2)
249 if v, ok := l.Peek(1); !ok || v != 1 {
250 t.Errorf("1 should be set to 1: %v, %v", v, ok)
251 }
252
253 l.Add(3, 3)
254 if l.Contains(1) {
255 t.Errorf("should not have updated recent-ness of 1")
256 }
257 }
258
259
260 func TestLRUResize(t *testing.T) {
261 onEvictCounter := 0
262 onEvicted := func(k int, v int) {
263 onEvictCounter++
264 }
265 l, err := NewWithEvict(2, onEvicted)
266 if err != nil {
267 t.Fatalf("err: %v", err)
268 }
269
270
271 l.Add(1, 1)
272 l.Add(2, 2)
273 evicted := l.Resize(1)
274 if evicted != 1 {
275 t.Errorf("1 element should have been evicted: %v", evicted)
276 }
277 if onEvictCounter != 1 {
278 t.Errorf("onEvicted should have been called 1 time: %v", onEvictCounter)
279 }
280
281 l.Add(3, 3)
282 if l.Contains(1) {
283 t.Errorf("Element 1 should have been evicted")
284 }
285
286
287 evicted = l.Resize(2)
288 if evicted != 0 {
289 t.Errorf("0 elements should have been evicted: %v", evicted)
290 }
291
292 l.Add(4, 4)
293 if !l.Contains(3) || !l.Contains(4) {
294 t.Errorf("Cache should have contained 2 elements")
295 }
296 }
297
298 func (c *Cache[K, V]) wantKeys(t *testing.T, want []K) {
299 t.Helper()
300 got := c.Keys()
301 if !reflect.DeepEqual(got, want) {
302 t.Errorf("wrong keys got: %v, want: %v ", got, want)
303 }
304 }
305
306 func TestCache_EvictionSameKey(t *testing.T) {
307 t.Run("Add", func(t *testing.T) {
308 var evictedKeys []int
309
310 cache, _ := NewWithEvict(
311 2,
312 func(key int, _ struct{}) {
313 evictedKeys = append(evictedKeys, key)
314 })
315
316 if evicted := cache.Add(1, struct{}{}); evicted {
317 t.Error("First 1: got unexpected eviction")
318 }
319 cache.wantKeys(t, []int{1})
320
321 if evicted := cache.Add(2, struct{}{}); evicted {
322 t.Error("2: got unexpected eviction")
323 }
324 cache.wantKeys(t, []int{1, 2})
325
326 if evicted := cache.Add(1, struct{}{}); evicted {
327 t.Error("Second 1: got unexpected eviction")
328 }
329 cache.wantKeys(t, []int{2, 1})
330
331 if evicted := cache.Add(3, struct{}{}); !evicted {
332 t.Error("3: did not get expected eviction")
333 }
334 cache.wantKeys(t, []int{1, 3})
335
336 want := []int{2}
337 if !reflect.DeepEqual(evictedKeys, want) {
338 t.Errorf("evictedKeys got: %v want: %v", evictedKeys, want)
339 }
340 })
341
342 t.Run("ContainsOrAdd", func(t *testing.T) {
343 var evictedKeys []int
344
345 cache, _ := NewWithEvict(
346 2,
347 func(key int, _ struct{}) {
348 evictedKeys = append(evictedKeys, key)
349 })
350
351 contained, evicted := cache.ContainsOrAdd(1, struct{}{})
352 if contained {
353 t.Error("First 1: got unexpected contained")
354 }
355 if evicted {
356 t.Error("First 1: got unexpected eviction")
357 }
358 cache.wantKeys(t, []int{1})
359
360 contained, evicted = cache.ContainsOrAdd(2, struct{}{})
361 if contained {
362 t.Error("2: got unexpected contained")
363 }
364 if evicted {
365 t.Error("2: got unexpected eviction")
366 }
367 cache.wantKeys(t, []int{1, 2})
368
369 contained, evicted = cache.ContainsOrAdd(1, struct{}{})
370 if !contained {
371 t.Error("Second 1: did not get expected contained")
372 }
373 if evicted {
374 t.Error("Second 1: got unexpected eviction")
375 }
376 cache.wantKeys(t, []int{1, 2})
377
378 contained, evicted = cache.ContainsOrAdd(3, struct{}{})
379 if contained {
380 t.Error("3: got unexpected contained")
381 }
382 if !evicted {
383 t.Error("3: did not get expected eviction")
384 }
385 cache.wantKeys(t, []int{2, 3})
386
387 want := []int{1}
388 if !reflect.DeepEqual(evictedKeys, want) {
389 t.Errorf("evictedKeys got: %v want: %v", evictedKeys, want)
390 }
391 })
392
393 t.Run("PeekOrAdd", func(t *testing.T) {
394 var evictedKeys []int
395
396 cache, _ := NewWithEvict(
397 2,
398 func(key int, _ struct{}) {
399 evictedKeys = append(evictedKeys, key)
400 })
401
402 _, contained, evicted := cache.PeekOrAdd(1, struct{}{})
403 if contained {
404 t.Error("First 1: got unexpected contained")
405 }
406 if evicted {
407 t.Error("First 1: got unexpected eviction")
408 }
409 cache.wantKeys(t, []int{1})
410
411 _, contained, evicted = cache.PeekOrAdd(2, struct{}{})
412 if contained {
413 t.Error("2: got unexpected contained")
414 }
415 if evicted {
416 t.Error("2: got unexpected eviction")
417 }
418 cache.wantKeys(t, []int{1, 2})
419
420 _, contained, evicted = cache.PeekOrAdd(1, struct{}{})
421 if !contained {
422 t.Error("Second 1: did not get expected contained")
423 }
424 if evicted {
425 t.Error("Second 1: got unexpected eviction")
426 }
427 cache.wantKeys(t, []int{1, 2})
428
429 _, contained, evicted = cache.PeekOrAdd(3, struct{}{})
430 if contained {
431 t.Error("3: got unexpected contained")
432 }
433 if !evicted {
434 t.Error("3: did not get expected eviction")
435 }
436 cache.wantKeys(t, []int{2, 3})
437
438 want := []int{1}
439 if !reflect.DeepEqual(evictedKeys, want) {
440 t.Errorf("evictedKeys got: %v want: %v", evictedKeys, want)
441 }
442 })
443 }
444
View as plain text