index.js 8.0 KB

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