-
Notifications
You must be signed in to change notification settings - Fork 1
Expand file tree
/
Copy pathlrucache.go
More file actions
179 lines (164 loc) · 3.92 KB
/
lrucache.go
File metadata and controls
179 lines (164 loc) · 3.92 KB
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
package lrucache
import (
"container/list"
"errors"
"sync"
"time"
)
// EvictCallback is used to get a callback when a cache entry is evicted
type EvictCallback func(key interface{}, value interface{})
// LruCache implements a thread safe fixed size Expire LRU cache
type LruCache struct {
size int
evictList *list.List
cache map[interface{}]*list.Element
ttl time.Duration
onEvict EvictCallback
lock sync.RWMutex
}
// entry is used to hold a value in the evictList
type entry struct {
key interface{}
value interface{}
//if tll is nil, entry is not expire auto
ttl *time.Time
}
func (e *entry) IsExpired() bool {
if e.ttl == nil {
return false
}
return time.Now().After(*e.ttl)
}
// NewLRUCache creates an expiring cache with the given size
func NewLRUCache(maxSize int, ttl time.Duration, onEvict EvictCallback) (*LruCache, error) {
if maxSize <= 0 {
return nil, errors.New("Must provide a positive size to cache")
}
c := &LruCache{
size: maxSize,
evictList: list.New(),
cache: make(map[interface{}]*list.Element),
ttl: ttl,
onEvict: onEvict,
}
return c, nil
}
// Get a key's value from the cache.
func (c *LruCache) Get(key interface{}) (value interface{}, ok bool) {
c.lock.Lock()
defer c.lock.Unlock()
//exsit
if ent, ok := c.cache[key]; ok {
//expired
if ent.Value.(*entry).IsExpired() {
c.removeElement(ent)
return nil, false
}
//not expired,movetofront
c.evictList.MoveToFront(ent)
return ent.Value.(*entry).value, true
}
return nil, false
}
// removeElement is used to remove a given list element from the cache
func (c *LruCache) removeElement(e *list.Element) {
c.evictList.Remove(e)
kv := e.Value.(*entry)
delete(c.cache, kv.key)
if c.onEvict != nil {
c.onEvict(kv.key, kv.value)
}
}
// Add adds the value to the cache at key with the specified maximum duration.
func (c *LruCache) Put(key interface{}, value interface{}, ttl time.Duration) bool {
c.lock.Lock()
defer c.lock.Unlock()
var ex *time.Time = nil
if ttl > 0 {
expire := time.Now().Add(ttl)
ex = &expire
} else if c.ttl > 0 {
expire := time.Now().Add(c.ttl)
ex = &expire
}
//Check for existing item
if ent, ok := c.cache[key]; ok {
c.evictList.MoveToFront(ent)
ent.Value.(*entry).value = value
ent.Value.(*entry).ttl = ex
return false
}
// Add new item
ent := &entry{
key: key,
value: value,
ttl: ex,
}
entry := c.evictList.PushFront(ent)
c.cache[key] = entry
evict := c.evictList.Len() > c.size
// Verify size not exceeded
if evict {
c.removeOldest()
}
return evict
}
// removeOldest removes the oldest item from the cache
func (c *LruCache) removeOldest() {
ent := c.evictList.Back()
if ent != nil {
c.removeElement(ent)
}
}
// Len returns the number of items in the cache.
func (c *LruCache) Len() int {
c.lock.RLock()
defer c.lock.RUnlock()
return c.evictList.Len()
}
// Remove removes the provided key from the cache.
func (c *LruCache) Remove(key interface{}) bool {
c.lock.Lock()
defer c.lock.Unlock()
if ent, ok := c.cache[key]; ok {
c.removeElement(ent)
return true
}
return false
}
// Contains Check if a key exsists in cache without updating the recent-ness.
func (c *LruCache) Contains(key interface{}) (ok bool) {
c.lock.RLock()
defer c.lock.RUnlock()
if ent, ok := c.cache[key]; ok {
if ent.Value.(*entry).IsExpired() {
return false
}
return ok
}
return false
}
// Keys return all the keys in cache, from oldest to newest
func (c *LruCache) Keys() []interface{} {
c.lock.RLock()
defer c.lock.RUnlock()
keys := make([]interface{}, len(c.cache))
i := 0
for ent := c.evictList.Back(); ent != nil; ent = ent.Prev() {
keys[i] = ent.Value.(*entry).key
i++
}
return keys
}
// Clear remove all the keys in cache
func (c *LruCache) Clear() {
c.lock.Lock()
defer c.lock.Unlock()
for k, v := range c.cache {
if c.onEvict != nil {
c.onEvict(k, v.Value.(*entry).value)
}
delete(c.cache, k)
}
c.evictList.Init()
}