/
lru.go
188 lines (138 loc) · 3.71 KB
/
lru.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
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
180
181
182
183
184
185
186
187
188
// Copyright © 2016 Abcum Ltd
//
// Licensed under the Apache License, Version 2.0 (the "License");
// you may not use this file except in compliance with the License.
// You may obtain a copy of the License at
//
// http://www.apache.org/licenses/LICENSE-2.0
//
// Unless required by applicable law or agreed to in writing, software
// distributed under the License is distributed on an "AS IS" BASIS,
// WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
// See the License for the specific language governing permissions and
// limitations under the License.
package lru
import (
"bytes"
"container/list"
"errors"
"sync"
)
type elem struct {
sze int
key string
val []byte
}
// Cache represents an in-memory Least Recently Used cache that is
// safe to use for concurrent writes from multiple goroutines.
type Cache struct {
size int
lock sync.Mutex
bytes int
queue *list.List
items map[string]*list.Element
}
// New creates and returns a LRU (Least Recently Used) cache with a
// maximum size specified in bytes. The cache size must be a number
// greater than 0, otherwise en error will be returned.
func New(size int) (*Cache, error) {
if size <= 0 {
return nil, errors.New("Size must be a positive number")
}
c := &Cache{
size: size,
queue: list.New(),
items: make(map[string]*list.Element),
}
return c, nil
}
// Clr removes and clears every item from the cache, and resets its size.
func (c *Cache) Clr() {
c.lock.Lock()
defer c.lock.Unlock()
c.clr()
}
// Has checks to see if the key exists in the cache, returning a true
// if it exists and false if not.
func (c *Cache) Has(key string) bool {
c.lock.Lock()
defer c.lock.Unlock()
return c.has(key)
}
// Get looks up a key's value in the cache. If the value exists in the
// cache then the value is returned, otherwise a nil byte slice is
// returned.
func (c *Cache) Get(key string) []byte {
c.lock.Lock()
defer c.lock.Unlock()
return c.get(key)
}
// Del deletes a key from the cache. If the value existed in the cache
// then the value is returned, otherwise a nil byte slice is returned.
func (c *Cache) Del(key string) []byte {
c.lock.Lock()
defer c.lock.Unlock()
return c.del(key)
}
// Put puts a new item into the cache using the specified key. If the
// size of the cache will rise above the allowed cache size, the oldest
// items will be removed.
func (c *Cache) Put(key string, val []byte) []byte {
c.lock.Lock()
defer c.lock.Unlock()
return c.put(key, val)
}
// ---------------------------------------------------------------------------
func (c *Cache) clr() {
for k := range c.items {
delete(c.items, k)
}
c.queue.Init()
c.bytes = 0
}
func (c *Cache) has(key string) bool {
_, ok := c.items[key]
return ok
}
func (c *Cache) get(key string) []byte {
if item, ok := c.items[key]; ok {
c.queue.MoveToFront(item)
return item.Value.(*elem).val
}
return nil
}
func (c *Cache) del(key string) []byte {
if item, ok := c.items[key]; ok {
c.bytes -= item.Value.(*elem).sze
delete(c.items, key)
c.queue.Remove(item)
return item.Value.(*elem).val
}
return nil
}
func (c *Cache) put(key string, val []byte) []byte {
// Get the data length
sze := len(val)
// Check if value is same
if bytes.Equal(c.get(key), val) {
return val
}
// Delete the item if it exists
ret := c.del(key)
// The item is too big for caching
if sze > c.size {
return ret
}
// Free up some data from the cache
for c.queue.Len() > 0 && sze+c.bytes > c.size {
if item := c.queue.Back(); item != nil {
c.del(item.Value.(*elem).key)
}
}
// Insert the element into the cache
elem := &elem{sze: sze, key: key, val: val}
item := c.queue.PushFront(elem)
c.items[key] = item
c.bytes += sze
return ret
}