3 module.exports = LRUCache
5 // This will be a proper iterable 'Map' in engines that support it,
6 // or a fakey-fake PseudoMap in older versions.
7 var Map = require('pseudomap')
8 var util = require('util')
10 // A linked list to keep track of recently-used-ness
11 var Yallist = require('yallist')
13 // use symbols if possible, otherwise just _props
14 var hasSymbol = typeof Symbol === 'function' && process.env._nodeLRUCacheForceNoSymbol !== '1'
17 makeSymbol = function (key) {
21 makeSymbol = function (key) {
26 var MAX = makeSymbol('max')
27 var LENGTH = makeSymbol('length')
28 var LENGTH_CALCULATOR = makeSymbol('lengthCalculator')
29 var ALLOW_STALE = makeSymbol('allowStale')
30 var MAX_AGE = makeSymbol('maxAge')
31 var DISPOSE = makeSymbol('dispose')
32 var NO_DISPOSE_ON_SET = makeSymbol('noDisposeOnSet')
33 var LRU_LIST = makeSymbol('lruList')
34 var CACHE = makeSymbol('cache')
36 function naiveLength () { return 1 }
38 // lruList is a yallist where the head is the youngest
39 // item, and the tail is the oldest. the list contains the Hit
40 // objects as the entries.
41 // Each Hit object has a reference to its Yallist.Node. This
44 // cache is a Map (or PseudoMap) that matches the keys to
45 // the Yallist.Node object.
46 function LRUCache (options) {
47 if (!(this instanceof LRUCache)) {
48 return new LRUCache(options)
51 if (typeof options === 'number') {
52 options = { max: options }
59 var max = this[MAX] = options.max
60 // Kind of weird to have a default max of Infinity, but oh well.
62 !(typeof max === 'number') ||
67 var lc = options.length || naiveLength
68 if (typeof lc !== 'function') {
71 this[LENGTH_CALCULATOR] = lc
73 this[ALLOW_STALE] = options.stale || false
74 this[MAX_AGE] = options.maxAge || 0
75 this[DISPOSE] = options.dispose
76 this[NO_DISPOSE_ON_SET] = options.noDisposeOnSet || false
80 // resize the cache when the max changes.
81 Object.defineProperty(LRUCache.prototype, 'max', {
83 if (!mL || !(typeof mL === 'number') || mL <= 0) {
95 Object.defineProperty(LRUCache.prototype, 'allowStale', {
96 set: function (allowStale) {
97 this[ALLOW_STALE] = !!allowStale
100 return this[ALLOW_STALE]
105 Object.defineProperty(LRUCache.prototype, 'maxAge', {
107 if (!mA || !(typeof mA === 'number') || mA < 0) {
119 // resize the cache when the lengthCalculator changes.
120 Object.defineProperty(LRUCache.prototype, 'lengthCalculator', {
122 if (typeof lC !== 'function') {
125 if (lC !== this[LENGTH_CALCULATOR]) {
126 this[LENGTH_CALCULATOR] = lC
128 this[LRU_LIST].forEach(function (hit) {
129 hit.length = this[LENGTH_CALCULATOR](hit.value, hit.key)
130 this[LENGTH] += hit.length
135 get: function () { return this[LENGTH_CALCULATOR] },
139 Object.defineProperty(LRUCache.prototype, 'length', {
140 get: function () { return this[LENGTH] },
144 Object.defineProperty(LRUCache.prototype, 'itemCount', {
145 get: function () { return this[LRU_LIST].length },
149 LRUCache.prototype.rforEach = function (fn, thisp) {
150 thisp = thisp || this
151 for (var walker = this[LRU_LIST].tail; walker !== null;) {
152 var prev = walker.prev
153 forEachStep(this, fn, walker, thisp)
158 function forEachStep (self, fn, node, thisp) {
160 if (isStale(self, hit)) {
162 if (!self[ALLOW_STALE]) {
167 fn.call(thisp, hit.value, hit.key, self)
171 LRUCache.prototype.forEach = function (fn, thisp) {
172 thisp = thisp || this
173 for (var walker = this[LRU_LIST].head; walker !== null;) {
174 var next = walker.next
175 forEachStep(this, fn, walker, thisp)
180 LRUCache.prototype.keys = function () {
181 return this[LRU_LIST].toArray().map(function (k) {
186 LRUCache.prototype.values = function () {
187 return this[LRU_LIST].toArray().map(function (k) {
192 LRUCache.prototype.reset = function () {
195 this[LRU_LIST].length) {
196 this[LRU_LIST].forEach(function (hit) {
197 this[DISPOSE](hit.key, hit.value)
201 this[CACHE] = new Map() // hash of items by key
202 this[LRU_LIST] = new Yallist() // list of items in order of use recency
203 this[LENGTH] = 0 // length of items in the list
206 LRUCache.prototype.dump = function () {
207 return this[LRU_LIST].map(function (hit) {
208 if (!isStale(this, hit)) {
212 e: hit.now + (hit.maxAge || 0)
215 }, this).toArray().filter(function (h) {
220 LRUCache.prototype.dumpLru = function () {
221 return this[LRU_LIST]
224 /* istanbul ignore next */
225 LRUCache.prototype.inspect = function (n, opts) {
226 var str = 'LRUCache {'
229 var as = this[ALLOW_STALE]
231 str += '\n allowStale: true'
236 if (max && max !== Infinity) {
240 str += '\n max: ' + util.inspect(max, opts)
244 var maxAge = this[MAX_AGE]
249 str += '\n maxAge: ' + util.inspect(maxAge, opts)
253 var lc = this[LENGTH_CALCULATOR]
254 if (lc && lc !== naiveLength) {
258 str += '\n length: ' + util.inspect(this[LENGTH], opts)
263 this[LRU_LIST].forEach(function (item) {
273 var key = util.inspect(item.key).split('\n').join('\n ')
274 var val = { value: item.value }
275 if (item.maxAge !== maxAge) {
276 val.maxAge = item.maxAge
278 if (lc !== naiveLength) {
279 val.length = item.length
281 if (isStale(this, item)) {
285 val = util.inspect(val, opts).split('\n').join('\n ')
286 str += key + ' => ' + val
289 if (didFirst || extras) {
297 LRUCache.prototype.set = function (key, value, maxAge) {
298 maxAge = maxAge || this[MAX_AGE]
300 var now = maxAge ? Date.now() : 0
301 var len = this[LENGTH_CALCULATOR](value, key)
303 if (this[CACHE].has(key)) {
304 if (len > this[MAX]) {
305 del(this, this[CACHE].get(key))
309 var node = this[CACHE].get(key)
310 var item = node.value
312 // dispose of the old one before overwriting
313 // split out into 2 ifs for better coverage tracking
315 if (!this[NO_DISPOSE_ON_SET]) {
316 this[DISPOSE](key, item.value)
323 this[LENGTH] += len - item.length
330 var hit = new Entry(key, value, len, now, maxAge)
332 // oversized objects fall out of cache automatically.
333 if (hit.length > this[MAX]) {
335 this[DISPOSE](key, value)
340 this[LENGTH] += hit.length
341 this[LRU_LIST].unshift(hit)
342 this[CACHE].set(key, this[LRU_LIST].head)
347 LRUCache.prototype.has = function (key) {
348 if (!this[CACHE].has(key)) return false
349 var hit = this[CACHE].get(key).value
350 if (isStale(this, hit)) {
356 LRUCache.prototype.get = function (key) {
357 return get(this, key, true)
360 LRUCache.prototype.peek = function (key) {
361 return get(this, key, false)
364 LRUCache.prototype.pop = function () {
365 var node = this[LRU_LIST].tail
366 if (!node) return null
371 LRUCache.prototype.del = function (key) {
372 del(this, this[CACHE].get(key))
375 LRUCache.prototype.load = function (arr) {
380 // A previous serialized cache has the most recent items first
381 for (var l = arr.length - 1; l >= 0; l--) {
383 var expiresAt = hit.e || 0
384 if (expiresAt === 0) {
385 // the item was created without expiration in a non aged cache
386 this.set(hit.k, hit.v)
388 var maxAge = expiresAt - now
389 // dont add already expired items
391 this.set(hit.k, hit.v, maxAge)
397 LRUCache.prototype.prune = function () {
399 this[CACHE].forEach(function (value, key) {
400 get(self, key, false)
404 function get (self, key, doUse) {
405 var node = self[CACHE].get(key)
408 if (isStale(self, hit)) {
410 if (!self[ALLOW_STALE]) hit = undefined
413 self[LRU_LIST].unshiftNode(node)
416 if (hit) hit = hit.value
421 function isStale (self, hit) {
422 if (!hit || (!hit.maxAge && !self[MAX_AGE])) {
426 var diff = Date.now() - hit.now
428 stale = diff > hit.maxAge
430 stale = self[MAX_AGE] && (diff > self[MAX_AGE])
435 function trim (self) {
436 if (self[LENGTH] > self[MAX]) {
437 for (var walker = self[LRU_LIST].tail;
438 self[LENGTH] > self[MAX] && walker !== null;) {
439 // We know that we're about to delete this one, and also
440 // what the next least recently used key will be, so just
441 // go ahead and set it now.
442 var prev = walker.prev
449 function del (self, node) {
453 self[DISPOSE](hit.key, hit.value)
455 self[LENGTH] -= hit.length
456 self[CACHE].delete(hit.key)
457 self[LRU_LIST].removeNode(node)
461 // classy, since V8 prefers predictable objects.
462 function Entry (key, value, length, now, maxAge) {
467 this.maxAge = maxAge || 0