1 module.exports = LRUCache
3 // This will be a proper iterable 'Map' in engines that support it,
4 // or a fakey-fake PseudoMap in older versions.
5 var Map = require('pseudomap')
6 var util = require('util')
8 // A linked list to keep track of recently-used-ness
9 var Yallist = require('yallist')
11 // use symbols if possible, otherwise just _props
13 var hasSymbol = typeof Symbol === 'function'
15 /* istanbul ignore if */
17 makeSymbol = function (key) {
18 return Symbol.for(key)
21 makeSymbol = function (key) {
26 function priv (obj, key, val) {
34 if (arguments.length === 2) {
42 function naiveLength () { return 1 }
44 // lruList is a yallist where the head is the youngest
45 // item, and the tail is the oldest. the list contains the Hit
46 // objects as the entries.
47 // Each Hit object has a reference to its Yallist.Node. This
50 // cache is a Map (or PseudoMap) that matches the keys to
51 // the Yallist.Node object.
52 function LRUCache (options) {
53 if (!(this instanceof LRUCache)) {
54 return new LRUCache(options)
57 if (typeof options === 'number') {
58 options = { max: options }
65 var max = priv(this, 'max', options.max)
66 // Kind of weird to have a default max of Infinity, but oh well.
68 !(typeof max === 'number') ||
70 priv(this, 'max', Infinity)
73 var lc = options.length || naiveLength
74 if (typeof lc !== 'function') {
77 priv(this, 'lengthCalculator', lc)
79 priv(this, 'allowStale', options.stale || false)
80 priv(this, 'maxAge', options.maxAge || 0)
81 priv(this, 'dispose', options.dispose)
85 // resize the cache when the max changes.
86 Object.defineProperty(LRUCache.prototype, 'max', {
88 if (!mL || !(typeof mL === 'number') || mL <= 0) {
95 return priv(this, 'max')
100 Object.defineProperty(LRUCache.prototype, 'allowStale', {
101 set: function (allowStale) {
102 priv(this, 'allowStale', !!allowStale)
105 return priv(this, 'allowStale')
110 Object.defineProperty(LRUCache.prototype, 'maxAge', {
112 if (!mA || !(typeof mA === 'number') || mA < 0) {
115 priv(this, 'maxAge', mA)
119 return priv(this, 'maxAge')
124 // resize the cache when the lengthCalculator changes.
125 Object.defineProperty(LRUCache.prototype, 'lengthCalculator', {
127 if (typeof lC !== 'function') {
130 if (lC !== priv(this, 'lengthCalculator')) {
131 priv(this, 'lengthCalculator', lC)
132 priv(this, 'length', 0)
133 priv(this, 'lruList').forEach(function (hit) {
134 hit.length = priv(this, 'lengthCalculator').call(this, hit.value, hit.key)
135 priv(this, 'length', priv(this, 'length') + hit.length)
140 get: function () { return priv(this, 'lengthCalculator') },
144 Object.defineProperty(LRUCache.prototype, 'length', {
145 get: function () { return priv(this, 'length') },
149 Object.defineProperty(LRUCache.prototype, 'itemCount', {
150 get: function () { return priv(this, 'lruList').length },
154 LRUCache.prototype.rforEach = function (fn, thisp) {
155 thisp = thisp || this
156 for (var walker = priv(this, 'lruList').tail; walker !== null;) {
157 var prev = walker.prev
158 forEachStep(this, fn, walker, thisp)
163 function forEachStep (self, fn, node, thisp) {
165 if (isStale(self, hit)) {
167 if (!priv(self, 'allowStale')) {
172 fn.call(thisp, hit.value, hit.key, self)
176 LRUCache.prototype.forEach = function (fn, thisp) {
177 thisp = thisp || this
178 for (var walker = priv(this, 'lruList').head; walker !== null;) {
179 var next = walker.next
180 forEachStep(this, fn, walker, thisp)
185 LRUCache.prototype.keys = function () {
186 return priv(this, 'lruList').toArray().map(function (k) {
191 LRUCache.prototype.values = function () {
192 return priv(this, 'lruList').toArray().map(function (k) {
197 LRUCache.prototype.reset = function () {
198 if (priv(this, 'dispose') &&
199 priv(this, 'lruList') &&
200 priv(this, 'lruList').length) {
201 priv(this, 'lruList').forEach(function (hit) {
202 priv(this, 'dispose').call(this, hit.key, hit.value)
206 priv(this, 'cache', new Map()) // hash of items by key
207 priv(this, 'lruList', new Yallist()) // list of items in order of use recency
208 priv(this, 'length', 0) // length of items in the list
211 LRUCache.prototype.dump = function () {
212 return priv(this, 'lruList').map(function (hit) {
213 if (!isStale(this, hit)) {
217 e: hit.now + (hit.maxAge || 0)
220 }, this).toArray().filter(function (h) {
225 LRUCache.prototype.dumpLru = function () {
226 return priv(this, 'lruList')
229 LRUCache.prototype.inspect = function (n, opts) {
230 var str = 'LRUCache {'
233 var as = priv(this, 'allowStale')
235 str += '\n allowStale: true'
239 var max = priv(this, 'max')
240 if (max && max !== Infinity) {
244 str += '\n max: ' + util.inspect(max, opts)
248 var maxAge = priv(this, 'maxAge')
253 str += '\n maxAge: ' + util.inspect(maxAge, opts)
257 var lc = priv(this, 'lengthCalculator')
258 if (lc && lc !== naiveLength) {
262 str += '\n length: ' + util.inspect(priv(this, 'length'), opts)
267 priv(this, 'lruList').forEach(function (item) {
277 var key = util.inspect(item.key).split('\n').join('\n ')
278 var val = { value: item.value }
279 if (item.maxAge !== maxAge) {
280 val.maxAge = item.maxAge
282 if (lc !== naiveLength) {
283 val.length = item.length
285 if (isStale(this, item)) {
289 val = util.inspect(val, opts).split('\n').join('\n ')
290 str += key + ' => ' + val
293 if (didFirst || extras) {
301 LRUCache.prototype.set = function (key, value, maxAge) {
302 maxAge = maxAge || priv(this, 'maxAge')
304 var now = maxAge ? Date.now() : 0
305 var len = priv(this, 'lengthCalculator').call(this, value, key)
307 if (priv(this, 'cache').has(key)) {
308 if (len > priv(this, 'max')) {
309 del(this, priv(this, 'cache').get(key))
313 var node = priv(this, 'cache').get(key)
314 var item = node.value
316 // dispose of the old one before overwriting
317 if (priv(this, 'dispose')) {
318 priv(this, 'dispose').call(this, key, item.value)
324 priv(this, 'length', priv(this, 'length') + (len - item.length))
331 var hit = new Entry(key, value, len, now, maxAge)
333 // oversized objects fall out of cache automatically.
334 if (hit.length > priv(this, 'max')) {
335 if (priv(this, 'dispose')) {
336 priv(this, 'dispose').call(this, key, value)
341 priv(this, 'length', priv(this, 'length') + hit.length)
342 priv(this, 'lruList').unshift(hit)
343 priv(this, 'cache').set(key, priv(this, 'lruList').head)
348 LRUCache.prototype.has = function (key) {
349 if (!priv(this, 'cache').has(key)) return false
350 var hit = priv(this, 'cache').get(key).value
351 if (isStale(this, hit)) {
357 LRUCache.prototype.get = function (key) {
358 return get(this, key, true)
361 LRUCache.prototype.peek = function (key) {
362 return get(this, key, false)
365 LRUCache.prototype.pop = function () {
366 var node = priv(this, 'lruList').tail
367 if (!node) return null
372 LRUCache.prototype.del = function (key) {
373 del(this, priv(this, 'cache').get(key))
376 LRUCache.prototype.load = function (arr) {
381 // A previous serialized cache has the most recent items first
382 for (var l = arr.length - 1; l >= 0; l--) {
384 var expiresAt = hit.e || 0
385 if (expiresAt === 0) {
386 // the item was created without expiration in a non aged cache
387 this.set(hit.k, hit.v)
389 var maxAge = expiresAt - now
390 // dont add already expired items
392 this.set(hit.k, hit.v, maxAge)
398 LRUCache.prototype.prune = function () {
400 priv(this, 'cache').forEach(function (value, key) {
401 get(self, key, false)
405 function get (self, key, doUse) {
406 var node = priv(self, 'cache').get(key)
409 if (isStale(self, hit)) {
411 if (!priv(self, 'allowStale')) hit = undefined
414 priv(self, 'lruList').unshiftNode(node)
417 if (hit) hit = hit.value
422 function isStale (self, hit) {
423 if (!hit || (!hit.maxAge && !priv(self, 'maxAge'))) {
427 var diff = Date.now() - hit.now
429 stale = diff > hit.maxAge
431 stale = priv(self, 'maxAge') && (diff > priv(self, 'maxAge'))
436 function trim (self) {
437 if (priv(self, 'length') > priv(self, 'max')) {
438 for (var walker = priv(self, 'lruList').tail;
439 priv(self, 'length') > priv(self, 'max') && walker !== null;) {
440 // We know that we're about to delete this one, and also
441 // what the next least recently used key will be, so just
442 // go ahead and set it now.
443 var prev = walker.prev
450 function del (self, node) {
453 if (priv(self, 'dispose')) {
454 priv(self, 'dispose').call(this, hit.key, hit.value)
456 priv(self, 'length', priv(self, 'length') - hit.length)
457 priv(self, 'cache').delete(hit.key)
458 priv(self, 'lruList').removeNode(node)
462 // classy, since V8 prefers predictable objects.
463 function Entry (key, value, length, now, maxAge) {
468 this.maxAge = maxAge || 0