corrade-nucleus-nucleons – Blame information for rev 20

Subversion Repositories:
Rev:
Rev Author Line No. Line
20 office 1 module.exports = LRUCache
2  
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  
7 function naiveLength () { return 1 }
8  
9 function LRUCache (options) {
10 if (!(this instanceof LRUCache))
11 return new LRUCache(options)
12  
13 if (typeof options === 'number')
14 options = { max: options }
15  
16 if (!options)
17 options = {}
18  
19 this._max = options.max
20 // Kind of weird to have a default max of Infinity, but oh well.
21 if (!this._max || !(typeof this._max === "number") || this._max <= 0 )
22 this._max = Infinity
23  
24 this._lengthCalculator = options.length || naiveLength
25 if (typeof this._lengthCalculator !== "function")
26 this._lengthCalculator = naiveLength
27  
28 this._allowStale = options.stale || false
29 this._maxAge = options.maxAge || null
30 this._dispose = options.dispose
31 this.reset()
32 }
33  
34 // resize the cache when the max changes.
35 Object.defineProperty(LRUCache.prototype, "max",
36 { set : function (mL) {
37 if (!mL || !(typeof mL === "number") || mL <= 0 ) mL = Infinity
38 this._max = mL
39 if (this._length > this._max) trim(this)
40 }
41 , get : function () { return this._max }
42 , enumerable : true
43 })
44  
45 // resize the cache when the lengthCalculator changes.
46 Object.defineProperty(LRUCache.prototype, "lengthCalculator",
47 { set : function (lC) {
48 if (typeof lC !== "function") {
49 this._lengthCalculator = naiveLength
50 this._length = this._lruList.size
51 this._cache.forEach(function (value, key) {
52 value.length = 1
53 })
54 } else {
55 this._lengthCalculator = lC
56 this._length = 0
57 this._cache.forEach(function (value, key) {
58 value.length = this._lengthCalculator(value.value, key)
59 this._length += value.length
60 }, this)
61 }
62  
63 if (this._length > this._max) trim(this)
64 }
65 , get : function () { return this._lengthCalculator }
66 , enumerable : true
67 })
68  
69 Object.defineProperty(LRUCache.prototype, "length",
70 { get : function () { return this._length }
71 , enumerable : true
72 })
73  
74 Object.defineProperty(LRUCache.prototype, "itemCount",
75 { get : function () { return this._lruList.size }
76 , enumerable : true
77 })
78  
79 function reverseKeys (map) {
80 // keys live in lruList map in insertion order.
81 // we want them in reverse insertion order.
82 // flip the list of keys.
83 var itemCount = map.size
84 var keys = new Array(itemCount)
85 var i = itemCount
86 map.forEach(function (value, key) {
87 keys[--i] = key
88 })
89  
90 return keys
91 }
92  
93 LRUCache.prototype.rforEach = function (fn, thisp) {
94 thisp = thisp || this
95 this._lruList.forEach(function (hit) {
96 forEachStep(this, fn, hit, thisp)
97 }, this)
98 }
99  
100 function forEachStep (self, fn, hit, thisp) {
101 if (isStale(self, hit)) {
102 del(self, hit)
103 if (!self._allowStale) {
104 hit = undefined
105 }
106 }
107 if (hit) {
108 fn.call(thisp, hit.value, hit.key, self)
109 }
110 }
111  
112  
113 LRUCache.prototype.forEach = function (fn, thisp) {
114 thisp = thisp || this
115  
116 var keys = reverseKeys(this._lruList)
117 for (var k = 0; k < keys.length; k++) {
118 var hit = this._lruList.get(keys[k])
119 forEachStep(this, fn, hit, thisp)
120 }
121 }
122  
123 LRUCache.prototype.keys = function () {
124 return reverseKeys(this._lruList).map(function (k) {
125 return this._lruList.get(k).key
126 }, this)
127 }
128  
129 LRUCache.prototype.values = function () {
130 return reverseKeys(this._lruList).map(function (k) {
131 return this._lruList.get(k).value
132 }, this)
133 }
134  
135 LRUCache.prototype.reset = function () {
136 if (this._dispose && this._cache) {
137 this._cache.forEach(function (entry, key) {
138 this._dispose(key, entry.value)
139 }, this)
140 }
141  
142 this._cache = new Map() // hash of items by key
143 this._lruList = new Map() // list of items in order of use recency
144 this._mru = 0 // most recently used
145 this._lru = 0 // least recently used
146 this._length = 0 // number of items in the list
147 }
148  
149 LRUCache.prototype.dump = function () {
150 var arr = []
151 var i = 0
152 var size = this._lruList.size
153 return reverseKeys(this._lruList).map(function (k) {
154 var hit = this._lruList.get(k)
155 if (!isStale(this, hit)) {
156 return {
157 k: hit.key,
158 v: hit.value,
159 e: hit.now + (hit.maxAge || 0)
160 }
161 }
162 }, this).filter(function (h) {
163 return h
164 })
165 }
166  
167 LRUCache.prototype.dumpLru = function () {
168 return this._lruList
169 }
170  
171 LRUCache.prototype.set = function (key, value, maxAge) {
172 maxAge = maxAge || this._maxAge
173  
174 var now = maxAge ? Date.now() : 0
175 var len = this._lengthCalculator(value, key)
176  
177 if (this._cache.has(key)) {
178 if (len > this._max) {
179 del(this, this._cache.get(key))
180 return false
181 }
182  
183 var item = this._cache.get(key)
184  
185 // dispose of the old one before overwriting
186 if (this._dispose)
187 this._dispose(key, item.value)
188  
189 item.now = now
190 item.maxAge = maxAge
191 item.value = value
192 this._length += (len - item.length)
193 item.length = len
194 this.get(key)
195  
196 if (this._length > this._max)
197 trim(this)
198  
199 return true
200 }
201  
202 var hit = new Entry(key, value, this._mru, len, now, maxAge)
203 incMru(this)
204  
205 // oversized objects fall out of cache automatically.
206 if (hit.length > this._max) {
207 if (this._dispose) this._dispose(key, value)
208 return false
209 }
210  
211 this._length += hit.length
212 this._cache.set(key, hit)
213 this._lruList.set(hit.lu, hit)
214  
215 if (this._length > this._max)
216 trim(this)
217  
218 return true
219 }
220  
221 LRUCache.prototype.has = function (key) {
222 if (!this._cache.has(key)) return false
223 var hit = this._cache.get(key)
224 if (isStale(this, hit)) {
225 return false
226 }
227 return true
228 }
229  
230 LRUCache.prototype.get = function (key) {
231 return get(this, key, true)
232 }
233  
234 LRUCache.prototype.peek = function (key) {
235 return get(this, key, false)
236 }
237  
238 LRUCache.prototype.pop = function () {
239 var hit = this._lruList.get(this._lru)
240 del(this, hit)
241 return hit || null
242 }
243  
244 LRUCache.prototype.del = function (key) {
245 del(this, this._cache.get(key))
246 }
247  
248 LRUCache.prototype.load = function (arr) {
249 //reset the cache
250 this.reset();
251  
252 var now = Date.now()
253 // A previous serialized cache has the most recent items first
254 for (var l = arr.length - 1; l >= 0; l--) {
255 var hit = arr[l]
256 var expiresAt = hit.e || 0
257 if (expiresAt === 0) {
258 // the item was created without expiration in a non aged cache
259 this.set(hit.k, hit.v)
260 } else {
261 var maxAge = expiresAt - now
262 // dont add already expired items
263 if (maxAge > 0) {
264 this.set(hit.k, hit.v, maxAge)
265 }
266 }
267 }
268 }
269  
270 function get (self, key, doUse) {
271 var hit = self._cache.get(key)
272 if (hit) {
273 if (isStale(self, hit)) {
274 del(self, hit)
275 if (!self._allowStale) hit = undefined
276 } else {
277 if (doUse) use(self, hit)
278 }
279 if (hit) hit = hit.value
280 }
281 return hit
282 }
283  
284 function isStale(self, hit) {
285 if (!hit || (!hit.maxAge && !self._maxAge)) return false
286 var stale = false;
287 var diff = Date.now() - hit.now
288 if (hit.maxAge) {
289 stale = diff > hit.maxAge
290 } else {
291 stale = self._maxAge && (diff > self._maxAge)
292 }
293 return stale;
294 }
295  
296 function use (self, hit) {
297 shiftLU(self, hit)
298 hit.lu = self._mru
299 incMru(self)
300 self._lruList.set(hit.lu, hit)
301 }
302  
303 function trim (self) {
304 if (self._length > self._max) {
305 var keys = reverseKeys(self._lruList)
306 for (var k = keys.length - 1; self._length > self._max; k--) {
307 // We know that we're about to delete this one, and also
308 // what the next least recently used key will be, so just
309 // go ahead and set it now.
310 self._lru = keys[k - 1]
311 del(self, self._lruList.get(keys[k]))
312 }
313 }
314 }
315  
316 function shiftLU (self, hit) {
317 self._lruList.delete(hit.lu)
318 if (hit.lu === self._lru)
319 self._lru = reverseKeys(self._lruList).pop()
320 }
321  
322 function del (self, hit) {
323 if (hit) {
324 if (self._dispose) self._dispose(hit.key, hit.value)
325 self._length -= hit.length
326 self._cache.delete(hit.key)
327 shiftLU(self, hit)
328 }
329 }
330  
331 // classy, since V8 prefers predictable objects.
332 function Entry (key, value, lu, length, now, maxAge) {
333 this.key = key
334 this.value = value
335 this.lu = lu
336 this.length = length
337 this.now = now
338 if (maxAge) this.maxAge = maxAge
339 }
340  
341  
342 // Incrementers and decrementers that loop at MAX_SAFE_INTEGER
343 // only relevant for the lu, lru, and mru counters, since they
344 // get touched a lot and can get very large. Also, since they
345 // only go upwards, and the sets will tend to be much smaller than
346 // the max, we can very well assume that a very small number comes
347 // after a very large number, rather than before it.
348 var maxSafeInt = Number.MAX_SAFE_INTEGER || 9007199254740991
349 function intInc (number) {
350 return (number === maxSafeInt) ? 0 : number + 1
351 }
352 function incMru (self) {
353 do {
354 self._mru = intInc(self._mru)
355 } while (self._lruList.has(self._mru))
356 }