www.aleph1.co.uk Git - yaffs-website/blob - node_modules/cross-spawn/node_modules/lru-cache/lib/lru-cache.js

   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 var util = require('util')
   7
   8 // A linked list to keep track of recently-used-ness
   9 var Yallist = require('yallist')
  10
  11 // use symbols if possible, otherwise just _props
  12 var symbols = {}
  13 var hasSymbol = typeof Symbol === 'function'
  14 var makeSymbol
  15 /* istanbul ignore if */
  16 if (hasSymbol) {
  17   makeSymbol = function (key) {
  18     return Symbol.for(key)
  19   }
  20 } else {
  21   makeSymbol = function (key) {
  22     return '_' + key
  23   }
  24 }
  25
  26 function priv (obj, key, val) {
  27   var sym
  28   if (symbols[key]) {
  29     sym = symbols[key]
  30   } else {
  31     sym = makeSymbol(key)
  32     symbols[key] = sym
  33   }
  34   if (arguments.length === 2) {
  35     return obj[sym]
  36   } else {
  37     obj[sym] = val
  38     return val
  39   }
  40 }
  41
  42 function naiveLength () { return 1 }
  43
  44 // lruList is a yallist where the head is the youngest
  45 // item, and the tail is the oldest.  the list contains the Hit
  46 // objects as the entries.
  47 // Each Hit object has a reference to its Yallist.Node.  This
  48 // never changes.
  49 //
  50 // cache is a Map (or PseudoMap) that matches the keys to
  51 // the Yallist.Node object.
  52 function LRUCache (options) {
  53   if (!(this instanceof LRUCache)) {
  54     return new LRUCache(options)
  55   }
  56
  57   if (typeof options === 'number') {
  58     options = { max: options }
  59   }
  60
  61   if (!options) {
  62     options = {}
  63   }
  64
  65   var max = priv(this, 'max', options.max)
  66   // Kind of weird to have a default max of Infinity, but oh well.
  67   if (!max ||
  68       !(typeof max === 'number') ||
  69       max <= 0) {
  70     priv(this, 'max', Infinity)
  71   }
  72
  73   var lc = options.length || naiveLength
  74   if (typeof lc !== 'function') {
  75     lc = naiveLength
  76   }
  77   priv(this, 'lengthCalculator', lc)
  78
  79   priv(this, 'allowStale', options.stale || false)
  80   priv(this, 'maxAge', options.maxAge || 0)
  81   priv(this, 'dispose', options.dispose)
  82   this.reset()
  83 }
  84
  85 // resize the cache when the max changes.
  86 Object.defineProperty(LRUCache.prototype, 'max', {
  87   set: function (mL) {
  88     if (!mL || !(typeof mL === 'number') || mL <= 0) {
  89       mL = Infinity
  90     }
  91     priv(this, 'max', mL)
  92     trim(this)
  93   },
  94   get: function () {
  95     return priv(this, 'max')
  96   },
  97   enumerable: true
  98 })
  99
 100 Object.defineProperty(LRUCache.prototype, 'allowStale', {
 101   set: function (allowStale) {
 102     priv(this, 'allowStale', !!allowStale)
 103   },
 104   get: function () {
 105     return priv(this, 'allowStale')
 106   },
 107   enumerable: true
 108 })
 109
 110 Object.defineProperty(LRUCache.prototype, 'maxAge', {
 111   set: function (mA) {
 112     if (!mA || !(typeof mA === 'number') || mA < 0) {
 113       mA = 0
 114     }
 115     priv(this, 'maxAge', mA)
 116     trim(this)
 117   },
 118   get: function () {
 119     return priv(this, 'maxAge')
 120   },
 121   enumerable: true
 122 })
 123
 124 // resize the cache when the lengthCalculator changes.
 125 Object.defineProperty(LRUCache.prototype, 'lengthCalculator', {
 126   set: function (lC) {
 127     if (typeof lC !== 'function') {
 128       lC = naiveLength
 129     }
 130     if (lC !== priv(this, 'lengthCalculator')) {
 131       priv(this, 'lengthCalculator', lC)
 132       priv(this, 'length', 0)
 133       priv(this, 'lruList').forEach(function (hit) {
 134         hit.length = priv(this, 'lengthCalculator').call(this, hit.value, hit.key)
 135         priv(this, 'length', priv(this, 'length') + hit.length)
 136       }, this)
 137     }
 138     trim(this)
 139   },
 140   get: function () { return priv(this, 'lengthCalculator') },
 141   enumerable: true
 142 })
 143
 144 Object.defineProperty(LRUCache.prototype, 'length', {
 145   get: function () { return priv(this, 'length') },
 146   enumerable: true
 147 })
 148
 149 Object.defineProperty(LRUCache.prototype, 'itemCount', {
 150   get: function () { return priv(this, 'lruList').length },
 151   enumerable: true
 152 })
 153
 154 LRUCache.prototype.rforEach = function (fn, thisp) {
 155   thisp = thisp || this
 156   for (var walker = priv(this, 'lruList').tail; walker !== null;) {
 157     var prev = walker.prev
 158     forEachStep(this, fn, walker, thisp)
 159     walker = prev
 160   }
 161 }
 162
 163 function forEachStep (self, fn, node, thisp) {
 164   var hit = node.value
 165   if (isStale(self, hit)) {
 166     del(self, node)
 167     if (!priv(self, 'allowStale')) {
 168       hit = undefined
 169     }
 170   }
 171   if (hit) {
 172     fn.call(thisp, hit.value, hit.key, self)
 173   }
 174 }
 175
 176 LRUCache.prototype.forEach = function (fn, thisp) {
 177   thisp = thisp || this
 178   for (var walker = priv(this, 'lruList').head; walker !== null;) {
 179     var next = walker.next
 180     forEachStep(this, fn, walker, thisp)
 181     walker = next
 182   }
 183 }
 184
 185 LRUCache.prototype.keys = function () {
 186   return priv(this, 'lruList').toArray().map(function (k) {
 187     return k.key
 188   }, this)
 189 }
 190
 191 LRUCache.prototype.values = function () {
 192   return priv(this, 'lruList').toArray().map(function (k) {
 193     return k.value
 194   }, this)
 195 }
 196
 197 LRUCache.prototype.reset = function () {
 198   if (priv(this, 'dispose') &&
 199       priv(this, 'lruList') &&
 200       priv(this, 'lruList').length) {
 201     priv(this, 'lruList').forEach(function (hit) {
 202       priv(this, 'dispose').call(this, hit.key, hit.value)
 203     }, this)
 204   }
 205
 206   priv(this, 'cache', new Map()) // hash of items by key
 207   priv(this, 'lruList', new Yallist()) // list of items in order of use recency
 208   priv(this, 'length', 0) // length of items in the list
 209 }
 210
 211 LRUCache.prototype.dump = function () {
 212   return priv(this, 'lruList').map(function (hit) {
 213     if (!isStale(this, hit)) {
 214       return {
 215         k: hit.key,
 216         v: hit.value,
 217         e: hit.now + (hit.maxAge || 0)
 218       }
 219     }
 220   }, this).toArray().filter(function (h) {
 221     return h
 222   })
 223 }
 224
 225 LRUCache.prototype.dumpLru = function () {
 226   return priv(this, 'lruList')
 227 }
 228
 229 LRUCache.prototype.inspect = function (n, opts) {
 230   var str = 'LRUCache {'
 231   var extras = false
 232
 233   var as = priv(this, 'allowStale')
 234   if (as) {
 235     str += '\n  allowStale: true'
 236     extras = true
 237   }
 238
 239   var max = priv(this, 'max')
 240   if (max && max !== Infinity) {
 241     if (extras) {
 242       str += ','
 243     }
 244     str += '\n  max: ' + util.inspect(max, opts)
 245     extras = true
 246   }
 247
 248   var maxAge = priv(this, 'maxAge')
 249   if (maxAge) {
 250     if (extras) {
 251       str += ','
 252     }
 253     str += '\n  maxAge: ' + util.inspect(maxAge, opts)
 254     extras = true
 255   }
 256
 257   var lc = priv(this, 'lengthCalculator')
 258   if (lc && lc !== naiveLength) {
 259     if (extras) {
 260       str += ','
 261     }
 262     str += '\n  length: ' + util.inspect(priv(this, 'length'), opts)
 263     extras = true
 264   }
 265
 266   var didFirst = false
 267   priv(this, 'lruList').forEach(function (item) {
 268     if (didFirst) {
 269       str += ',\n  '
 270     } else {
 271       if (extras) {
 272         str += ',\n'
 273       }
 274       didFirst = true
 275       str += '\n  '
 276     }
 277     var key = util.inspect(item.key).split('\n').join('\n  ')
 278     var val = { value: item.value }
 279     if (item.maxAge !== maxAge) {
 280       val.maxAge = item.maxAge
 281     }
 282     if (lc !== naiveLength) {
 283       val.length = item.length
 284     }
 285     if (isStale(this, item)) {
 286       val.stale = true
 287     }
 288
 289     val = util.inspect(val, opts).split('\n').join('\n  ')
 290     str += key + ' => ' + val
 291   })
 292
 293   if (didFirst || extras) {
 294     str += '\n'
 295   }
 296   str += '}'
 297
 298   return str
 299 }
 300
 301 LRUCache.prototype.set = function (key, value, maxAge) {
 302   maxAge = maxAge || priv(this, 'maxAge')
 303
 304   var now = maxAge ? Date.now() : 0
 305   var len = priv(this, 'lengthCalculator').call(this, value, key)
 306
 307   if (priv(this, 'cache').has(key)) {
 308     if (len > priv(this, 'max')) {
 309       del(this, priv(this, 'cache').get(key))
 310       return false
 311     }
 312
 313     var node = priv(this, 'cache').get(key)
 314     var item = node.value
 315
 316     // dispose of the old one before overwriting
 317     if (priv(this, 'dispose')) {
 318       priv(this, 'dispose').call(this, key, item.value)
 319     }
 320
 321     item.now = now
 322     item.maxAge = maxAge
 323     item.value = value
 324     priv(this, 'length', priv(this, 'length') + (len - item.length))
 325     item.length = len
 326     this.get(key)
 327     trim(this)
 328     return true
 329   }
 330
 331   var hit = new Entry(key, value, len, now, maxAge)
 332
 333   // oversized objects fall out of cache automatically.
 334   if (hit.length > priv(this, 'max')) {
 335     if (priv(this, 'dispose')) {
 336       priv(this, 'dispose').call(this, key, value)
 337     }
 338     return false
 339   }
 340
 341   priv(this, 'length', priv(this, 'length') + hit.length)
 342   priv(this, 'lruList').unshift(hit)
 343   priv(this, 'cache').set(key, priv(this, 'lruList').head)
 344   trim(this)
 345   return true
 346 }
 347
 348 LRUCache.prototype.has = function (key) {
 349   if (!priv(this, 'cache').has(key)) return false
 350   var hit = priv(this, 'cache').get(key).value
 351   if (isStale(this, hit)) {
 352     return false
 353   }
 354   return true
 355 }
 356
 357 LRUCache.prototype.get = function (key) {
 358   return get(this, key, true)
 359 }
 360
 361 LRUCache.prototype.peek = function (key) {
 362   return get(this, key, false)
 363 }
 364
 365 LRUCache.prototype.pop = function () {
 366   var node = priv(this, 'lruList').tail
 367   if (!node) return null
 368   del(this, node)
 369   return node.value
 370 }
 371
 372 LRUCache.prototype.del = function (key) {
 373   del(this, priv(this, 'cache').get(key))
 374 }
 375
 376 LRUCache.prototype.load = function (arr) {
 377   // reset the cache
 378   this.reset()
 379
 380   var now = Date.now()
 381   // A previous serialized cache has the most recent items first
 382   for (var l = arr.length - 1; l >= 0; l--) {
 383     var hit = arr[l]
 384     var expiresAt = hit.e || 0
 385     if (expiresAt === 0) {
 386       // the item was created without expiration in a non aged cache
 387       this.set(hit.k, hit.v)
 388     } else {
 389       var maxAge = expiresAt - now
 390       // dont add already expired items
 391       if (maxAge > 0) {
 392         this.set(hit.k, hit.v, maxAge)
 393       }
 394     }
 395   }
 396 }
 397
 398 LRUCache.prototype.prune = function () {
 399   var self = this
 400   priv(this, 'cache').forEach(function (value, key) {
 401     get(self, key, false)
 402   })
 403 }
 404
 405 function get (self, key, doUse) {
 406   var node = priv(self, 'cache').get(key)
 407   if (node) {
 408     var hit = node.value
 409     if (isStale(self, hit)) {
 410       del(self, node)
 411       if (!priv(self, 'allowStale')) hit = undefined
 412     } else {
 413       if (doUse) {
 414         priv(self, 'lruList').unshiftNode(node)
 415       }
 416     }
 417     if (hit) hit = hit.value
 418   }
 419   return hit
 420 }
 421
 422 function isStale (self, hit) {
 423   if (!hit || (!hit.maxAge && !priv(self, 'maxAge'))) {
 424     return false
 425   }
 426   var stale = false
 427   var diff = Date.now() - hit.now
 428   if (hit.maxAge) {
 429     stale = diff > hit.maxAge
 430   } else {
 431     stale = priv(self, 'maxAge') && (diff > priv(self, 'maxAge'))
 432   }
 433   return stale
 434 }
 435
 436 function trim (self) {
 437   if (priv(self, 'length') > priv(self, 'max')) {
 438     for (var walker = priv(self, 'lruList').tail;
 439          priv(self, 'length') > priv(self, 'max') && walker !== null;) {
 440       // We know that we're about to delete this one, and also
 441       // what the next least recently used key will be, so just
 442       // go ahead and set it now.
 443       var prev = walker.prev
 444       del(self, walker)
 445       walker = prev
 446     }
 447   }
 448 }
 449
 450 function del (self, node) {
 451   if (node) {
 452     var hit = node.value
 453     if (priv(self, 'dispose')) {
 454       priv(self, 'dispose').call(this, hit.key, hit.value)
 455     }
 456     priv(self, 'length', priv(self, 'length') - hit.length)
 457     priv(self, 'cache').delete(hit.key)
 458     priv(self, 'lruList').removeNode(node)
 459   }
 460 }
 461
 462 // classy, since V8 prefers predictable objects.
 463 function Entry (key, value, length, now, maxAge) {
 464   this.key = key
 465   this.value = value
 466   this.length = length
 467   this.now = now
 468   this.maxAge = maxAge || 0
 469 }