1 ;(function () { // closure for web browsers
3 if (typeof module === 'object' && module.exports) {
4 module.exports = LRUCache
6 // just set the global for non-node platforms.
7 this.LRUCache = LRUCache
10 function hOP (obj, key) {
11 return Object.prototype.hasOwnProperty.call(obj, key)
14 function naiveLength () { return 1 }
16 var didTypeWarning = false
17 function typeCheckKey(key) {
18 if (!didTypeWarning && typeof key !== 'string' && typeof key !== 'number') {
20 console.error(new TypeError("LRU: key must be a string or number. Almost certainly a bug! " + typeof key).stack)
24 function LRUCache (options) {
25 if (!(this instanceof LRUCache))
26 return new LRUCache(options)
28 if (typeof options === 'number')
29 options = { max: options }
34 this._max = options.max
35 // Kind of weird to have a default max of Infinity, but oh well.
36 if (!this._max || !(typeof this._max === "number") || this._max <= 0 )
39 this._lengthCalculator = options.length || naiveLength
40 if (typeof this._lengthCalculator !== "function")
41 this._lengthCalculator = naiveLength
43 this._allowStale = options.stale || false
44 this._maxAge = options.maxAge || null
45 this._dispose = options.dispose
49 // resize the cache when the max changes.
50 Object.defineProperty(LRUCache.prototype, "max",
51 { set : function (mL) {
52 if (!mL || !(typeof mL === "number") || mL <= 0 ) mL = Infinity
54 if (this._length > this._max) trim(this)
56 , get : function () { return this._max }
60 // resize the cache when the lengthCalculator changes.
61 Object.defineProperty(LRUCache.prototype, "lengthCalculator",
62 { set : function (lC) {
63 if (typeof lC !== "function") {
64 this._lengthCalculator = naiveLength
65 this._length = this._itemCount
66 for (var key in this._cache) {
67 this._cache[key].length = 1
70 this._lengthCalculator = lC
72 for (var key in this._cache) {
73 this._cache[key].length = this._lengthCalculator(this._cache[key].value)
74 this._length += this._cache[key].length
78 if (this._length > this._max) trim(this)
80 , get : function () { return this._lengthCalculator }
84 Object.defineProperty(LRUCache.prototype, "length",
85 { get : function () { return this._length }
90 Object.defineProperty(LRUCache.prototype, "itemCount",
91 { get : function () { return this._itemCount }
95 LRUCache.prototype.forEach = function (fn, thisp) {
98 var itemCount = this._itemCount
100 for (var k = this._mru - 1; k >= 0 && i < itemCount; k--) if (this._lruList[k]) {
102 var hit = this._lruList[k]
103 if (isStale(this, hit)) {
105 if (!this._allowStale) hit = undefined
108 fn.call(thisp, hit.value, hit.key, this)
113 LRUCache.prototype.keys = function () {
114 var keys = new Array(this._itemCount)
116 for (var k = this._mru - 1; k >= 0 && i < this._itemCount; k--) if (this._lruList[k]) {
117 var hit = this._lruList[k]
123 LRUCache.prototype.values = function () {
124 var values = new Array(this._itemCount)
126 for (var k = this._mru - 1; k >= 0 && i < this._itemCount; k--) if (this._lruList[k]) {
127 var hit = this._lruList[k]
128 values[i++] = hit.value
133 LRUCache.prototype.reset = function () {
134 if (this._dispose && this._cache) {
135 for (var k in this._cache) {
136 this._dispose(k, this._cache[k].value)
140 this._cache = Object.create(null) // hash of items by key
141 this._lruList = Object.create(null) // list of items in order of use recency
142 this._mru = 0 // most recently used
143 this._lru = 0 // least recently used
144 this._length = 0 // number of items in the list
148 LRUCache.prototype.dump = function () {
152 for (var k = this._mru - 1; k >= 0 && i < this._itemCount; k--) if (this._lruList[k]) {
153 var hit = this._lruList[k]
154 if (!isStale(this, hit)) {
155 //Do not store staled hits
160 e: hit.now + (hit.maxAge || 0)
164 //arr has the most read first
168 LRUCache.prototype.dumpLru = function () {
172 LRUCache.prototype.set = function (key, value, maxAge) {
173 maxAge = maxAge || this._maxAge
176 var now = maxAge ? Date.now() : 0
177 var len = this._lengthCalculator(value)
179 if (hOP(this._cache, key)) {
180 if (len > this._max) {
181 del(this, this._cache[key])
184 // dispose of the old one before overwriting
186 this._dispose(key, this._cache[key].value)
188 this._cache[key].now = now
189 this._cache[key].maxAge = maxAge
190 this._cache[key].value = value
191 this._length += (len - this._cache[key].length)
192 this._cache[key].length = len
195 if (this._length > this._max)
201 var hit = new Entry(key, value, this._mru++, len, now, maxAge)
203 // oversized objects fall out of cache automatically.
204 if (hit.length > this._max) {
205 if (this._dispose) this._dispose(key, value)
209 this._length += hit.length
210 this._lruList[hit.lu] = this._cache[key] = hit
213 if (this._length > this._max)
219 LRUCache.prototype.has = function (key) {
221 if (!hOP(this._cache, key)) return false
222 var hit = this._cache[key]
223 if (isStale(this, hit)) {
229 LRUCache.prototype.get = function (key) {
231 return get(this, key, true)
234 LRUCache.prototype.peek = function (key) {
236 return get(this, key, false)
239 LRUCache.prototype.pop = function () {
240 var hit = this._lruList[this._lru]
245 LRUCache.prototype.del = function (key) {
247 del(this, this._cache[key])
250 LRUCache.prototype.load = function (arr) {
255 //A previous serialized cache has the most recent items first
256 for (var l = arr.length - 1; l >= 0; l-- ) {
259 var expiresAt = hit.e || 0
260 if (expiresAt === 0) {
261 //the item was created without expiration in a non aged cache
262 this.set(hit.k, hit.v)
264 var maxAge = expiresAt - now
265 //dont add already expired items
266 if (maxAge > 0) this.set(hit.k, hit.v, maxAge)
271 function get (self, key, doUse) {
273 var hit = self._cache[key]
275 if (isStale(self, hit)) {
277 if (!self._allowStale) hit = undefined
279 if (doUse) use(self, hit)
281 if (hit) hit = hit.value
286 function isStale(self, hit) {
287 if (!hit || (!hit.maxAge && !self._maxAge)) return false
289 var diff = Date.now() - hit.now
291 stale = diff > hit.maxAge
293 stale = self._maxAge && (diff > self._maxAge)
298 function use (self, hit) {
300 hit.lu = self._mru ++
301 self._lruList[hit.lu] = hit
304 function trim (self) {
305 while (self._lru < self._mru && self._length > self._max)
306 del(self, self._lruList[self._lru])
309 function shiftLU (self, hit) {
310 delete self._lruList[ hit.lu ]
311 while (self._lru < self._mru && !self._lruList[self._lru]) self._lru ++
314 function del (self, hit) {
316 if (self._dispose) self._dispose(hit.key, hit.value)
317 self._length -= hit.length
319 delete self._cache[ hit.key ]
324 // classy, since V8 prefers predictable objects.
325 function Entry (key, value, lu, length, now, maxAge) {
331 if (maxAge) this.maxAge = maxAge