index.js 10 KB

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