Codebase list golang-github-renekroon-ttlcache / upstream/1.4.0+git20190429.e7780e9
New upstream version 1.4.0+git20190429.e7780e9 Sascha Steinbiss 4 years ago
9 changed file(s) with 974 addition(s) and 0 deletion(s). Raw diff Collapse all Expand all
+21
-0
.travis.yml less more
0 language: go
1
2 go:
3 - 1.12
4 - 1.11
5 git:
6 depth: 1
7
8 install:
9 - go install -race std
10 - go get golang.org/x/tools/cmd/cover
11 - go get golang.org/x/lint/golint
12 - go get github.com/tools/godep
13 - export PATH=$HOME/gopath/bin:$PATH
14 - godep restore
15
16 script:
17 - golint .
18 - go test ./... -race -count=1 -timeout=1m -run .
19 - go test -cover ./...
20 - go test -run=Bench.* -bench=. -benchmem⏎
+21
-0
LICENSE less more
0 MIT License
1
2 Copyright (c) 2018 Rene Kroon
3
4 Permission is hereby granted, free of charge, to any person obtaining a copy
5 of this software and associated documentation files (the "Software"), to deal
6 in the Software without restriction, including without limitation the rights
7 to use, copy, modify, merge, publish, distribute, sublicense, and/or sell
8 copies of the Software, and to permit persons to whom the Software is
9 furnished to do so, subject to the following conditions:
10
11 The above copyright notice and this permission notice shall be included in all
12 copies or substantial portions of the Software.
13
14 THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS OR
15 IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY,
16 FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT. IN NO EVENT SHALL THE
17 AUTHORS OR COPYRIGHT HOLDERS BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER
18 LIABILITY, WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING FROM,
19 OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN THE
20 SOFTWARE.
+61
-0
Readme.md less more
0 ## TTLCache - an in-memory cache with expiration
1
2 TTLCache is a simple key/value cache in golang with the following functions:
3
4 1. Thread-safe
5 2. Individual expiring time or global expiring time, you can choose
6 3. Auto-Extending expiration on `Get` -or- DNS style TTL, see `SkipTtlExtensionOnHit(bool)`
7 4. Fast and memory efficient
8 5. Can trigger callback on key expiration
9
10 [![Build Status](https://travis-ci.org/ReneKroon/ttlcache.svg?branch=master)](https://travis-ci.org/ReneKroon/ttlcache)
11
12 #### Usage
13 ```go
14 import (
15 "time"
16 "fmt"
17
18 "github.com/ReneKroon/ttlcache"
19 )
20
21 func main () {
22 newItemCallback := func(key string, value interface{}) {
23 fmt.Printf("New key(%s) added\n", key)
24 }
25 checkExpirationCallback := func(key string, value interface{}) bool {
26 if key == "key1" {
27 // if the key equals "key1", the value
28 // will not be allowed to expire
29 return false
30 }
31 // all other values are allowed to expire
32 return true
33 }
34 expirationCallback := func(key string, value interface{}) {
35 fmt.Printf("This key(%s) has expired\n", key)
36 }
37
38 cache := ttlcache.NewCache()
39 cache.SetTTL(time.Duration(10 * time.Second))
40 cache.SetExpirationCallback(expirationCallback)
41
42 cache.Set("key", "value")
43 cache.SetWithTTL("keyWithTTL", "value", 10 * time.Second)
44
45 value, exists := cache.Get("key")
46 count := cache.Count()
47 result := cache.Remove("key")
48 }
49 ```
50
51 #### Original Project
52
53 TTLCache was forked from [wunderlist/ttlcache](https://github.com/wunderlist/ttlcache) to add extra functions not avaiable in the original scope.
54 The main differences are:
55
56 1. A item can store any kind of object, previously, only strings could be saved
57 2. Optionally, you can add callbacks to: check if a value should expire, be notified if a value expires, and be notified when new values are added to the cache
58 3. The expiration can be either global or per item
59 4. Can exist items without expiration time
60 5. Expirations and callbacks are realtime. Don't have a pooling time to check anymore, now it's done with a heap.
+259
-0
cache.go less more
0 package ttlcache
1
2 import (
3 "sync"
4 "time"
5 )
6
7 // CheckExpireCallback is used as a callback for an external check on item expiration
8 type checkExpireCallback func(key string, value interface{}) bool
9
10 // ExpireCallback is used as a callback on item expiration or when notifying of an item new to the cache
11 type expireCallback func(key string, value interface{})
12
13 // Cache is a synchronized map of items that can auto-expire once stale
14 type Cache struct {
15 mutex sync.RWMutex
16 ttl time.Duration
17 items map[string]*item
18 expireCallback expireCallback
19 checkExpireCallback checkExpireCallback
20 newItemCallback expireCallback
21 priorityQueue *priorityQueue
22 expirationNotification chan bool
23 expirationTime time.Time
24 skipTTLExtension bool
25 }
26
27 func (cache *Cache) getItem(key string) (*item, bool) {
28 cache.mutex.RLock()
29
30 item, exists := cache.items[key]
31 if !exists || item.expired() {
32 cache.mutex.RUnlock()
33 return nil, false
34 }
35
36 if item.ttl >= 0 && (item.ttl > 0 || cache.ttl > 0) {
37 if cache.ttl > 0 && item.ttl == 0 {
38 item.ttl = cache.ttl
39 }
40
41 if !cache.skipTTLExtension {
42 item.touch()
43 }
44 cache.priorityQueue.update(item)
45 }
46
47 cache.mutex.RUnlock()
48 cache.expirationNotificationTrigger(item)
49 return item, exists
50 }
51
52 func (cache *Cache) startExpirationProcessing() {
53 for {
54 var sleepTime time.Duration
55 cache.mutex.Lock()
56 if cache.priorityQueue.Len() > 0 {
57 sleepTime = time.Until(cache.priorityQueue.items[0].expireAt)
58 if sleepTime < 0 && cache.priorityQueue.items[0].expireAt.IsZero() {
59 sleepTime = time.Hour
60 } else if sleepTime < 0 {
61 sleepTime = time.Microsecond
62 }
63 if cache.ttl > 0 {
64 sleepTime = min(sleepTime, cache.ttl)
65 }
66
67 } else if cache.ttl > 0 {
68 sleepTime = cache.ttl
69 } else {
70 sleepTime = time.Hour
71 }
72
73 cache.expirationTime = time.Now().Add(sleepTime)
74 cache.mutex.Unlock()
75
76 timer := time.NewTimer(sleepTime)
77 select {
78 case <-timer.C:
79 timer.Stop()
80 cache.mutex.Lock()
81 if cache.priorityQueue.Len() == 0 {
82 cache.mutex.Unlock()
83 continue
84 }
85
86 // index will only be advanced if the current entry will not be evicted
87 i := 0
88 for item := cache.priorityQueue.items[i]; item.expired(); item = cache.priorityQueue.items[i] {
89
90 if cache.checkExpireCallback != nil {
91 if !cache.checkExpireCallback(item.key, item.data) {
92 item.touch()
93 cache.priorityQueue.update(item)
94 i++
95 if i == cache.priorityQueue.Len() {
96 break
97 }
98 continue
99 }
100 }
101
102 cache.priorityQueue.remove(item)
103 delete(cache.items, item.key)
104 if cache.expireCallback != nil {
105 go cache.expireCallback(item.key, item.data)
106 }
107 if cache.priorityQueue.Len() == 0 {
108 goto done
109 }
110 }
111 done:
112 cache.mutex.Unlock()
113
114 case <-cache.expirationNotification:
115 timer.Stop()
116 continue
117 }
118 }
119 }
120
121 func (cache *Cache) expirationNotificationTrigger(item *item) {
122 cache.mutex.Lock()
123 if cache.expirationTime.After(time.Now().Add(item.ttl)) {
124 cache.mutex.Unlock()
125 cache.expirationNotification <- true
126 } else {
127 cache.mutex.Unlock()
128 }
129 }
130
131 // Set is a thread-safe way to add new items to the map
132 func (cache *Cache) Set(key string, data interface{}) {
133 cache.SetWithTTL(key, data, ItemExpireWithGlobalTTL)
134 }
135
136 // SetWithTTL is a thread-safe way to add new items to the map with individual ttl
137 func (cache *Cache) SetWithTTL(key string, data interface{}, ttl time.Duration) {
138 item, exists := cache.getItem(key)
139 cache.mutex.Lock()
140
141 if exists {
142 item.data = data
143 item.ttl = ttl
144 } else {
145 item = newItem(key, data, ttl)
146 cache.items[key] = item
147 }
148
149 if item.ttl >= 0 && (item.ttl > 0 || cache.ttl > 0) {
150 if cache.ttl > 0 && item.ttl == 0 {
151 item.ttl = cache.ttl
152 }
153 item.touch()
154 }
155
156 if exists {
157 cache.priorityQueue.update(item)
158 } else {
159 cache.priorityQueue.push(item)
160 }
161
162 cache.mutex.Unlock()
163 if !exists && cache.newItemCallback != nil {
164 cache.newItemCallback(key, data)
165 }
166 cache.expirationNotification <- true
167 }
168
169 // Get is a thread-safe way to lookup items
170 // Every lookup, also touches the item, hence extending it's life
171 func (cache *Cache) Get(key string) (interface{}, bool) {
172 item, exists := cache.getItem(key)
173 if exists {
174 cache.mutex.RLock()
175 defer cache.mutex.RUnlock()
176 return item.data, true
177 }
178 return nil, false
179 }
180
181 func (cache *Cache) Remove(key string) bool {
182 cache.mutex.Lock()
183 object, exists := cache.items[key]
184 if !exists {
185 cache.mutex.Unlock()
186 return false
187 }
188 delete(cache.items, object.key)
189 cache.priorityQueue.remove(object)
190 cache.mutex.Unlock()
191
192 return true
193 }
194
195 // Count returns the number of items in the cache
196 func (cache *Cache) Count() int {
197 cache.mutex.RLock()
198 length := len(cache.items)
199 cache.mutex.RUnlock()
200 return length
201 }
202
203 func (cache *Cache) SetTTL(ttl time.Duration) {
204 cache.mutex.Lock()
205 cache.ttl = ttl
206 cache.mutex.Unlock()
207 cache.expirationNotification <- true
208 }
209
210 // SetExpirationCallback sets a callback that will be called when an item expires
211 func (cache *Cache) SetExpirationCallback(callback expireCallback) {
212 cache.expireCallback = callback
213 }
214
215 // SetCheckExpirationCallback sets a callback that will be called when an item is about to expire
216 // in order to allow external code to decide whether the item expires or remains for another TTL cycle
217 func (cache *Cache) SetCheckExpirationCallback(callback checkExpireCallback) {
218 cache.checkExpireCallback = callback
219 }
220
221 // SetNewItemCallback sets a callback that will be called when a new item is added to the cache
222 func (cache *Cache) SetNewItemCallback(callback expireCallback) {
223 cache.newItemCallback = callback
224 }
225
226 // SkipTtlExtensionOnHit allows the user to change the cache behaviour. When this flag is set to true it will
227 // no longer extend TTL of items when they are retrieved using Get, or when their expiration condition is evaluated
228 // using SetCheckExpirationCallback.
229 func (cache *Cache) SkipTtlExtensionOnHit(value bool) {
230 cache.skipTTLExtension = value
231 }
232
233 // Purge will remove all entries
234 func (cache *Cache) Purge() {
235 cache.mutex.Lock()
236 cache.items = make(map[string]*item)
237 cache.priorityQueue = newPriorityQueue()
238 cache.mutex.Unlock()
239 }
240
241 // NewCache is a helper to create instance of the Cache struct
242 func NewCache() *Cache {
243 cache := &Cache{
244 items: make(map[string]*item),
245 priorityQueue: newPriorityQueue(),
246 expirationNotification: make(chan bool),
247 expirationTime: time.Now(),
248 }
249 go cache.startExpirationProcessing()
250 return cache
251 }
252
253 func min(duration time.Duration, second time.Duration) time.Duration {
254 if duration < second {
255 return duration
256 }
257 return second
258 }
+372
-0
cache_test.go less more
0 package ttlcache
1
2 import (
3 "testing"
4 "time"
5
6 "fmt"
7 "log"
8 "sync"
9
10 "github.com/stretchr/testify/assert"
11 )
12
13 // test for Feature request in issue #12
14 //
15 func TestCache_SkipTtlExtensionOnHit(t *testing.T) {
16 cache := NewCache()
17 cache.SetTTL(time.Millisecond * 100)
18
19 cache.SkipTtlExtensionOnHit(false)
20 cache.Set("test", "!")
21 startTime := time.Now()
22 for now := time.Now(); now.Before(startTime.Add(time.Second * 3)); now = time.Now() {
23 if _, found := cache.Get("test"); !found {
24 t.Errorf("Item was not found, even though it should not expire.")
25 }
26
27 }
28
29 cache.SkipTtlExtensionOnHit(true)
30 cache.Set("expireTest", "!")
31 // will loop if item does not expire
32 for _, found := cache.Get("expireTest"); found; _, found = cache.Get("expireTest") {
33 }
34 }
35
36 func TestCache_SkipTtlExtensionOnHit_ForRacesAcrossGoroutines(t *testing.T) {
37 cache := NewCache()
38 cache.SetTTL(time.Minute * 1)
39 cache.SkipTtlExtensionOnHit(true)
40
41 var wgSet sync.WaitGroup
42 var wgGet sync.WaitGroup
43
44 n := 500
45 wgSet.Add(1)
46 go func() {
47 for i := 0; i < n; i++ {
48 wgSet.Add(1)
49
50 go func() {
51 cache.Set("test", false)
52 wgSet.Done()
53 }()
54 }
55 wgSet.Done()
56 }()
57 wgGet.Add(1)
58 go func() {
59 for i := 0; i < n; i++ {
60 wgGet.Add(1)
61
62 go func() {
63 cache.Get("test")
64 wgGet.Done()
65 }()
66 }
67 wgGet.Done()
68 }()
69
70 wgGet.Wait()
71 wgSet.Wait()
72 }
73
74 // test github issue #14
75 // Testing expiration callback would continue with the next item in list, even when it exceeds list lengths
76 func TestCache_SetCheckExpirationCallback(t *testing.T) {
77 iterated := 0
78 ch := make(chan struct{})
79
80 cacheAD := NewCache()
81 cacheAD.SetTTL(time.Millisecond)
82 cacheAD.SetCheckExpirationCallback(func(key string, value interface{}) bool {
83 v := value.(*int)
84 log.Printf("key=%v, value=%d\n", key, *v)
85 iterated++
86 if iterated == 1 {
87 // this is the breaking test case for issue #14
88 return false
89 }
90 ch <- struct{}{}
91 return true
92 })
93
94 i := 2
95 cacheAD.Set("a", &i)
96
97 <-ch
98 }
99
100 // test github issue #9
101 // Due to scheduling the expected TTL of the top entry can become negative (already expired)
102 // This is an issue because negative TTL at the item level was interpreted as 'use global TTL'
103 // Which is not right when we become negative due to scheduling.
104 // This test could use improvement as it's not requiring a lot of time to trigger.
105 func TestCache_SetExpirationCallback(t *testing.T) {
106
107 type A struct {
108 }
109
110 // Setup the TTL cache
111 cache := NewCache()
112 cache.SetTTL(time.Second * 1)
113 cache.SetExpirationCallback(func(key string, value interface{}) {
114 fmt.Printf("This key(%s) has expired\n", key)
115 })
116 for i := 0; i < 1024; i++ {
117 cache.Set(fmt.Sprintf("item_%d", i), A{})
118 time.Sleep(time.Millisecond * 10)
119 fmt.Printf("Cache size: %d\n", cache.Count())
120 }
121
122 if cache.Count() > 100 {
123 t.Fatal("Cache should empty entries >1 second old")
124 }
125 }
126
127 // test github issue #4
128 func TestRemovalAndCountDoesNotPanic(t *testing.T) {
129 cache := NewCache()
130 cache.Set("key", "value")
131 cache.Remove("key")
132 count := cache.Count()
133 t.Logf("cache has %d keys\n", count)
134 }
135
136 // test github issue #3
137 func TestRemovalWithTtlDoesNotPanic(t *testing.T) {
138 cache := NewCache()
139 cache.SetExpirationCallback(func(key string, value interface{}) {
140 t.Logf("This key(%s) has expired\n", key)
141 })
142
143 cache.SetWithTTL("keyWithTTL", "value", time.Duration(2*time.Second))
144 cache.Set("key", "value")
145 cache.Remove("key")
146
147 value, exists := cache.Get("keyWithTTL")
148 if exists {
149 t.Logf("got %s for keyWithTTL\n", value)
150 }
151 count := cache.Count()
152 t.Logf("cache has %d keys\n", count)
153
154 <-time.After(3 * time.Second)
155
156 value, exists = cache.Get("keyWithTTL")
157 if exists {
158 t.Logf("got %s for keyWithTTL\n", value)
159 } else {
160 t.Logf("keyWithTTL has gone")
161 }
162 count = cache.Count()
163 t.Logf("cache has %d keys\n", count)
164 }
165
166 func TestCacheIndividualExpirationBiggerThanGlobal(t *testing.T) {
167 cache := NewCache()
168 cache.SetTTL(time.Duration(50 * time.Millisecond))
169 cache.SetWithTTL("key", "value", time.Duration(100*time.Millisecond))
170 <-time.After(150 * time.Millisecond)
171 data, exists := cache.Get("key")
172 assert.Equal(t, exists, false, "Expected item to not exist")
173 assert.Nil(t, data, "Expected item to be nil")
174 }
175
176 func TestCacheGlobalExpirationByGlobal(t *testing.T) {
177 cache := NewCache()
178 cache.Set("key", "value")
179 <-time.After(50 * time.Millisecond)
180 data, exists := cache.Get("key")
181 assert.Equal(t, exists, true, "Expected item to exist in cache")
182 assert.Equal(t, data.(string), "value", "Expected item to have 'value' in value")
183
184 cache.SetTTL(time.Duration(50 * time.Millisecond))
185 data, exists = cache.Get("key")
186 assert.Equal(t, exists, true, "Expected item to exist in cache")
187 assert.Equal(t, data.(string), "value", "Expected item to have 'value' in value")
188
189 <-time.After(100 * time.Millisecond)
190 data, exists = cache.Get("key")
191 assert.Equal(t, exists, false, "Expected item to not exist")
192 assert.Nil(t, data, "Expected item to be nil")
193 }
194
195 func TestCacheGlobalExpiration(t *testing.T) {
196 cache := NewCache()
197 cache.SetTTL(time.Duration(100 * time.Millisecond))
198 cache.Set("key_1", "value")
199 cache.Set("key_2", "value")
200 <-time.After(200 * time.Millisecond)
201 assert.Equal(t, 0, cache.Count(), "Cache should be empty")
202 assert.Equal(t, 0, cache.priorityQueue.Len(), "PriorityQueue should be empty")
203 }
204
205 func TestCacheMixedExpirations(t *testing.T) {
206 cache := NewCache()
207 cache.SetExpirationCallback(func(key string, value interface{}) {
208 t.Logf("expired: %s", key)
209 })
210 cache.Set("key_1", "value")
211 cache.SetTTL(time.Duration(100 * time.Millisecond))
212 cache.Set("key_2", "value")
213 <-time.After(150 * time.Millisecond)
214 assert.Equal(t, 1, cache.Count(), "Cache should have only 1 item")
215 }
216
217 func TestCacheIndividualExpiration(t *testing.T) {
218 cache := NewCache()
219 cache.SetWithTTL("key", "value", time.Duration(100*time.Millisecond))
220 cache.SetWithTTL("key2", "value", time.Duration(100*time.Millisecond))
221 cache.SetWithTTL("key3", "value", time.Duration(100*time.Millisecond))
222 <-time.After(50 * time.Millisecond)
223 assert.Equal(t, cache.Count(), 3, "Should have 3 elements in cache")
224 <-time.After(160 * time.Millisecond)
225 assert.Equal(t, cache.Count(), 0, "Cache should be empty")
226
227 cache.SetWithTTL("key4", "value", time.Duration(50*time.Millisecond))
228 <-time.After(100 * time.Millisecond)
229 <-time.After(100 * time.Millisecond)
230 assert.Equal(t, 0, cache.Count(), "Cache should be empty")
231 }
232
233 func TestCacheGet(t *testing.T) {
234 cache := NewCache()
235 data, exists := cache.Get("hello")
236 assert.Equal(t, exists, false, "Expected empty cache to return no data")
237 assert.Nil(t, data, "Expected data to be empty")
238
239 cache.Set("hello", "world")
240 data, exists = cache.Get("hello")
241 assert.NotNil(t, data, "Expected data to be not nil")
242 assert.Equal(t, true, exists, "Expected data to exist")
243 assert.Equal(t, "world", (data.(string)), "Expected data content to be 'world'")
244 }
245
246 func TestCacheExpirationCallbackFunction(t *testing.T) {
247 expiredCount := 0
248 var lock sync.Mutex
249
250 cache := NewCache()
251 cache.SetTTL(time.Duration(500 * time.Millisecond))
252 cache.SetExpirationCallback(func(key string, value interface{}) {
253 lock.Lock()
254 defer lock.Unlock()
255 expiredCount = expiredCount + 1
256 })
257 cache.SetWithTTL("key", "value", time.Duration(1000*time.Millisecond))
258 cache.Set("key_2", "value")
259 <-time.After(1100 * time.Millisecond)
260
261 lock.Lock()
262 defer lock.Unlock()
263 assert.Equal(t, 2, expiredCount, "Expected 2 items to be expired")
264 }
265
266 // TestCacheCheckExpirationCallbackFunction should consider that the next entry in the queue
267 // needs to be considered for eviction even if the callback returns no eviction for the current item
268 func TestCacheCheckExpirationCallbackFunction(t *testing.T) {
269 expiredCount := 0
270 var lock sync.Mutex
271
272 cache := NewCache()
273 cache.SkipTtlExtensionOnHit(true)
274 cache.SetTTL(time.Duration(50 * time.Millisecond))
275 cache.SetCheckExpirationCallback(func(key string, value interface{}) bool {
276 if key == "key2" || key == "key4" {
277 return true
278 }
279 return false
280 })
281 cache.SetExpirationCallback(func(key string, value interface{}) {
282 lock.Lock()
283 expiredCount = expiredCount + 1
284 lock.Unlock()
285 })
286 cache.Set("key", "value")
287 cache.Set("key3", "value")
288 cache.Set("key2", "value")
289 cache.Set("key4", "value")
290
291 <-time.After(110 * time.Millisecond)
292 lock.Lock()
293 assert.Equal(t, 2, expiredCount, "Expected 2 items to be expired")
294 lock.Unlock()
295 }
296
297 func TestCacheNewItemCallbackFunction(t *testing.T) {
298 newItemCount := 0
299 cache := NewCache()
300 cache.SetTTL(time.Duration(50 * time.Millisecond))
301 cache.SetNewItemCallback(func(key string, value interface{}) {
302 newItemCount = newItemCount + 1
303 })
304 cache.Set("key", "value")
305 cache.Set("key2", "value")
306 cache.Set("key", "value")
307 <-time.After(110 * time.Millisecond)
308 assert.Equal(t, 2, newItemCount, "Expected only 2 new items")
309 }
310
311 func TestCacheRemove(t *testing.T) {
312 cache := NewCache()
313 cache.SetTTL(time.Duration(50 * time.Millisecond))
314 cache.SetWithTTL("key", "value", time.Duration(100*time.Millisecond))
315 cache.Set("key_2", "value")
316 <-time.After(70 * time.Millisecond)
317 removeKey := cache.Remove("key")
318 removeKey2 := cache.Remove("key_2")
319 assert.Equal(t, true, removeKey, "Expected 'key' to be removed from cache")
320 assert.Equal(t, false, removeKey2, "Expected 'key_2' to already be expired from cache")
321 }
322
323 func TestCacheSetWithTTLExistItem(t *testing.T) {
324 cache := NewCache()
325 cache.SetTTL(time.Duration(100 * time.Millisecond))
326 cache.SetWithTTL("key", "value", time.Duration(50*time.Millisecond))
327 <-time.After(30 * time.Millisecond)
328 cache.SetWithTTL("key", "value2", time.Duration(50*time.Millisecond))
329 data, exists := cache.Get("key")
330 assert.Equal(t, true, exists, "Expected 'key' to exist")
331 assert.Equal(t, "value2", data.(string), "Expected 'data' to have value 'value2'")
332 }
333
334 func TestCache_Purge(t *testing.T) {
335 cache := NewCache()
336 cache.SetTTL(time.Duration(100 * time.Millisecond))
337
338 for i := 0; i < 5; i++ {
339
340 cache.SetWithTTL("key", "value", time.Duration(50*time.Millisecond))
341 <-time.After(30 * time.Millisecond)
342 cache.SetWithTTL("key", "value2", time.Duration(50*time.Millisecond))
343 cache.Get("key")
344
345 cache.Purge()
346 assert.Equal(t, 0, cache.Count(), "Cache should be empty")
347 }
348
349 }
350
351 func BenchmarkCacheSetWithoutTTL(b *testing.B) {
352 cache := NewCache()
353 for n := 0; n < b.N; n++ {
354 cache.Set(string(n), "value")
355 }
356 }
357
358 func BenchmarkCacheSetWithGlobalTTL(b *testing.B) {
359 cache := NewCache()
360 cache.SetTTL(time.Duration(50 * time.Millisecond))
361 for n := 0; n < b.N; n++ {
362 cache.Set(string(n), "value")
363 }
364 }
365
366 func BenchmarkCacheSetWithTTL(b *testing.B) {
367 cache := NewCache()
368 for n := 0; n < b.N; n++ {
369 cache.SetWithTTL(string(n), "value", time.Duration(50*time.Millisecond))
370 }
371 }
+46
-0
item.go less more
0 package ttlcache
1
2 import (
3 "time"
4 )
5
6 const (
7 // ItemNotExpire Will avoid the item being expired by TTL, but can still be exired by callback etc.
8 ItemNotExpire time.Duration = -1
9 // ItemExpireWithGlobalTTL will use the global TTL when set.
10 ItemExpireWithGlobalTTL time.Duration = 0
11 )
12
13 func newItem(key string, data interface{}, ttl time.Duration) *item {
14 item := &item{
15 data: data,
16 ttl: ttl,
17 key: key,
18 }
19 // since nobody is aware yet of this item, it's safe to touch without lock here
20 item.touch()
21 return item
22 }
23
24 type item struct {
25 key string
26 data interface{}
27 ttl time.Duration
28 expireAt time.Time
29 queueIndex int
30 }
31
32 // Reset the item expiration time
33 func (item *item) touch() {
34 if item.ttl > 0 {
35 item.expireAt = time.Now().Add(item.ttl)
36 }
37 }
38
39 // Verify if the item is expired
40 func (item *item) expired() bool {
41 if item.ttl <= 0 {
42 return false
43 }
44 return item.expireAt.Before(time.Now())
45 }
+34
-0
item_test.go less more
0 package ttlcache
1
2 import (
3 "testing"
4 "time"
5
6 "github.com/stretchr/testify/assert"
7 )
8
9 func TestItemExpired(t *testing.T) {
10 item := newItem("key", "value", (time.Duration(100) * time.Millisecond))
11 assert.Equal(t, item.expired(), false, "Expected item to not be expired")
12 <-time.After(200 * time.Millisecond)
13 assert.Equal(t, item.expired(), true, "Expected item to be expired once time has passed")
14 }
15
16 func TestItemTouch(t *testing.T) {
17 item := newItem("key", "value", (time.Duration(100) * time.Millisecond))
18 oldExpireAt := item.expireAt
19 <-time.After(50 * time.Millisecond)
20 item.touch()
21 assert.NotEqual(t, oldExpireAt, item.expireAt, "Expected dates to be different")
22 <-time.After(150 * time.Millisecond)
23 assert.Equal(t, item.expired(), true, "Expected item to be expired")
24 item.touch()
25 <-time.After(50 * time.Millisecond)
26 assert.Equal(t, item.expired(), false, "Expected item to not be expired")
27 }
28
29 func TestItemWithoutExpiration(t *testing.T) {
30 item := newItem("key", "value", ItemNotExpire)
31 <-time.After(50 * time.Millisecond)
32 assert.Equal(t, item.expired(), false, "Expected item to not be expired")
33 }
+71
-0
priority_queue.go less more
0 package ttlcache
1
2 import (
3 "container/heap"
4 )
5
6 func newPriorityQueue() *priorityQueue {
7 queue := &priorityQueue{}
8 heap.Init(queue)
9 return queue
10 }
11
12 type priorityQueue struct {
13 items []*item
14 }
15
16 func (pq *priorityQueue) update(item *item) {
17 heap.Fix(pq, item.queueIndex)
18 }
19
20 func (pq *priorityQueue) push(item *item) {
21 heap.Push(pq, item)
22 }
23
24 func (pq *priorityQueue) pop() *item {
25 if pq.Len() == 0 {
26 return nil
27 }
28 return heap.Pop(pq).(*item)
29 }
30
31 func (pq *priorityQueue) remove(item *item) {
32 heap.Remove(pq, item.queueIndex)
33 }
34
35 func (pq priorityQueue) Len() int {
36 length := len(pq.items)
37 return length
38 }
39
40 // Less will consider items with time.Time default value (epoch start) as more than set items.
41 func (pq priorityQueue) Less(i, j int) bool {
42 if pq.items[i].expireAt.IsZero() {
43 return false
44 }
45 if pq.items[j].expireAt.IsZero() {
46 return true
47 }
48 return pq.items[i].expireAt.Before(pq.items[j].expireAt)
49 }
50
51 func (pq priorityQueue) Swap(i, j int) {
52 pq.items[i], pq.items[j] = pq.items[j], pq.items[i]
53 pq.items[i].queueIndex = i
54 pq.items[j].queueIndex = j
55 }
56
57 func (pq *priorityQueue) Push(x interface{}) {
58 item := x.(*item)
59 item.queueIndex = len(pq.items)
60 pq.items = append(pq.items, item)
61 }
62
63 func (pq *priorityQueue) Pop() interface{} {
64 old := pq.items
65 n := len(old)
66 item := old[n-1]
67 item.queueIndex = -1
68 pq.items = old[0 : n-1]
69 return item
70 }
+89
-0
priority_queue_test.go less more
0 package ttlcache
1
2 import (
3 "fmt"
4 "testing"
5 "time"
6
7 "github.com/stretchr/testify/assert"
8 )
9
10 func TestPriorityQueuePush(t *testing.T) {
11 queue := newPriorityQueue()
12 for i := 0; i < 10; i++ {
13 queue.push(newItem(fmt.Sprintf("key_%d", i), "data", -1))
14 }
15 assert.Equal(t, queue.Len(), 10, "Expected queue to have 10 elements")
16 }
17
18 func TestPriorityQueuePop(t *testing.T) {
19 queue := newPriorityQueue()
20 for i := 0; i < 10; i++ {
21 queue.push(newItem(fmt.Sprintf("key_%d", i), "data", -1))
22 }
23 for i := 0; i < 5; i++ {
24 item := queue.pop()
25 assert.Equal(t, fmt.Sprintf("%T", item), "*ttlcache.item", "Expected 'item' to be a '*ttlcache.item'")
26 }
27 assert.Equal(t, queue.Len(), 5, "Expected queue to have 5 elements")
28 for i := 0; i < 5; i++ {
29 item := queue.pop()
30 assert.Equal(t, fmt.Sprintf("%T", item), "*ttlcache.item", "Expected 'item' to be a '*ttlcache.item'")
31 }
32 assert.Equal(t, queue.Len(), 0, "Expected queue to have 0 elements")
33
34 item := queue.pop()
35 assert.Nil(t, item, "*ttlcache.item", "Expected 'item' to be nil")
36 }
37
38 func TestPriorityQueueCheckOrder(t *testing.T) {
39 queue := newPriorityQueue()
40 for i := 10; i > 0; i-- {
41 queue.push(newItem(fmt.Sprintf("key_%d", i), "data", time.Duration(i)*time.Second))
42 }
43 for i := 1; i <= 10; i++ {
44 item := queue.pop()
45 assert.Equal(t, item.key, fmt.Sprintf("key_%d", i), "error")
46 }
47 }
48
49 func TestPriorityQueueRemove(t *testing.T) {
50 queue := newPriorityQueue()
51 items := make(map[string]*item)
52 var itemRemove *item
53 for i := 0; i < 5; i++ {
54 key := fmt.Sprintf("key_%d", i)
55 items[key] = newItem(key, "data", time.Duration(i)*time.Second)
56 queue.push(items[key])
57
58 if i == 2 {
59 itemRemove = items[key]
60 }
61 }
62 assert.Equal(t, queue.Len(), 5, "Expected queue to have 5 elements")
63 queue.remove(itemRemove)
64 assert.Equal(t, queue.Len(), 4, "Expected queue to have 4 elements")
65
66 for {
67 item := queue.pop()
68 if item == nil {
69 break
70 }
71 assert.NotEqual(t, itemRemove.key, item.key, "This element was not supose to be in the queue")
72 }
73
74 assert.Equal(t, queue.Len(), 0, "The queue is supose to be with 0 items")
75 }
76
77 func TestPriorityQueueUpdate(t *testing.T) {
78 queue := newPriorityQueue()
79 item := newItem("key", "data", 1*time.Second)
80 queue.push(item)
81 assert.Equal(t, queue.Len(), 1, "The queue is supose to be with 1 item")
82
83 item.key = "newKey"
84 queue.update(item)
85 newItem := queue.pop()
86 assert.Equal(t, newItem.key, "newKey", "The item key didn't change")
87 assert.Equal(t, queue.Len(), 0, "The queue is supose to be with 0 items")
88 }