1 package lru
2
3 import (
4 "testing"
5 )
6
7 func BenchmarkLRU_Rand(b *testing.B) {
8 l, err := New(8192)
9 if err != nil {
10 b.Fatalf("err: %v", err)
11 }
12
13 trace := make([]int64, b.N*2)
14 for i := 0; i < b.N*2; i++ {
15 trace[i] = getRand(b) % 32768
16 }
17
18 b.ResetTimer()
19
20 var hit, miss int
21 for i := 0; i < 2*b.N; i++ {
22 if i%2 == 0 {
23 l.Add(trace[i], trace[i])
24 } else {
25 _, ok := l.Get(trace[i])
26 if ok {
27 hit++
28 } else {
29 miss++
30 }
31 }
32 }
33 b.Logf("hit: %d miss: %d ratio: %f", hit, miss, float64(hit)/float64(miss))
34 }
35
36 func BenchmarkLRU_Freq(b *testing.B) {
37 l, err := New(8192)
38 if err != nil {
39 b.Fatalf("err: %v", err)
40 }
41
42 trace := make([]int64, b.N*2)
43 for i := 0; i < b.N*2; i++ {
44 if i%2 == 0 {
45 trace[i] = getRand(b) % 16384
46 } else {
47 trace[i] = getRand(b) % 32768
48 }
49 }
50
51 b.ResetTimer()
52
53 for i := 0; i < b.N; i++ {
54 l.Add(trace[i], trace[i])
55 }
56 var hit, miss int
57 for i := 0; i < b.N; i++ {
58 _, ok := l.Get(trace[i])
59 if ok {
60 hit++
61 } else {
62 miss++
63 }
64 }
65 b.Logf("hit: %d miss: %d ratio: %f", hit, miss, float64(hit)/float64(miss))
66 }
67
68 func TestLRU(t *testing.T) {
69 evictCounter := 0
70 onEvicted := func(k interface{}, v interface{}) {
71 if k != v {
72 t.Fatalf("Evict values not equal (%v!=%v)", k, v)
73 }
74 evictCounter++
75 }
76 l, err := NewWithEvict(128, onEvicted)
77 if err != nil {
78 t.Fatalf("err: %v", err)
79 }
80
81 for i := 0; i < 256; i++ {
82 l.Add(i, i)
83 }
84 if l.Len() != 128 {
85 t.Fatalf("bad len: %v", l.Len())
86 }
87
88 if evictCounter != 128 {
89 t.Fatalf("bad evict count: %v", evictCounter)
90 }
91
92 for i, k := range l.Keys() {
93 if v, ok := l.Get(k); !ok || v != k || v != i+128 {
94 t.Fatalf("bad key: %v", k)
95 }
96 }
97 for i := 0; i < 128; i++ {
98 _, ok := l.Get(i)
99 if ok {
100 t.Fatalf("should be evicted")
101 }
102 }
103 for i := 128; i < 256; i++ {
104 _, ok := l.Get(i)
105 if !ok {
106 t.Fatalf("should not be evicted")
107 }
108 }
109 for i := 128; i < 192; i++ {
110 l.Remove(i)
111 _, ok := l.Get(i)
112 if ok {
113 t.Fatalf("should be deleted")
114 }
115 }
116
117 l.Get(192)
118
119 for i, k := range l.Keys() {
120 if (i < 63 && k != i+193) || (i == 63 && k != 192) {
121 t.Fatalf("out of order key: %v", k)
122 }
123 }
124
125 l.Purge()
126 if l.Len() != 0 {
127 t.Fatalf("bad len: %v", l.Len())
128 }
129 if _, ok := l.Get(200); ok {
130 t.Fatalf("should contain nothing")
131 }
132 }
133
134
135 func TestLRUAdd(t *testing.T) {
136 evictCounter := 0
137 onEvicted := func(k interface{}, v interface{}) {
138 evictCounter++
139 }
140
141 l, err := NewWithEvict(1, onEvicted)
142 if err != nil {
143 t.Fatalf("err: %v", err)
144 }
145
146 if l.Add(1, 1) == true || evictCounter != 0 {
147 t.Errorf("should not have an eviction")
148 }
149 if l.Add(2, 2) == false || evictCounter != 1 {
150 t.Errorf("should have an eviction")
151 }
152 }
153
154
155 func TestLRUContains(t *testing.T) {
156 l, err := New(2)
157 if err != nil {
158 t.Fatalf("err: %v", err)
159 }
160
161 l.Add(1, 1)
162 l.Add(2, 2)
163 if !l.Contains(1) {
164 t.Errorf("1 should be contained")
165 }
166
167 l.Add(3, 3)
168 if l.Contains(1) {
169 t.Errorf("Contains should not have updated recent-ness of 1")
170 }
171 }
172
173
174 func TestLRUContainsOrAdd(t *testing.T) {
175 l, err := New(2)
176 if err != nil {
177 t.Fatalf("err: %v", err)
178 }
179
180 l.Add(1, 1)
181 l.Add(2, 2)
182 contains, evict := l.ContainsOrAdd(1, 1)
183 if !contains {
184 t.Errorf("1 should be contained")
185 }
186 if evict {
187 t.Errorf("nothing should be evicted here")
188 }
189
190 l.Add(3, 3)
191 contains, evict = l.ContainsOrAdd(1, 1)
192 if contains {
193 t.Errorf("1 should not have been contained")
194 }
195 if !evict {
196 t.Errorf("an eviction should have occurred")
197 }
198 if !l.Contains(1) {
199 t.Errorf("now 1 should be contained")
200 }
201 }
202
203
204 func TestLRUPeekOrAdd(t *testing.T) {
205 l, err := New(2)
206 if err != nil {
207 t.Fatalf("err: %v", err)
208 }
209
210 l.Add(1, 1)
211 l.Add(2, 2)
212 previous, contains, evict := l.PeekOrAdd(1, 1)
213 if !contains {
214 t.Errorf("1 should be contained")
215 }
216 if evict {
217 t.Errorf("nothing should be evicted here")
218 }
219 if previous != 1 {
220 t.Errorf("previous is not equal to 1")
221 }
222
223 l.Add(3, 3)
224 contains, evict = l.ContainsOrAdd(1, 1)
225 if contains {
226 t.Errorf("1 should not have been contained")
227 }
228 if !evict {
229 t.Errorf("an eviction should have occurred")
230 }
231 if !l.Contains(1) {
232 t.Errorf("now 1 should be contained")
233 }
234 }
235
236
237 func TestLRUPeek(t *testing.T) {
238 l, err := New(2)
239 if err != nil {
240 t.Fatalf("err: %v", err)
241 }
242
243 l.Add(1, 1)
244 l.Add(2, 2)
245 if v, ok := l.Peek(1); !ok || v != 1 {
246 t.Errorf("1 should be set to 1: %v, %v", v, ok)
247 }
248
249 l.Add(3, 3)
250 if l.Contains(1) {
251 t.Errorf("should not have updated recent-ness of 1")
252 }
253 }
254
255
256 func TestLRUResize(t *testing.T) {
257 onEvictCounter := 0
258 onEvicted := func(k interface{}, v interface{}) {
259 onEvictCounter++
260 }
261 l, err := NewWithEvict(2, onEvicted)
262 if err != nil {
263 t.Fatalf("err: %v", err)
264 }
265
266
267 l.Add(1, 1)
268 l.Add(2, 2)
269 evicted := l.Resize(1)
270 if evicted != 1 {
271 t.Errorf("1 element should have been evicted: %v", evicted)
272 }
273 if onEvictCounter != 1 {
274 t.Errorf("onEvicted should have been called 1 time: %v", onEvictCounter)
275 }
276
277 l.Add(3, 3)
278 if l.Contains(1) {
279 t.Errorf("Element 1 should have been evicted")
280 }
281
282
283 evicted = l.Resize(2)
284 if evicted != 0 {
285 t.Errorf("0 elements should have been evicted: %v", evicted)
286 }
287
288 l.Add(4, 4)
289 if !l.Contains(3) || !l.Contains(4) {
290 t.Errorf("Cache should have contained 2 elements")
291 }
292 }
293
View as plain text