1  'use strict'
  2  
  3  // A linked list to keep track of recently-used-ness
  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  // 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
 23  // never changes.
 24  //
 25  // cache is a Map (or PseudoMap) that matches the keys to
 26  // the Yallist.Node object.
 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      // Kind of weird to have a default max of Infinity, but oh well.
 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    // resize the cache when the max changes.
 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    // resize the cache when the lengthCalculator changes.
 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() // 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
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        // dispose of the old one before overwriting
172        // split out into 2 ifs for better coverage tracking
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      // oversized objects fall out of cache automatically.
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      // reset the cache
234      this.reset()
235  
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--) {
239        const hit = arr[l]
240        const expiresAt = hit.e || 0
241        if (expiresAt === 0)
242          // the item was created without expiration in a non aged cache
243          this.set(hit.k, hit.v)
244        else {
245          const maxAge = expiresAt - now
246          // dont add already expired items
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        // 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
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