| ;(function () { // closure for web browsers |
| |
| if (typeof module === 'object' && module.exports) { |
| module.exports = LRUCache |
| } else { |
| // just set the global for non-node platforms. |
| this.LRUCache = LRUCache |
| } |
| |
| function hOP (obj, key) { |
| return Object.prototype.hasOwnProperty.call(obj, key) |
| } |
| |
| function naiveLength () { return 1 } |
| |
| var didTypeWarning = false |
| function typeCheckKey(key) { |
| if (!didTypeWarning && typeof key !== 'string' && typeof key !== 'number') { |
| didTypeWarning = true |
| console.error(new TypeError("LRU: key must be a string or number. Almost certainly a bug! " + typeof key).stack) |
| } |
| } |
| |
| function LRUCache (options) { |
| if (!(this instanceof LRUCache)) |
| return new LRUCache(options) |
| |
| if (typeof options === 'number') |
| options = { max: options } |
| |
| if (!options) |
| options = {} |
| |
| this._max = options.max |
| // Kind of weird to have a default max of Infinity, but oh well. |
| if (!this._max || !(typeof this._max === "number") || this._max <= 0 ) |
| this._max = Infinity |
| |
| this._lengthCalculator = options.length || naiveLength |
| if (typeof this._lengthCalculator !== "function") |
| this._lengthCalculator = naiveLength |
| |
| this._allowStale = options.stale || false |
| this._maxAge = options.maxAge || null |
| 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 |
| this._max = mL |
| if (this._length > this._max) trim(this) |
| } |
| , get : function () { return this._max } |
| , enumerable : true |
| }) |
| |
| // resize the cache when the lengthCalculator changes. |
| Object.defineProperty(LRUCache.prototype, "lengthCalculator", |
| { set : function (lC) { |
| if (typeof lC !== "function") { |
| this._lengthCalculator = naiveLength |
| this._length = this._itemCount |
| for (var key in this._cache) { |
| this._cache[key].length = 1 |
| } |
| } else { |
| this._lengthCalculator = lC |
| this._length = 0 |
| for (var key in this._cache) { |
| this._cache[key].length = this._lengthCalculator(this._cache[key].value) |
| this._length += this._cache[key].length |
| } |
| } |
| |
| if (this._length > this._max) trim(this) |
| } |
| , get : function () { return this._lengthCalculator } |
| , enumerable : true |
| }) |
| |
| Object.defineProperty(LRUCache.prototype, "length", |
| { get : function () { return this._length } |
| , enumerable : true |
| }) |
| |
| |
| Object.defineProperty(LRUCache.prototype, "itemCount", |
| { get : function () { return this._itemCount } |
| , enumerable : true |
| }) |
| |
| LRUCache.prototype.forEach = function (fn, thisp) { |
| thisp = thisp || this |
| var i = 0 |
| var itemCount = this._itemCount |
| |
| for (var k = this._mru - 1; k >= 0 && i < itemCount; k--) if (this._lruList[k]) { |
| i++ |
| var hit = this._lruList[k] |
| if (isStale(this, hit)) { |
| del(this, hit) |
| if (!this._allowStale) hit = undefined |
| } |
| if (hit) { |
| fn.call(thisp, hit.value, hit.key, this) |
| } |
| } |
| } |
| |
| LRUCache.prototype.keys = function () { |
| var keys = new Array(this._itemCount) |
| var i = 0 |
| for (var k = this._mru - 1; k >= 0 && i < this._itemCount; k--) if (this._lruList[k]) { |
| var hit = this._lruList[k] |
| keys[i++] = hit.key |
| } |
| return keys |
| } |
| |
| LRUCache.prototype.values = function () { |
| var values = new Array(this._itemCount) |
| var i = 0 |
| for (var k = this._mru - 1; k >= 0 && i < this._itemCount; k--) if (this._lruList[k]) { |
| var hit = this._lruList[k] |
| values[i++] = hit.value |
| } |
| return values |
| } |
| |
| LRUCache.prototype.reset = function () { |
| if (this._dispose && this._cache) { |
| for (var k in this._cache) { |
| this._dispose(k, this._cache[k].value) |
| } |
| } |
| |
| this._cache = Object.create(null) // hash of items by key |
| this._lruList = Object.create(null) // list of items in order of use recency |
| this._mru = 0 // most recently used |
| this._lru = 0 // least recently used |
| this._length = 0 // number of items in the list |
| this._itemCount = 0 |
| } |
| |
| LRUCache.prototype.dump = function () { |
| var arr = [] |
| var i = 0 |
| |
| for (var k = this._mru - 1; k >= 0 && i < this._itemCount; k--) if (this._lruList[k]) { |
| var hit = this._lruList[k] |
| if (!isStale(this, hit)) { |
| //Do not store staled hits |
| ++i |
| arr.push({ |
| k: hit.key, |
| v: hit.value, |
| e: hit.now + (hit.maxAge || 0) |
| }); |
| } |
| } |
| //arr has the most read first |
| return arr |
| } |
| |
| LRUCache.prototype.dumpLru = function () { |
| return this._lruList |
| } |
| |
| LRUCache.prototype.set = function (key, value, maxAge) { |
| maxAge = maxAge || this._maxAge |
| typeCheckKey(key) |
| |
| var now = maxAge ? Date.now() : 0 |
| var len = this._lengthCalculator(value) |
| |
| if (hOP(this._cache, key)) { |
| if (len > this._max) { |
| del(this, this._cache[key]) |
| return false |
| } |
| // dispose of the old one before overwriting |
| if (this._dispose) |
| this._dispose(key, this._cache[key].value) |
| |
| this._cache[key].now = now |
| this._cache[key].maxAge = maxAge |
| this._cache[key].value = value |
| this._length += (len - this._cache[key].length) |
| this._cache[key].length = len |
| this.get(key) |
| |
| if (this._length > this._max) |
| trim(this) |
| |
| return true |
| } |
| |
| var hit = new Entry(key, value, this._mru++, len, now, maxAge) |
| |
| // oversized objects fall out of cache automatically. |
| if (hit.length > this._max) { |
| if (this._dispose) this._dispose(key, value) |
| return false |
| } |
| |
| this._length += hit.length |
| this._lruList[hit.lu] = this._cache[key] = hit |
| this._itemCount ++ |
| |
| if (this._length > this._max) |
| trim(this) |
| |
| return true |
| } |
| |
| LRUCache.prototype.has = function (key) { |
| typeCheckKey(key) |
| if (!hOP(this._cache, key)) return false |
| var hit = this._cache[key] |
| if (isStale(this, hit)) { |
| return false |
| } |
| return true |
| } |
| |
| LRUCache.prototype.get = function (key) { |
| typeCheckKey(key) |
| return get(this, key, true) |
| } |
| |
| LRUCache.prototype.peek = function (key) { |
| typeCheckKey(key) |
| return get(this, key, false) |
| } |
| |
| LRUCache.prototype.pop = function () { |
| var hit = this._lruList[this._lru] |
| del(this, hit) |
| return hit || null |
| } |
| |
| LRUCache.prototype.del = function (key) { |
| typeCheckKey(key) |
| del(this, this._cache[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] |
| typeCheckKey(hit.k) |
| 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) |
| } |
| } |
| } |
| |
| function get (self, key, doUse) { |
| typeCheckKey(key) |
| var hit = self._cache[key] |
| if (hit) { |
| if (isStale(self, hit)) { |
| del(self, hit) |
| if (!self._allowStale) hit = undefined |
| } else { |
| if (doUse) use(self, hit) |
| } |
| if (hit) hit = hit.value |
| } |
| return hit |
| } |
| |
| function isStale(self, hit) { |
| if (!hit || (!hit.maxAge && !self._maxAge)) return false |
| var stale = false; |
| var diff = Date.now() - hit.now |
| if (hit.maxAge) { |
| stale = diff > hit.maxAge |
| } else { |
| stale = self._maxAge && (diff > self._maxAge) |
| } |
| return stale; |
| } |
| |
| function use (self, hit) { |
| shiftLU(self, hit) |
| hit.lu = self._mru ++ |
| self._lruList[hit.lu] = hit |
| } |
| |
| function trim (self) { |
| while (self._lru < self._mru && self._length > self._max) |
| del(self, self._lruList[self._lru]) |
| } |
| |
| function shiftLU (self, hit) { |
| delete self._lruList[ hit.lu ] |
| while (self._lru < self._mru && !self._lruList[self._lru]) self._lru ++ |
| } |
| |
| function del (self, hit) { |
| if (hit) { |
| if (self._dispose) self._dispose(hit.key, hit.value) |
| self._length -= hit.length |
| self._itemCount -- |
| delete self._cache[ hit.key ] |
| shiftLU(self, hit) |
| } |
| } |
| |
| // classy, since V8 prefers predictable objects. |
| function Entry (key, value, lu, length, now, maxAge) { |
| this.key = key |
| this.value = value |
| this.lu = lu |
| this.length = length |
| this.now = now |
| if (maxAge) this.maxAge = maxAge |
| } |
| |
| })() |