1 package ristretto
2
3 import (
4 "testing"
5 "time"
6
7 "github.com/stretchr/testify/require"
8 )
9
10 func TestPolicy(t *testing.T) {
11 defer func() {
12 require.Nil(t, recover())
13 }()
14 newPolicy(100, 10)
15 }
16
17 func TestPolicyMetrics(t *testing.T) {
18 p := newDefaultPolicy(100, 10)
19 p.CollectMetrics(newMetrics())
20 require.NotNil(t, p.metrics)
21 require.NotNil(t, p.evict.metrics)
22 }
23
24 func TestPolicyProcessItems(t *testing.T) {
25 p := newDefaultPolicy(100, 10)
26 p.itemsCh <- []uint64{1, 2, 2}
27 time.Sleep(wait)
28 p.Lock()
29 require.Equal(t, int64(2), p.admit.Estimate(2))
30 require.Equal(t, int64(1), p.admit.Estimate(1))
31 p.Unlock()
32
33 p.stop <- struct{}{}
34 p.itemsCh <- []uint64{3, 3, 3}
35 time.Sleep(wait)
36 p.Lock()
37 require.Equal(t, int64(0), p.admit.Estimate(3))
38 p.Unlock()
39 }
40
41 func TestPolicyPush(t *testing.T) {
42 p := newDefaultPolicy(100, 10)
43 require.True(t, p.Push([]uint64{}))
44
45 keepCount := 0
46 for i := 0; i < 10; i++ {
47 if p.Push([]uint64{1, 2, 3, 4, 5}) {
48 keepCount++
49 }
50 }
51 require.NotEqual(t, 0, keepCount)
52 }
53
54 func TestPolicyAdd(t *testing.T) {
55 p := newDefaultPolicy(1000, 100)
56 if victims, added := p.Add(1, 101); victims != nil || added {
57 t.Fatal("can't add an item bigger than entire cache")
58 }
59 p.Lock()
60 p.evict.add(1, 1)
61 p.admit.Increment(1)
62 p.admit.Increment(2)
63 p.admit.Increment(3)
64 p.Unlock()
65
66 victims, added := p.Add(1, 1)
67 require.Nil(t, victims)
68 require.False(t, added)
69
70 victims, added = p.Add(2, 20)
71 require.Nil(t, victims)
72 require.True(t, added)
73
74 victims, added = p.Add(3, 90)
75 require.NotNil(t, victims)
76 require.True(t, added)
77
78 victims, added = p.Add(4, 20)
79 require.NotNil(t, victims)
80 require.False(t, added)
81 }
82
83 func TestPolicyHas(t *testing.T) {
84 p := newDefaultPolicy(100, 10)
85 p.Add(1, 1)
86 require.True(t, p.Has(1))
87 require.False(t, p.Has(2))
88 }
89
90 func TestPolicyDel(t *testing.T) {
91 p := newDefaultPolicy(100, 10)
92 p.Add(1, 1)
93 p.Del(1)
94 p.Del(2)
95 require.False(t, p.Has(1))
96 require.False(t, p.Has(2))
97 }
98
99 func TestPolicyCap(t *testing.T) {
100 p := newDefaultPolicy(100, 10)
101 p.Add(1, 1)
102 require.Equal(t, int64(9), p.Cap())
103 }
104
105 func TestPolicyUpdate(t *testing.T) {
106 p := newDefaultPolicy(100, 10)
107 p.Add(1, 1)
108 p.Update(1, 2)
109 p.Lock()
110 require.Equal(t, int64(2), p.evict.keyCosts[1])
111 p.Unlock()
112 }
113
114 func TestPolicyCost(t *testing.T) {
115 p := newDefaultPolicy(100, 10)
116 p.Add(1, 2)
117 require.Equal(t, int64(2), p.Cost(1))
118 require.Equal(t, int64(-1), p.Cost(2))
119 }
120
121 func TestPolicyClear(t *testing.T) {
122 p := newDefaultPolicy(100, 10)
123 p.Add(1, 1)
124 p.Add(2, 2)
125 p.Add(3, 3)
126 p.Clear()
127 require.Equal(t, int64(10), p.Cap())
128 require.False(t, p.Has(1))
129 require.False(t, p.Has(2))
130 require.False(t, p.Has(3))
131 }
132
133 func TestPolicyClose(t *testing.T) {
134 defer func() {
135 require.NotNil(t, recover())
136 }()
137
138 p := newDefaultPolicy(100, 10)
139 p.Add(1, 1)
140 p.Close()
141 p.itemsCh <- []uint64{1}
142 }
143
144 func TestSampledLFUAdd(t *testing.T) {
145 e := newSampledLFU(4)
146 e.add(1, 1)
147 e.add(2, 2)
148 e.add(3, 1)
149 require.Equal(t, int64(4), e.used)
150 require.Equal(t, int64(2), e.keyCosts[2])
151 }
152
153 func TestSampledLFUDel(t *testing.T) {
154 e := newSampledLFU(4)
155 e.add(1, 1)
156 e.add(2, 2)
157 e.del(2)
158 require.Equal(t, int64(1), e.used)
159 _, ok := e.keyCosts[2]
160 require.False(t, ok)
161 e.del(4)
162 }
163
164 func TestSampledLFUUpdate(t *testing.T) {
165 e := newSampledLFU(4)
166 e.add(1, 1)
167 require.True(t, e.updateIfHas(1, 2))
168 require.Equal(t, int64(2), e.used)
169 require.False(t, e.updateIfHas(2, 2))
170 }
171
172 func TestSampledLFUClear(t *testing.T) {
173 e := newSampledLFU(4)
174 e.add(1, 1)
175 e.add(2, 2)
176 e.add(3, 1)
177 e.clear()
178 require.Equal(t, 0, len(e.keyCosts))
179 require.Equal(t, int64(0), e.used)
180 }
181
182 func TestSampledLFURoom(t *testing.T) {
183 e := newSampledLFU(16)
184 e.add(1, 1)
185 e.add(2, 2)
186 e.add(3, 3)
187 require.Equal(t, int64(6), e.roomLeft(4))
188 }
189
190 func TestSampledLFUSample(t *testing.T) {
191 e := newSampledLFU(16)
192 e.add(4, 4)
193 e.add(5, 5)
194 sample := e.fillSample([]*policyPair{
195 {1, 1},
196 {2, 2},
197 {3, 3},
198 })
199 k := sample[len(sample)-1].key
200 require.Equal(t, 5, len(sample))
201 require.NotEqual(t, 1, k)
202 require.NotEqual(t, 2, k)
203 require.NotEqual(t, 3, k)
204 require.Equal(t, len(sample), len(e.fillSample(sample)))
205 e.del(5)
206 sample = e.fillSample(sample[:len(sample)-2])
207 require.Equal(t, 4, len(sample))
208 }
209
210 func TestTinyLFUIncrement(t *testing.T) {
211 a := newTinyLFU(4)
212 a.Increment(1)
213 a.Increment(1)
214 a.Increment(1)
215 require.True(t, a.door.Has(1))
216 require.Equal(t, int64(2), a.freq.Estimate(1))
217
218 a.Increment(1)
219 require.False(t, a.door.Has(1))
220 require.Equal(t, int64(1), a.freq.Estimate(1))
221 }
222
223 func TestTinyLFUEstimate(t *testing.T) {
224 a := newTinyLFU(8)
225 a.Increment(1)
226 a.Increment(1)
227 a.Increment(1)
228 require.Equal(t, int64(3), a.Estimate(1))
229 require.Equal(t, int64(0), a.Estimate(2))
230 }
231
232 func TestTinyLFUPush(t *testing.T) {
233 a := newTinyLFU(16)
234 a.Push([]uint64{1, 2, 2, 3, 3, 3})
235 require.Equal(t, int64(1), a.Estimate(1))
236 require.Equal(t, int64(2), a.Estimate(2))
237 require.Equal(t, int64(3), a.Estimate(3))
238 require.Equal(t, int64(6), a.incrs)
239 }
240
241 func TestTinyLFUClear(t *testing.T) {
242 a := newTinyLFU(16)
243 a.Push([]uint64{1, 3, 3, 3})
244 a.clear()
245 require.Equal(t, int64(0), a.incrs)
246 require.Equal(t, int64(0), a.Estimate(3))
247 }
248
View as plain text