3 // A linked list to keep track of recently-used-ness
4 const Yallist = require('yallist')
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')
17 const naiveLength = () => 1
19 // lruList is a yallist where the head is the youngest
20 // item, and the tail is the oldest. the list contains the Hit
21 // objects as the entries.
22 // Each Hit object has a reference to its Yallist.Node. This
25 // cache is a Map (or PseudoMap) that matches the keys to
26 // the Yallist.Node object.
28 constructor (options) {
29 if (typeof options === 'number')
30 options = { max: options }
35 if (options.max && (typeof options.max !== 'number' || options.max < 0))
36 throw new TypeError('max must be a non-negative number')
37 // Kind of weird to have a default max of Infinity, but oh well.
38 const max = this[MAX] = options.max || Infinity
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
52 // resize the cache when the max changes.
54 if (typeof mL !== 'number' || mL < 0)
55 throw new TypeError('max must be a non-negative number')
57 this[MAX] = mL || Infinity
64 set allowStale (allowStale) {
65 this[ALLOW_STALE] = !!allowStale
68 return this[ALLOW_STALE]
72 if (typeof mA !== 'number')
73 throw new TypeError('maxAge must be a non-negative number')
82 // resize the cache when the lengthCalculator changes.
83 set lengthCalculator (lC) {
84 if (typeof lC !== 'function')
87 if (lC !== this[LENGTH_CALCULATOR]) {
88 this[LENGTH_CALCULATOR] = lC
90 this[LRU_LIST].forEach(hit => {
91 hit.length = this[LENGTH_CALCULATOR](hit.value, hit.key)
92 this[LENGTH] += hit.length
97 get lengthCalculator () { return this[LENGTH_CALCULATOR] }
99 get length () { return this[LENGTH] }
100 get itemCount () { return this[LRU_LIST].length }
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)
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)
121 return this[LRU_LIST].toArray().map(k => k.key)
125 return this[LRU_LIST].toArray().map(k => k.value)
131 this[LRU_LIST].length) {
132 this[LRU_LIST].forEach(hit => this[DISPOSE](hit.key, hit.value))
135 this[CACHE] = new Map() // hash of items by key
136 this[LRU_LIST] = new Yallist() // list of items in order of use recency
137 this[LENGTH] = 0 // length of items in the list
141 return this[LRU_LIST].map(hit =>
142 isStale(this, hit) ? false : {
145 e: hit.now + (hit.maxAge || 0)
146 }).toArray().filter(h => h)
150 return this[LRU_LIST]
153 set (key, value, maxAge) {
154 maxAge = maxAge || this[MAX_AGE]
156 if (maxAge && typeof maxAge !== 'number')
157 throw new TypeError('maxAge must be a number')
159 const now = maxAge ? Date.now() : 0
160 const len = this[LENGTH_CALCULATOR](value, key)
162 if (this[CACHE].has(key)) {
163 if (len > this[MAX]) {
164 del(this, this[CACHE].get(key))
168 const node = this[CACHE].get(key)
169 const item = node.value
171 // dispose of the old one before overwriting
172 // split out into 2 ifs for better coverage tracking
174 if (!this[NO_DISPOSE_ON_SET])
175 this[DISPOSE](key, item.value)
181 this[LENGTH] += len - item.length
188 const hit = new Entry(key, value, len, now, maxAge)
190 // oversized objects fall out of cache automatically.
191 if (hit.length > this[MAX]) {
193 this[DISPOSE](key, value)
198 this[LENGTH] += hit.length
199 this[LRU_LIST].unshift(hit)
200 this[CACHE].set(key, this[LRU_LIST].head)
206 if (!this[CACHE].has(key)) return false
207 const hit = this[CACHE].get(key).value
208 return !isStale(this, hit)
212 return get(this, key, true)
216 return get(this, key, false)
220 const node = this[LRU_LIST].tail
229 del(this, this[CACHE].get(key))
236 const now = Date.now()
237 // A previous serialized cache has the most recent items first
238 for (let l = arr.length - 1; l >= 0; l--) {
240 const expiresAt = hit.e || 0
242 // the item was created without expiration in a non aged cache
243 this.set(hit.k, hit.v)
245 const maxAge = expiresAt - now
246 // dont add already expired items
248 this.set(hit.k, hit.v, maxAge)
255 this[CACHE].forEach((value, key) => get(this, key, false))
259 const get = (self, key, doUse) => {
260 const node = self[CACHE].get(key)
262 const hit = node.value
263 if (isStale(self, hit)) {
265 if (!self[ALLOW_STALE])
269 if (self[UPDATE_AGE_ON_GET])
270 node.value.now = Date.now()
271 self[LRU_LIST].unshiftNode(node)
278 const isStale = (self, hit) => {
279 if (!hit || (!hit.maxAge && !self[MAX_AGE]))
282 const diff = Date.now() - hit.now
283 return hit.maxAge ? diff > hit.maxAge
284 : self[MAX_AGE] && (diff > self[MAX_AGE])
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 // We know that we're about to delete this one, and also
292 // what the next least recently used key will be, so just
293 // go ahead and set it now.
294 const prev = walker.prev
301 const del = (self, node) => {
303 const hit = node.value
305 self[DISPOSE](hit.key, hit.value)
307 self[LENGTH] -= hit.length
308 self[CACHE].delete(hit.key)
309 self[LRU_LIST].removeNode(node)
314 constructor (key, value, length, now, maxAge) {
319 this.maxAge = maxAge || 0
323 const forEachStep = (self, fn, node, thisp) => {
325 if (isStale(self, hit)) {
327 if (!self[ALLOW_STALE])
331 fn.call(thisp, hit.value, hit.key, self)
334 module.exports = LRUCache