source: trip-planner-front/node_modules/lru-cache/index.js@ 1ad8e64

Last change on this file since 1ad8e64 was 6a3a178, checked in by Ema <ema_spirova@…>, 3 years ago

initial commit

  • Property mode set to 100644
File size: 8.0 KB
Line 
1'use strict'
2
3// A linked list to keep track of recently-used-ness
4const Yallist = require('yallist')
5
6const MAX = Symbol('max')
7const LENGTH = Symbol('length')
8const LENGTH_CALCULATOR = Symbol('lengthCalculator')
9const ALLOW_STALE = Symbol('allowStale')
10const MAX_AGE = Symbol('maxAge')
11const DISPOSE = Symbol('dispose')
12const NO_DISPOSE_ON_SET = Symbol('noDisposeOnSet')
13const LRU_LIST = Symbol('lruList')
14const CACHE = Symbol('cache')
15const UPDATE_AGE_ON_GET = Symbol('updateAgeOnGet')
16
17const naiveLength = () => 1
18
19// lruList is a yallist where the head is the youngest
20// item, and the tail is the oldest. the list contains the Hit
21// objects as the entries.
22// Each Hit object has a reference to its Yallist.Node. This
23// never changes.
24//
25// cache is a Map (or PseudoMap) that matches the keys to
26// the Yallist.Node object.
27class LRUCache {
28 constructor (options) {
29 if (typeof options === 'number')
30 options = { max: options }
31
32 if (!options)
33 options = {}
34
35 if (options.max && (typeof options.max !== 'number' || options.max < 0))
36 throw new TypeError('max must be a non-negative number')
37 // Kind of weird to have a default max of Infinity, but oh well.
38 const max = this[MAX] = options.max || Infinity
39
40 const lc = options.length || naiveLength
41 this[LENGTH_CALCULATOR] = (typeof lc !== 'function') ? naiveLength : lc
42 this[ALLOW_STALE] = options.stale || false
43 if (options.maxAge && typeof options.maxAge !== 'number')
44 throw new TypeError('maxAge must be a number')
45 this[MAX_AGE] = options.maxAge || 0
46 this[DISPOSE] = options.dispose
47 this[NO_DISPOSE_ON_SET] = options.noDisposeOnSet || false
48 this[UPDATE_AGE_ON_GET] = options.updateAgeOnGet || false
49 this.reset()
50 }
51
52 // resize the cache when the max changes.
53 set max (mL) {
54 if (typeof mL !== 'number' || mL < 0)
55 throw new TypeError('max must be a non-negative number')
56
57 this[MAX] = mL || Infinity
58 trim(this)
59 }
60 get max () {
61 return this[MAX]
62 }
63
64 set allowStale (allowStale) {
65 this[ALLOW_STALE] = !!allowStale
66 }
67 get allowStale () {
68 return this[ALLOW_STALE]
69 }
70
71 set maxAge (mA) {
72 if (typeof mA !== 'number')
73 throw new TypeError('maxAge must be a non-negative number')
74
75 this[MAX_AGE] = mA
76 trim(this)
77 }
78 get maxAge () {
79 return this[MAX_AGE]
80 }
81
82 // resize the cache when the lengthCalculator changes.
83 set lengthCalculator (lC) {
84 if (typeof lC !== 'function')
85 lC = naiveLength
86
87 if (lC !== this[LENGTH_CALCULATOR]) {
88 this[LENGTH_CALCULATOR] = lC
89 this[LENGTH] = 0
90 this[LRU_LIST].forEach(hit => {
91 hit.length = this[LENGTH_CALCULATOR](hit.value, hit.key)
92 this[LENGTH] += hit.length
93 })
94 }
95 trim(this)
96 }
97 get lengthCalculator () { return this[LENGTH_CALCULATOR] }
98
99 get length () { return this[LENGTH] }
100 get itemCount () { return this[LRU_LIST].length }
101
102 rforEach (fn, thisp) {
103 thisp = thisp || this
104 for (let walker = this[LRU_LIST].tail; walker !== null;) {
105 const prev = walker.prev
106 forEachStep(this, fn, walker, thisp)
107 walker = prev
108 }
109 }
110
111 forEach (fn, thisp) {
112 thisp = thisp || this
113 for (let walker = this[LRU_LIST].head; walker !== null;) {
114 const next = walker.next
115 forEachStep(this, fn, walker, thisp)
116 walker = next
117 }
118 }
119
120 keys () {
121 return this[LRU_LIST].toArray().map(k => k.key)
122 }
123
124 values () {
125 return this[LRU_LIST].toArray().map(k => k.value)
126 }
127
128 reset () {
129 if (this[DISPOSE] &&
130 this[LRU_LIST] &&
131 this[LRU_LIST].length) {
132 this[LRU_LIST].forEach(hit => this[DISPOSE](hit.key, hit.value))
133 }
134
135 this[CACHE] = new Map() // hash of items by key
136 this[LRU_LIST] = new Yallist() // list of items in order of use recency
137 this[LENGTH] = 0 // length of items in the list
138 }
139
140 dump () {
141 return this[LRU_LIST].map(hit =>
142 isStale(this, hit) ? false : {
143 k: hit.key,
144 v: hit.value,
145 e: hit.now + (hit.maxAge || 0)
146 }).toArray().filter(h => h)
147 }
148
149 dumpLru () {
150 return this[LRU_LIST]
151 }
152
153 set (key, value, maxAge) {
154 maxAge = maxAge || this[MAX_AGE]
155
156 if (maxAge && typeof maxAge !== 'number')
157 throw new TypeError('maxAge must be a number')
158
159 const now = maxAge ? Date.now() : 0
160 const len = this[LENGTH_CALCULATOR](value, key)
161
162 if (this[CACHE].has(key)) {
163 if (len > this[MAX]) {
164 del(this, this[CACHE].get(key))
165 return false
166 }
167
168 const node = this[CACHE].get(key)
169 const item = node.value
170
171 // dispose of the old one before overwriting
172 // split out into 2 ifs for better coverage tracking
173 if (this[DISPOSE]) {
174 if (!this[NO_DISPOSE_ON_SET])
175 this[DISPOSE](key, item.value)
176 }
177
178 item.now = now
179 item.maxAge = maxAge
180 item.value = value
181 this[LENGTH] += len - item.length
182 item.length = len
183 this.get(key)
184 trim(this)
185 return true
186 }
187
188 const hit = new Entry(key, value, len, now, maxAge)
189
190 // oversized objects fall out of cache automatically.
191 if (hit.length > this[MAX]) {
192 if (this[DISPOSE])
193 this[DISPOSE](key, value)
194
195 return false
196 }
197
198 this[LENGTH] += hit.length
199 this[LRU_LIST].unshift(hit)
200 this[CACHE].set(key, this[LRU_LIST].head)
201 trim(this)
202 return true
203 }
204
205 has (key) {
206 if (!this[CACHE].has(key)) return false
207 const hit = this[CACHE].get(key).value
208 return !isStale(this, hit)
209 }
210
211 get (key) {
212 return get(this, key, true)
213 }
214
215 peek (key) {
216 return get(this, key, false)
217 }
218
219 pop () {
220 const node = this[LRU_LIST].tail
221 if (!node)
222 return null
223
224 del(this, node)
225 return node.value
226 }
227
228 del (key) {
229 del(this, this[CACHE].get(key))
230 }
231
232 load (arr) {
233 // reset the cache
234 this.reset()
235
236 const now = Date.now()
237 // A previous serialized cache has the most recent items first
238 for (let l = arr.length - 1; l >= 0; l--) {
239 const hit = arr[l]
240 const expiresAt = hit.e || 0
241 if (expiresAt === 0)
242 // the item was created without expiration in a non aged cache
243 this.set(hit.k, hit.v)
244 else {
245 const maxAge = expiresAt - now
246 // dont add already expired items
247 if (maxAge > 0) {
248 this.set(hit.k, hit.v, maxAge)
249 }
250 }
251 }
252 }
253
254 prune () {
255 this[CACHE].forEach((value, key) => get(this, key, false))
256 }
257}
258
259const get = (self, key, doUse) => {
260 const node = self[CACHE].get(key)
261 if (node) {
262 const hit = node.value
263 if (isStale(self, hit)) {
264 del(self, node)
265 if (!self[ALLOW_STALE])
266 return undefined
267 } else {
268 if (doUse) {
269 if (self[UPDATE_AGE_ON_GET])
270 node.value.now = Date.now()
271 self[LRU_LIST].unshiftNode(node)
272 }
273 }
274 return hit.value
275 }
276}
277
278const isStale = (self, hit) => {
279 if (!hit || (!hit.maxAge && !self[MAX_AGE]))
280 return false
281
282 const diff = Date.now() - hit.now
283 return hit.maxAge ? diff > hit.maxAge
284 : self[MAX_AGE] && (diff > self[MAX_AGE])
285}
286
287const trim = self => {
288 if (self[LENGTH] > self[MAX]) {
289 for (let walker = self[LRU_LIST].tail;
290 self[LENGTH] > self[MAX] && walker !== null;) {
291 // We know that we're about to delete this one, and also
292 // what the next least recently used key will be, so just
293 // go ahead and set it now.
294 const prev = walker.prev
295 del(self, walker)
296 walker = prev
297 }
298 }
299}
300
301const del = (self, node) => {
302 if (node) {
303 const hit = node.value
304 if (self[DISPOSE])
305 self[DISPOSE](hit.key, hit.value)
306
307 self[LENGTH] -= hit.length
308 self[CACHE].delete(hit.key)
309 self[LRU_LIST].removeNode(node)
310 }
311}
312
313class Entry {
314 constructor (key, value, length, now, maxAge) {
315 this.key = key
316 this.value = value
317 this.length = length
318 this.now = now
319 this.maxAge = maxAge || 0
320 }
321}
322
323const forEachStep = (self, fn, node, thisp) => {
324 let hit = node.value
325 if (isStale(self, hit)) {
326 del(self, node)
327 if (!self[ALLOW_STALE])
328 hit = undefined
329 }
330 if (hit)
331 fn.call(thisp, hit.value, hit.key, self)
332}
333
334module.exports = LRUCache
Note: See TracBrowser for help on using the repository browser.