-
Notifications
You must be signed in to change notification settings - Fork 0
/
lru-cache.go
110 lines (96 loc) · 2.17 KB
/
lru-cache.go
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
package cache
import (
"container/list"
"runtime"
"sync"
"time"
)
type LRUCache struct {
mu sync.RWMutex
maxItems int
stopChan chan struct{}
expireTime time.Duration
cleanTime time.Duration
cache map[string]*list.Element
lruList *list.List
}
type CacheItem struct {
key string
value interface{}
expireAt time.Time
}
func (c *CacheItem) isExpired() bool {
return c.expireAt.Before(time.Now())
}
func NewLRUCache(maxItems int, expireTime time.Duration, cleanTime time.Duration) *LRUCache {
c := &LRUCache{
cache: make(map[string]*list.Element),
lruList: list.New(),
maxItems: maxItems,
expireTime: expireTime,
cleanTime: cleanTime,
stopChan: make(chan struct{}),
}
go c.startGC()
runtime.SetFinalizer(c, func() { c.stopChan <- struct{}{} })
return c
}
func (c *LRUCache) Get(key string) (interface{}, bool) {
c.mu.RLock()
if ele, hit := c.cache[key]; hit && !ele.Value.(*CacheItem).isExpired() {
c.mu.RUnlock()
c.mu.Lock()
c.lruList.MoveToFront(ele)
c.mu.Unlock()
return ele.Value.(*CacheItem).value, true
}
c.mu.RUnlock()
return nil, false
}
func (c *LRUCache) Set(key string, value interface{}) {
c.mu.Lock()
defer c.mu.Unlock()
if ele, hit := c.cache[key]; hit {
c.lruList.MoveToFront(ele)
ele.Value.(*CacheItem).expireAt = time.Now().Add(c.expireTime)
ele.Value.(*CacheItem).value = value
return
}
ele := c.lruList.PushFront(&CacheItem{key: key, value: value, expireAt: time.Now().Add(c.expireTime)})
c.cache[key] = ele
if c.lruList.Len() > c.maxItems {
// Remove least recently used item
ele := c.lruList.Back()
if ele != nil {
c.lruList.Remove(ele)
delete(c.cache, ele.Value.(*CacheItem).key)
}
}
}
func (c *LRUCache) Delete(key string) {
c.mu.Lock()
defer c.mu.Unlock()
if ele, hit := c.cache[key]; hit {
c.lruList.Remove(ele)
delete(c.cache, key)
}
}
func (c *LRUCache) startGC() {
ticker := time.NewTicker(c.cleanTime)
for {
select {
case <-c.stopChan:
ticker.Stop()
return
case <-ticker.C:
c.mu.Lock()
for key, ele := range c.cache {
if ele.Value.(*CacheItem).isExpired() {
c.lruList.Remove(ele)
delete(c.cache, key)
}
}
c.mu.Unlock()
}
}
}