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