1 | ;(function () {
|
2 |
|
3 | if (typeof module === 'object' && module.exports) {
|
4 | module.exports = LRUCache
|
5 | } else {
|
6 |
|
7 | this.LRUCache = LRUCache
|
8 | }
|
9 |
|
10 | function hOP (obj, key) {
|
11 | return Object.prototype.hasOwnProperty.call(obj, key)
|
12 | }
|
13 |
|
14 | function naiveLength () { return 1 }
|
15 |
|
16 | function typeCheckKey(key) {
|
17 | if (typeof key !== 'string' && typeof key !== 'number')
|
18 | throw new TypeError("key must be a string or number. " + typeof key)
|
19 | }
|
20 |
|
21 | function LRUCache (options) {
|
22 | if (!(this instanceof LRUCache))
|
23 | return new LRUCache(options)
|
24 |
|
25 | if (typeof options === 'number')
|
26 | options = { max: options }
|
27 |
|
28 | if (!options)
|
29 | options = {}
|
30 |
|
31 | this._max = options.max
|
32 |
|
33 | if (!this._max || !(typeof this._max === "number") || this._max <= 0 )
|
34 | this._max = Infinity
|
35 |
|
36 | this._lengthCalculator = options.length || naiveLength
|
37 | if (typeof this._lengthCalculator !== "function")
|
38 | this._lengthCalculator = naiveLength
|
39 |
|
40 | this._allowStale = options.stale || false
|
41 | this._maxAge = options.maxAge || null
|
42 | this._dispose = options.dispose
|
43 | this.reset()
|
44 | }
|
45 |
|
46 |
|
47 | Object.defineProperty(LRUCache.prototype, "max",
|
48 | { set : function (mL) {
|
49 | if (!mL || !(typeof mL === "number") || mL <= 0 ) mL = Infinity
|
50 | this._max = mL
|
51 | if (this._length > this._max) trim(this)
|
52 | }
|
53 | , get : function () { return this._max }
|
54 | , enumerable : true
|
55 | })
|
56 |
|
57 |
|
58 | Object.defineProperty(LRUCache.prototype, "lengthCalculator",
|
59 | { set : function (lC) {
|
60 | if (typeof lC !== "function") {
|
61 | this._lengthCalculator = naiveLength
|
62 | this._length = this._itemCount
|
63 | for (var key in this._cache) {
|
64 | this._cache[key].length = 1
|
65 | }
|
66 | } else {
|
67 | this._lengthCalculator = lC
|
68 | this._length = 0
|
69 | for (var key in this._cache) {
|
70 | this._cache[key].length = this._lengthCalculator(this._cache[key].value)
|
71 | this._length += this._cache[key].length
|
72 | }
|
73 | }
|
74 |
|
75 | if (this._length > this._max) trim(this)
|
76 | }
|
77 | , get : function () { return this._lengthCalculator }
|
78 | , enumerable : true
|
79 | })
|
80 |
|
81 | Object.defineProperty(LRUCache.prototype, "length",
|
82 | { get : function () { return this._length }
|
83 | , enumerable : true
|
84 | })
|
85 |
|
86 |
|
87 | Object.defineProperty(LRUCache.prototype, "itemCount",
|
88 | { get : function () { return this._itemCount }
|
89 | , enumerable : true
|
90 | })
|
91 |
|
92 | LRUCache.prototype.forEach = function (fn, thisp) {
|
93 | thisp = thisp || this
|
94 | var i = 0
|
95 | var itemCount = this._itemCount
|
96 |
|
97 | for (var k = this._mru - 1; k >= 0 && i < itemCount; k--) if (this._lruList[k]) {
|
98 | i++
|
99 | var hit = this._lruList[k]
|
100 | if (isStale(this, hit)) {
|
101 | del(this, hit)
|
102 | if (!this._allowStale) hit = undefined
|
103 | }
|
104 | if (hit) {
|
105 | fn.call(thisp, hit.value, hit.key, this)
|
106 | }
|
107 | }
|
108 | }
|
109 |
|
110 | LRUCache.prototype.keys = function () {
|
111 | var keys = new Array(this._itemCount)
|
112 | var i = 0
|
113 | for (var k = this._mru - 1; k >= 0 && i < this._itemCount; k--) if (this._lruList[k]) {
|
114 | var hit = this._lruList[k]
|
115 | keys[i++] = hit.key
|
116 | }
|
117 | return keys
|
118 | }
|
119 |
|
120 | LRUCache.prototype.values = function () {
|
121 | var values = new Array(this._itemCount)
|
122 | var i = 0
|
123 | for (var k = this._mru - 1; k >= 0 && i < this._itemCount; k--) if (this._lruList[k]) {
|
124 | var hit = this._lruList[k]
|
125 | values[i++] = hit.value
|
126 | }
|
127 | return values
|
128 | }
|
129 |
|
130 | LRUCache.prototype.reset = function () {
|
131 | if (this._dispose && this._cache) {
|
132 | for (var k in this._cache) {
|
133 | this._dispose(k, this._cache[k].value)
|
134 | }
|
135 | }
|
136 |
|
137 | this._cache = Object.create(null)
|
138 | this._lruList = Object.create(null)
|
139 | this._mru = 0
|
140 | this._lru = 0
|
141 | this._length = 0
|
142 | this._itemCount = 0
|
143 | }
|
144 |
|
145 | LRUCache.prototype.dump = function () {
|
146 | var arr = []
|
147 | var i = 0
|
148 |
|
149 | for (var k = this._mru - 1; k >= 0 && i < this._itemCount; k--) if (this._lruList[k]) {
|
150 | var hit = this._lruList[k]
|
151 | if (!isStale(this, hit)) {
|
152 |
|
153 | ++i
|
154 | arr.push({
|
155 | k: hit.key,
|
156 | v: hit.value,
|
157 | e: hit.now + (hit.maxAge || 0)
|
158 | });
|
159 | }
|
160 | }
|
161 |
|
162 | return arr
|
163 | }
|
164 |
|
165 | LRUCache.prototype.dumpLru = function () {
|
166 | return this._lruList
|
167 | }
|
168 |
|
169 | LRUCache.prototype.set = function (key, value, maxAge) {
|
170 | maxAge = maxAge || this._maxAge
|
171 | typeCheckKey(key)
|
172 |
|
173 | var now = maxAge ? Date.now() : 0
|
174 | var len = this._lengthCalculator(value)
|
175 |
|
176 | if (hOP(this._cache, key)) {
|
177 | if (len > this._max) {
|
178 | del(this, this._cache[key])
|
179 | return false
|
180 | }
|
181 |
|
182 | if (this._dispose)
|
183 | this._dispose(key, this._cache[key].value)
|
184 |
|
185 | this._cache[key].now = now
|
186 | this._cache[key].maxAge = maxAge
|
187 | this._cache[key].value = value
|
188 | this._length += (len - this._cache[key].length)
|
189 | this._cache[key].length = len
|
190 | this.get(key)
|
191 |
|
192 | if (this._length > this._max)
|
193 | trim(this)
|
194 |
|
195 | return true
|
196 | }
|
197 |
|
198 | var hit = new Entry(key, value, this._mru++, len, now, maxAge)
|
199 |
|
200 |
|
201 | if (hit.length > this._max) {
|
202 | if (this._dispose) this._dispose(key, value)
|
203 | return false
|
204 | }
|
205 |
|
206 | this._length += hit.length
|
207 | this._lruList[hit.lu] = this._cache[key] = hit
|
208 | this._itemCount ++
|
209 |
|
210 | if (this._length > this._max)
|
211 | trim(this)
|
212 |
|
213 | return true
|
214 | }
|
215 |
|
216 | LRUCache.prototype.has = function (key) {
|
217 | typeCheckKey(key)
|
218 | if (!hOP(this._cache, key)) return false
|
219 | var hit = this._cache[key]
|
220 | if (isStale(this, hit)) {
|
221 | return false
|
222 | }
|
223 | return true
|
224 | }
|
225 |
|
226 | LRUCache.prototype.get = function (key) {
|
227 | typeCheckKey(key)
|
228 | return get(this, key, true)
|
229 | }
|
230 |
|
231 | LRUCache.prototype.peek = function (key) {
|
232 | typeCheckKey(key)
|
233 | return get(this, key, false)
|
234 | }
|
235 |
|
236 | LRUCache.prototype.pop = function () {
|
237 | var hit = this._lruList[this._lru]
|
238 | del(this, hit)
|
239 | return hit || null
|
240 | }
|
241 |
|
242 | LRUCache.prototype.del = function (key) {
|
243 | typeCheckKey(key)
|
244 | del(this, this._cache[key])
|
245 | }
|
246 |
|
247 | LRUCache.prototype.load = function (arr) {
|
248 |
|
249 | this.reset();
|
250 |
|
251 | var now = Date.now()
|
252 |
|
253 | for (var l = arr.length - 1; l >= 0; l-- ) {
|
254 | var hit = arr[l]
|
255 | typeCheckKey(hit.k)
|
256 | var expiresAt = hit.e || 0
|
257 | if (expiresAt === 0) {
|
258 |
|
259 | this.set(hit.k, hit.v)
|
260 | } else {
|
261 | var maxAge = expiresAt - now
|
262 |
|
263 | if (maxAge > 0) this.set(hit.k, hit.v, maxAge)
|
264 | }
|
265 | }
|
266 | }
|
267 |
|
268 | function get (self, key, doUse) {
|
269 | typeCheckKey(key)
|
270 | var hit = self._cache[key]
|
271 | if (hit) {
|
272 | if (isStale(self, hit)) {
|
273 | del(self, hit)
|
274 | if (!self._allowStale) hit = undefined
|
275 | } else {
|
276 | if (doUse) use(self, hit)
|
277 | }
|
278 | if (hit) hit = hit.value
|
279 | }
|
280 | return hit
|
281 | }
|
282 |
|
283 | function isStale(self, hit) {
|
284 | if (!hit || (!hit.maxAge && !self._maxAge)) return false
|
285 | var stale = false;
|
286 | var diff = Date.now() - hit.now
|
287 | if (hit.maxAge) {
|
288 | stale = diff > hit.maxAge
|
289 | } else {
|
290 | stale = self._maxAge && (diff > self._maxAge)
|
291 | }
|
292 | return stale;
|
293 | }
|
294 |
|
295 | function use (self, hit) {
|
296 | shiftLU(self, hit)
|
297 | hit.lu = self._mru ++
|
298 | self._lruList[hit.lu] = hit
|
299 | }
|
300 |
|
301 | function trim (self) {
|
302 | while (self._lru < self._mru && self._length > self._max)
|
303 | del(self, self._lruList[self._lru])
|
304 | }
|
305 |
|
306 | function shiftLU (self, hit) {
|
307 | delete self._lruList[ hit.lu ]
|
308 | while (self._lru < self._mru && !self._lruList[self._lru]) self._lru ++
|
309 | }
|
310 |
|
311 | function del (self, hit) {
|
312 | if (hit) {
|
313 | if (self._dispose) self._dispose(hit.key, hit.value)
|
314 | self._length -= hit.length
|
315 | self._itemCount --
|
316 | delete self._cache[ hit.key ]
|
317 | shiftLU(self, hit)
|
318 | }
|
319 | }
|
320 |
|
321 |
|
322 | function Entry (key, value, lu, length, now, maxAge) {
|
323 | this.key = key
|
324 | this.value = value
|
325 | this.lu = lu
|
326 | this.length = length
|
327 | this.now = now
|
328 | if (maxAge) this.maxAge = maxAge
|
329 | }
|
330 |
|
331 | })()
|