1
2
3
4 package simplelru
5
6 import (
7 "reflect"
8 "testing"
9 )
10
11 func TestLRU(t *testing.T) {
12 evictCounter := 0
13 onEvicted := func(k int, v int) {
14 if k != v {
15 t.Fatalf("Evict values not equal (%v!=%v)", k, v)
16 }
17 evictCounter++
18 }
19 l, err := NewLRU(128, onEvicted)
20 if err != nil {
21 t.Fatalf("err: %v", err)
22 }
23
24 for i := 0; i < 256; i++ {
25 l.Add(i, i)
26 }
27 if l.Len() != 128 {
28 t.Fatalf("bad len: %v", l.Len())
29 }
30
31 if evictCounter != 128 {
32 t.Fatalf("bad evict count: %v", evictCounter)
33 }
34
35 for i, k := range l.Keys() {
36 if v, ok := l.Get(k); !ok || v != k || v != i+128 {
37 t.Fatalf("bad key: %v", k)
38 }
39 }
40 for i, v := range l.Values() {
41 if v != i+128 {
42 t.Fatalf("bad value: %v", v)
43 }
44 }
45 for i := 0; i < 128; i++ {
46 if _, ok := l.Get(i); ok {
47 t.Fatalf("should be evicted")
48 }
49 }
50 for i := 128; i < 256; i++ {
51 if _, ok := l.Get(i); !ok {
52 t.Fatalf("should not be evicted")
53 }
54 }
55 for i := 128; i < 192; i++ {
56 if ok := l.Remove(i); !ok {
57 t.Fatalf("should be contained")
58 }
59 if ok := l.Remove(i); ok {
60 t.Fatalf("should not be contained")
61 }
62 if _, ok := l.Get(i); ok {
63 t.Fatalf("should be deleted")
64 }
65 }
66
67 l.Get(192)
68
69 for i, k := range l.Keys() {
70 if (i < 63 && k != i+193) || (i == 63 && k != 192) {
71 t.Fatalf("out of order key: %v", k)
72 }
73 }
74
75 l.Purge()
76 if l.Len() != 0 {
77 t.Fatalf("bad len: %v", l.Len())
78 }
79 if _, ok := l.Get(200); ok {
80 t.Fatalf("should contain nothing")
81 }
82 }
83
84 func TestLRU_GetOldest_RemoveOldest(t *testing.T) {
85 l, err := NewLRU[int, int](128, nil)
86 if err != nil {
87 t.Fatalf("err: %v", err)
88 }
89 for i := 0; i < 256; i++ {
90 l.Add(i, i)
91 }
92 k, _, ok := l.GetOldest()
93 if !ok {
94 t.Fatalf("missing")
95 }
96 if k != 128 {
97 t.Fatalf("bad: %v", k)
98 }
99
100 k, _, ok = l.RemoveOldest()
101 if !ok {
102 t.Fatalf("missing")
103 }
104 if k != 128 {
105 t.Fatalf("bad: %v", k)
106 }
107
108 k, _, ok = l.RemoveOldest()
109 if !ok {
110 t.Fatalf("missing")
111 }
112 if k != 129 {
113 t.Fatalf("bad: %v", k)
114 }
115 }
116
117
118 func TestLRU_Add(t *testing.T) {
119 evictCounter := 0
120 onEvicted := func(k int, v int) {
121 evictCounter++
122 }
123
124 l, err := NewLRU(1, onEvicted)
125 if err != nil {
126 t.Fatalf("err: %v", err)
127 }
128
129 if l.Add(1, 1) == true || evictCounter != 0 {
130 t.Errorf("should not have an eviction")
131 }
132 if l.Add(2, 2) == false || evictCounter != 1 {
133 t.Errorf("should have an eviction")
134 }
135 }
136
137
138 func TestLRU_Contains(t *testing.T) {
139 l, err := NewLRU[int, int](2, nil)
140 if err != nil {
141 t.Fatalf("err: %v", err)
142 }
143
144 l.Add(1, 1)
145 l.Add(2, 2)
146 if !l.Contains(1) {
147 t.Errorf("1 should be contained")
148 }
149
150 l.Add(3, 3)
151 if l.Contains(1) {
152 t.Errorf("Contains should not have updated recent-ness of 1")
153 }
154 }
155
156
157 func TestLRU_Peek(t *testing.T) {
158 l, err := NewLRU[int, int](2, nil)
159 if err != nil {
160 t.Fatalf("err: %v", err)
161 }
162
163 l.Add(1, 1)
164 l.Add(2, 2)
165 if v, ok := l.Peek(1); !ok || v != 1 {
166 t.Errorf("1 should be set to 1: %v, %v", v, ok)
167 }
168
169 l.Add(3, 3)
170 if l.Contains(1) {
171 t.Errorf("should not have updated recent-ness of 1")
172 }
173 }
174
175
176 func TestLRU_Resize(t *testing.T) {
177 onEvictCounter := 0
178 onEvicted := func(k int, v int) {
179 onEvictCounter++
180 }
181 l, err := NewLRU(2, onEvicted)
182 if err != nil {
183 t.Fatalf("err: %v", err)
184 }
185
186
187 l.Add(1, 1)
188 l.Add(2, 2)
189 evicted := l.Resize(1)
190 if evicted != 1 {
191 t.Errorf("1 element should have been evicted: %v", evicted)
192 }
193 if onEvictCounter != 1 {
194 t.Errorf("onEvicted should have been called 1 time: %v", onEvictCounter)
195 }
196
197 l.Add(3, 3)
198 if l.Contains(1) {
199 t.Errorf("Element 1 should have been evicted")
200 }
201
202
203 evicted = l.Resize(2)
204 if evicted != 0 {
205 t.Errorf("0 elements should have been evicted: %v", evicted)
206 }
207
208 l.Add(4, 4)
209 if !l.Contains(3) || !l.Contains(4) {
210 t.Errorf("Cache should have contained 2 elements")
211 }
212 }
213
214 func (c *LRU[K, V]) wantKeys(t *testing.T, want []K) {
215 t.Helper()
216 got := c.Keys()
217 if !reflect.DeepEqual(got, want) {
218 t.Errorf("wrong keys got: %v, want: %v ", got, want)
219 }
220 }
221
222 func TestCache_EvictionSameKey(t *testing.T) {
223 var evictedKeys []int
224
225 cache, _ := NewLRU(
226 2,
227 func(key int, _ struct{}) {
228 evictedKeys = append(evictedKeys, key)
229 })
230
231 if evicted := cache.Add(1, struct{}{}); evicted {
232 t.Error("First 1: got unexpected eviction")
233 }
234 cache.wantKeys(t, []int{1})
235
236 if evicted := cache.Add(2, struct{}{}); evicted {
237 t.Error("2: got unexpected eviction")
238 }
239 cache.wantKeys(t, []int{1, 2})
240
241 if evicted := cache.Add(1, struct{}{}); evicted {
242 t.Error("Second 1: got unexpected eviction")
243 }
244 cache.wantKeys(t, []int{2, 1})
245
246 if evicted := cache.Add(3, struct{}{}); !evicted {
247 t.Error("3: did not get expected eviction")
248 }
249 cache.wantKeys(t, []int{1, 3})
250
251 want := []int{2}
252 if !reflect.DeepEqual(evictedKeys, want) {
253 t.Errorf("evictedKeys got: %v want: %v", evictedKeys, want)
254 }
255 }
256
View as plain text