diff options
Diffstat (limited to 'node_modules/lru-cache/lib/lru-cache.js')
-rw-r--r-- | node_modules/lru-cache/lib/lru-cache.js | 469 |
1 files changed, 469 insertions, 0 deletions
diff --git a/node_modules/lru-cache/lib/lru-cache.js b/node_modules/lru-cache/lib/lru-cache.js new file mode 100644 index 000000000..e98ef78a5 --- /dev/null +++ b/node_modules/lru-cache/lib/lru-cache.js @@ -0,0 +1,469 @@ +module.exports = LRUCache + +// This will be a proper iterable 'Map' in engines that support it, +// or a fakey-fake PseudoMap in older versions. +var Map = require('pseudomap') +var util = require('util') + +// A linked list to keep track of recently-used-ness +var Yallist = require('yallist') + +// use symbols if possible, otherwise just _props +var symbols = {} +var hasSymbol = typeof Symbol === 'function' +var makeSymbol +/* istanbul ignore if */ +if (hasSymbol) { + makeSymbol = function (key) { + return Symbol.for(key) + } +} else { + makeSymbol = function (key) { + return '_' + key + } +} + +function priv (obj, key, val) { + var sym + if (symbols[key]) { + sym = symbols[key] + } else { + sym = makeSymbol(key) + symbols[key] = sym + } + if (arguments.length === 2) { + return obj[sym] + } else { + obj[sym] = val + return val + } +} + +function naiveLength () { return 1 } + +// lruList is a yallist where the head is the youngest +// item, and the tail is the oldest. the list contains the Hit +// objects as the entries. +// Each Hit object has a reference to its Yallist.Node. This +// never changes. +// +// cache is a Map (or PseudoMap) that matches the keys to +// the Yallist.Node object. +function LRUCache (options) { + if (!(this instanceof LRUCache)) { + return new LRUCache(options) + } + + if (typeof options === 'number') { + options = { max: options } + } + + if (!options) { + options = {} + } + + var max = priv(this, 'max', options.max) + // Kind of weird to have a default max of Infinity, but oh well. + if (!max || + !(typeof max === 'number') || + max <= 0) { + priv(this, 'max', Infinity) + } + + var lc = options.length || naiveLength + if (typeof lc !== 'function') { + lc = naiveLength + } + priv(this, 'lengthCalculator', lc) + + priv(this, 'allowStale', options.stale || false) + priv(this, 'maxAge', options.maxAge || 0) + priv(this, 'dispose', options.dispose) + this.reset() +} + +// resize the cache when the max changes. +Object.defineProperty(LRUCache.prototype, 'max', { + set: function (mL) { + if (!mL || !(typeof mL === 'number') || mL <= 0) { + mL = Infinity + } + priv(this, 'max', mL) + trim(this) + }, + get: function () { + return priv(this, 'max') + }, + enumerable: true +}) + +Object.defineProperty(LRUCache.prototype, 'allowStale', { + set: function (allowStale) { + priv(this, 'allowStale', !!allowStale) + }, + get: function () { + return priv(this, 'allowStale') + }, + enumerable: true +}) + +Object.defineProperty(LRUCache.prototype, 'maxAge', { + set: function (mA) { + if (!mA || !(typeof mA === 'number') || mA < 0) { + mA = 0 + } + priv(this, 'maxAge', mA) + trim(this) + }, + get: function () { + return priv(this, 'maxAge') + }, + enumerable: true +}) + +// resize the cache when the lengthCalculator changes. +Object.defineProperty(LRUCache.prototype, 'lengthCalculator', { + set: function (lC) { + if (typeof lC !== 'function') { + lC = naiveLength + } + if (lC !== priv(this, 'lengthCalculator')) { + priv(this, 'lengthCalculator', lC) + priv(this, 'length', 0) + priv(this, 'lruList').forEach(function (hit) { + hit.length = priv(this, 'lengthCalculator').call(this, hit.value, hit.key) + priv(this, 'length', priv(this, 'length') + hit.length) + }, this) + } + trim(this) + }, + get: function () { return priv(this, 'lengthCalculator') }, + enumerable: true +}) + +Object.defineProperty(LRUCache.prototype, 'length', { + get: function () { return priv(this, 'length') }, + enumerable: true +}) + +Object.defineProperty(LRUCache.prototype, 'itemCount', { + get: function () { return priv(this, 'lruList').length }, + enumerable: true +}) + +LRUCache.prototype.rforEach = function (fn, thisp) { + thisp = thisp || this + for (var walker = priv(this, 'lruList').tail; walker !== null;) { + var prev = walker.prev + forEachStep(this, fn, walker, thisp) + walker = prev + } +} + +function forEachStep (self, fn, node, thisp) { + var hit = node.value + if (isStale(self, hit)) { + del(self, node) + if (!priv(self, 'allowStale')) { + hit = undefined + } + } + if (hit) { + fn.call(thisp, hit.value, hit.key, self) + } +} + +LRUCache.prototype.forEach = function (fn, thisp) { + thisp = thisp || this + for (var walker = priv(this, 'lruList').head; walker !== null;) { + var next = walker.next + forEachStep(this, fn, walker, thisp) + walker = next + } +} + +LRUCache.prototype.keys = function () { + return priv(this, 'lruList').toArray().map(function (k) { + return k.key + }, this) +} + +LRUCache.prototype.values = function () { + return priv(this, 'lruList').toArray().map(function (k) { + return k.value + }, this) +} + +LRUCache.prototype.reset = function () { + if (priv(this, 'dispose') && + priv(this, 'lruList') && + priv(this, 'lruList').length) { + priv(this, 'lruList').forEach(function (hit) { + priv(this, 'dispose').call(this, hit.key, hit.value) + }, this) + } + + priv(this, 'cache', new Map()) // hash of items by key + priv(this, 'lruList', new Yallist()) // list of items in order of use recency + priv(this, 'length', 0) // length of items in the list +} + +LRUCache.prototype.dump = function () { + return priv(this, 'lruList').map(function (hit) { + if (!isStale(this, hit)) { + return { + k: hit.key, + v: hit.value, + e: hit.now + (hit.maxAge || 0) + } + } + }, this).toArray().filter(function (h) { + return h + }) +} + +LRUCache.prototype.dumpLru = function () { + return priv(this, 'lruList') +} + +LRUCache.prototype.inspect = function (n, opts) { + var str = 'LRUCache {' + var extras = false + + var as = priv(this, 'allowStale') + if (as) { + str += '\n allowStale: true' + extras = true + } + + var max = priv(this, 'max') + if (max && max !== Infinity) { + if (extras) { + str += ',' + } + str += '\n max: ' + util.inspect(max, opts) + extras = true + } + + var maxAge = priv(this, 'maxAge') + if (maxAge) { + if (extras) { + str += ',' + } + str += '\n maxAge: ' + util.inspect(maxAge, opts) + extras = true + } + + var lc = priv(this, 'lengthCalculator') + if (lc && lc !== naiveLength) { + if (extras) { + str += ',' + } + str += '\n length: ' + util.inspect(priv(this, 'length'), opts) + extras = true + } + + var didFirst = false + priv(this, 'lruList').forEach(function (item) { + if (didFirst) { + str += ',\n ' + } else { + if (extras) { + str += ',\n' + } + didFirst = true + str += '\n ' + } + var key = util.inspect(item.key).split('\n').join('\n ') + var val = { value: item.value } + if (item.maxAge !== maxAge) { + val.maxAge = item.maxAge + } + if (lc !== naiveLength) { + val.length = item.length + } + if (isStale(this, item)) { + val.stale = true + } + + val = util.inspect(val, opts).split('\n').join('\n ') + str += key + ' => ' + val + }) + + if (didFirst || extras) { + str += '\n' + } + str += '}' + + return str +} + +LRUCache.prototype.set = function (key, value, maxAge) { + maxAge = maxAge || priv(this, 'maxAge') + + var now = maxAge ? Date.now() : 0 + var len = priv(this, 'lengthCalculator').call(this, value, key) + + if (priv(this, 'cache').has(key)) { + if (len > priv(this, 'max')) { + del(this, priv(this, 'cache').get(key)) + return false + } + + var node = priv(this, 'cache').get(key) + var item = node.value + + // dispose of the old one before overwriting + if (priv(this, 'dispose')) { + priv(this, 'dispose').call(this, key, item.value) + } + + item.now = now + item.maxAge = maxAge + item.value = value + priv(this, 'length', priv(this, 'length') + (len - item.length)) + item.length = len + this.get(key) + trim(this) + return true + } + + var hit = new Entry(key, value, len, now, maxAge) + + // oversized objects fall out of cache automatically. + if (hit.length > priv(this, 'max')) { + if (priv(this, 'dispose')) { + priv(this, 'dispose').call(this, key, value) + } + return false + } + + priv(this, 'length', priv(this, 'length') + hit.length) + priv(this, 'lruList').unshift(hit) + priv(this, 'cache').set(key, priv(this, 'lruList').head) + trim(this) + return true +} + +LRUCache.prototype.has = function (key) { + if (!priv(this, 'cache').has(key)) return false + var hit = priv(this, 'cache').get(key).value + if (isStale(this, hit)) { + return false + } + return true +} + +LRUCache.prototype.get = function (key) { + return get(this, key, true) +} + +LRUCache.prototype.peek = function (key) { + return get(this, key, false) +} + +LRUCache.prototype.pop = function () { + var node = priv(this, 'lruList').tail + if (!node) return null + del(this, node) + return node.value +} + +LRUCache.prototype.del = function (key) { + del(this, priv(this, 'cache').get(key)) +} + +LRUCache.prototype.load = function (arr) { + // reset the cache + this.reset() + + var now = Date.now() + // A previous serialized cache has the most recent items first + for (var l = arr.length - 1; l >= 0; l--) { + var hit = arr[l] + var expiresAt = hit.e || 0 + if (expiresAt === 0) { + // the item was created without expiration in a non aged cache + this.set(hit.k, hit.v) + } else { + var maxAge = expiresAt - now + // dont add already expired items + if (maxAge > 0) { + this.set(hit.k, hit.v, maxAge) + } + } + } +} + +LRUCache.prototype.prune = function () { + var self = this + priv(this, 'cache').forEach(function (value, key) { + get(self, key, false) + }) +} + +function get (self, key, doUse) { + var node = priv(self, 'cache').get(key) + if (node) { + var hit = node.value + if (isStale(self, hit)) { + del(self, node) + if (!priv(self, 'allowStale')) hit = undefined + } else { + if (doUse) { + priv(self, 'lruList').unshiftNode(node) + } + } + if (hit) hit = hit.value + } + return hit +} + +function isStale (self, hit) { + if (!hit || (!hit.maxAge && !priv(self, 'maxAge'))) { + return false + } + var stale = false + var diff = Date.now() - hit.now + if (hit.maxAge) { + stale = diff > hit.maxAge + } else { + stale = priv(self, 'maxAge') && (diff > priv(self, 'maxAge')) + } + return stale +} + +function trim (self) { + if (priv(self, 'length') > priv(self, 'max')) { + for (var walker = priv(self, 'lruList').tail; + priv(self, 'length') > priv(self, 'max') && walker !== null;) { + // We know that we're about to delete this one, and also + // what the next least recently used key will be, so just + // go ahead and set it now. + var prev = walker.prev + del(self, walker) + walker = prev + } + } +} + +function del (self, node) { + if (node) { + var hit = node.value + if (priv(self, 'dispose')) { + priv(self, 'dispose').call(this, hit.key, hit.value) + } + priv(self, 'length', priv(self, 'length') - hit.length) + priv(self, 'cache').delete(hit.key) + priv(self, 'lruList').removeNode(node) + } +} + +// classy, since V8 prefers predictable objects. +function Entry (key, value, length, now, maxAge) { + this.key = key + this.value = value + this.length = length + this.now = now + this.maxAge = maxAge || 0 +} |