1 | 'use strict'
|
2 |
|
3 |
|
4 | const Yallist = require('yallist')
|
5 |
|
6 | const MAX = Symbol('max')
|
7 | const LENGTH = Symbol('length')
|
8 | const LENGTH_CALCULATOR = Symbol('lengthCalculator')
|
9 | const ALLOW_STALE = Symbol('allowStale')
|
10 | const MAX_AGE = Symbol('maxAge')
|
11 | const DISPOSE = Symbol('dispose')
|
12 | const NO_DISPOSE_ON_SET = Symbol('noDisposeOnSet')
|
13 | const LRU_LIST = Symbol('lruList')
|
14 | const CACHE = Symbol('cache')
|
15 | const UPDATE_AGE_ON_GET = Symbol('updateAgeOnGet')
|
16 |
|
17 | const naiveLength = () => 1
|
18 |
|
19 |
|
20 |
|
21 |
|
22 |
|
23 |
|
24 |
|
25 |
|
26 |
|
27 | class LRUCache {
|
28 | constructor (options) {
|
29 | if (typeof options === 'number')
|
30 | options = { max: options }
|
31 |
|
32 | if (!options)
|
33 | options = {}
|
34 |
|
35 | if (options.max && (typeof options.max !== 'number' || options.max < 0))
|
36 | throw new TypeError('max must be a non-negative number')
|
37 |
|
38 | const max = this[MAX] = options.max || Infinity
|
39 |
|
40 | const lc = options.length || naiveLength
|
41 | this[LENGTH_CALCULATOR] = (typeof lc !== 'function') ? naiveLength : lc
|
42 | this[ALLOW_STALE] = options.stale || false
|
43 | if (options.maxAge && typeof options.maxAge !== 'number')
|
44 | throw new TypeError('maxAge must be a number')
|
45 | this[MAX_AGE] = options.maxAge || 0
|
46 | this[DISPOSE] = options.dispose
|
47 | this[NO_DISPOSE_ON_SET] = options.noDisposeOnSet || false
|
48 | this[UPDATE_AGE_ON_GET] = options.updateAgeOnGet || false
|
49 | this.reset()
|
50 | }
|
51 |
|
52 |
|
53 | set max (mL) {
|
54 | if (typeof mL !== 'number' || mL < 0)
|
55 | throw new TypeError('max must be a non-negative number')
|
56 |
|
57 | this[MAX] = mL || Infinity
|
58 | trim(this)
|
59 | }
|
60 | get max () {
|
61 | return this[MAX]
|
62 | }
|
63 |
|
64 | set allowStale (allowStale) {
|
65 | this[ALLOW_STALE] = !!allowStale
|
66 | }
|
67 | get allowStale () {
|
68 | return this[ALLOW_STALE]
|
69 | }
|
70 |
|
71 | set maxAge (mA) {
|
72 | if (typeof mA !== 'number')
|
73 | throw new TypeError('maxAge must be a non-negative number')
|
74 |
|
75 | this[MAX_AGE] = mA
|
76 | trim(this)
|
77 | }
|
78 | get maxAge () {
|
79 | return this[MAX_AGE]
|
80 | }
|
81 |
|
82 |
|
83 | set lengthCalculator (lC) {
|
84 | if (typeof lC !== 'function')
|
85 | lC = naiveLength
|
86 |
|
87 | if (lC !== this[LENGTH_CALCULATOR]) {
|
88 | this[LENGTH_CALCULATOR] = lC
|
89 | this[LENGTH] = 0
|
90 | this[LRU_LIST].forEach(hit => {
|
91 | hit.length = this[LENGTH_CALCULATOR](hit.value, hit.key)
|
92 | this[LENGTH] += hit.length
|
93 | })
|
94 | }
|
95 | trim(this)
|
96 | }
|
97 | get lengthCalculator () { return this[LENGTH_CALCULATOR] }
|
98 |
|
99 | get length () { return this[LENGTH] }
|
100 | get itemCount () { return this[LRU_LIST].length }
|
101 |
|
102 | rforEach (fn, thisp) {
|
103 | thisp = thisp || this
|
104 | for (let walker = this[LRU_LIST].tail; walker !== null;) {
|
105 | const prev = walker.prev
|
106 | forEachStep(this, fn, walker, thisp)
|
107 | walker = prev
|
108 | }
|
109 | }
|
110 |
|
111 | forEach (fn, thisp) {
|
112 | thisp = thisp || this
|
113 | for (let walker = this[LRU_LIST].head; walker !== null;) {
|
114 | const next = walker.next
|
115 | forEachStep(this, fn, walker, thisp)
|
116 | walker = next
|
117 | }
|
118 | }
|
119 |
|
120 | keys () {
|
121 | return this[LRU_LIST].toArray().map(k => k.key)
|
122 | }
|
123 |
|
124 | values () {
|
125 | return this[LRU_LIST].toArray().map(k => k.value)
|
126 | }
|
127 |
|
128 | reset () {
|
129 | if (this[DISPOSE] &&
|
130 | this[LRU_LIST] &&
|
131 | this[LRU_LIST].length) {
|
132 | this[LRU_LIST].forEach(hit => this[DISPOSE](hit.key, hit.value))
|
133 | }
|
134 |
|
135 | this[CACHE] = new Map()
|
136 | this[LRU_LIST] = new Yallist()
|
137 | this[LENGTH] = 0
|
138 | }
|
139 |
|
140 | dump () {
|
141 | return this[LRU_LIST].map(hit =>
|
142 | isStale(this, hit) ? false : {
|
143 | k: hit.key,
|
144 | v: hit.value,
|
145 | e: hit.now + (hit.maxAge || 0)
|
146 | }).toArray().filter(h => h)
|
147 | }
|
148 |
|
149 | dumpLru () {
|
150 | return this[LRU_LIST]
|
151 | }
|
152 |
|
153 | set (key, value, maxAge) {
|
154 | maxAge = maxAge || this[MAX_AGE]
|
155 |
|
156 | if (maxAge && typeof maxAge !== 'number')
|
157 | throw new TypeError('maxAge must be a number')
|
158 |
|
159 | const now = maxAge ? Date.now() : 0
|
160 | const len = this[LENGTH_CALCULATOR](value, key)
|
161 |
|
162 | if (this[CACHE].has(key)) {
|
163 | if (len > this[MAX]) {
|
164 | del(this, this[CACHE].get(key))
|
165 | return false
|
166 | }
|
167 |
|
168 | const node = this[CACHE].get(key)
|
169 | const item = node.value
|
170 |
|
171 |
|
172 |
|
173 | if (this[DISPOSE]) {
|
174 | if (!this[NO_DISPOSE_ON_SET])
|
175 | this[DISPOSE](key, item.value)
|
176 | }
|
177 |
|
178 | item.now = now
|
179 | item.maxAge = maxAge
|
180 | item.value = value
|
181 | this[LENGTH] += len - item.length
|
182 | item.length = len
|
183 | this.get(key)
|
184 | trim(this)
|
185 | return true
|
186 | }
|
187 |
|
188 | const hit = new Entry(key, value, len, now, maxAge)
|
189 |
|
190 |
|
191 | if (hit.length > this[MAX]) {
|
192 | if (this[DISPOSE])
|
193 | this[DISPOSE](key, value)
|
194 |
|
195 | return false
|
196 | }
|
197 |
|
198 | this[LENGTH] += hit.length
|
199 | this[LRU_LIST].unshift(hit)
|
200 | this[CACHE].set(key, this[LRU_LIST].head)
|
201 | trim(this)
|
202 | return true
|
203 | }
|
204 |
|
205 | has (key) {
|
206 | if (!this[CACHE].has(key)) return false
|
207 | const hit = this[CACHE].get(key).value
|
208 | return !isStale(this, hit)
|
209 | }
|
210 |
|
211 | get (key) {
|
212 | return get(this, key, true)
|
213 | }
|
214 |
|
215 | peek (key) {
|
216 | return get(this, key, false)
|
217 | }
|
218 |
|
219 | pop () {
|
220 | const node = this[LRU_LIST].tail
|
221 | if (!node)
|
222 | return null
|
223 |
|
224 | del(this, node)
|
225 | return node.value
|
226 | }
|
227 |
|
228 | del (key) {
|
229 | del(this, this[CACHE].get(key))
|
230 | }
|
231 |
|
232 | load (arr) {
|
233 |
|
234 | this.reset()
|
235 |
|
236 | const now = Date.now()
|
237 |
|
238 | for (let l = arr.length - 1; l >= 0; l--) {
|
239 | const hit = arr[l]
|
240 | const expiresAt = hit.e || 0
|
241 | if (expiresAt === 0)
|
242 |
|
243 | this.set(hit.k, hit.v)
|
244 | else {
|
245 | const maxAge = expiresAt - now
|
246 |
|
247 | if (maxAge > 0) {
|
248 | this.set(hit.k, hit.v, maxAge)
|
249 | }
|
250 | }
|
251 | }
|
252 | }
|
253 |
|
254 | prune () {
|
255 | this[CACHE].forEach((value, key) => get(this, key, false))
|
256 | }
|
257 | }
|
258 |
|
259 | const get = (self, key, doUse) => {
|
260 | const node = self[CACHE].get(key)
|
261 | if (node) {
|
262 | const hit = node.value
|
263 | if (isStale(self, hit)) {
|
264 | del(self, node)
|
265 | if (!self[ALLOW_STALE])
|
266 | return undefined
|
267 | } else {
|
268 | if (doUse) {
|
269 | if (self[UPDATE_AGE_ON_GET])
|
270 | node.value.now = Date.now()
|
271 | self[LRU_LIST].unshiftNode(node)
|
272 | }
|
273 | }
|
274 | return hit.value
|
275 | }
|
276 | }
|
277 |
|
278 | const isStale = (self, hit) => {
|
279 | if (!hit || (!hit.maxAge && !self[MAX_AGE]))
|
280 | return false
|
281 |
|
282 | const diff = Date.now() - hit.now
|
283 | return hit.maxAge ? diff > hit.maxAge
|
284 | : self[MAX_AGE] && (diff > self[MAX_AGE])
|
285 | }
|
286 |
|
287 | const trim = self => {
|
288 | if (self[LENGTH] > self[MAX]) {
|
289 | for (let walker = self[LRU_LIST].tail;
|
290 | self[LENGTH] > self[MAX] && walker !== null;) {
|
291 |
|
292 |
|
293 |
|
294 | const prev = walker.prev
|
295 | del(self, walker)
|
296 | walker = prev
|
297 | }
|
298 | }
|
299 | }
|
300 |
|
301 | const del = (self, node) => {
|
302 | if (node) {
|
303 | const hit = node.value
|
304 | if (self[DISPOSE])
|
305 | self[DISPOSE](hit.key, hit.value)
|
306 |
|
307 | self[LENGTH] -= hit.length
|
308 | self[CACHE].delete(hit.key)
|
309 | self[LRU_LIST].removeNode(node)
|
310 | }
|
311 | }
|
312 |
|
313 | class Entry {
|
314 | constructor (key, value, length, now, maxAge) {
|
315 | this.key = key
|
316 | this.value = value
|
317 | this.length = length
|
318 | this.now = now
|
319 | this.maxAge = maxAge || 0
|
320 | }
|
321 | }
|
322 |
|
323 | const forEachStep = (self, fn, node, thisp) => {
|
324 | let hit = node.value
|
325 | if (isStale(self, hit)) {
|
326 | del(self, node)
|
327 | if (!self[ALLOW_STALE])
|
328 | hit = undefined
|
329 | }
|
330 | if (hit)
|
331 | fn.call(thisp, hit.value, hit.key, self)
|
332 | }
|
333 |
|
334 | module.exports = LRUCache
|