lru-cache.js 8.0 KB

123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778798081828384858687888990919293949596979899100101102103104105106107108109110111112113114115116117118119120121122123124125126127128129130131132133134135136137138139140141142143144145146147148149150151152153154155156157158159160161162163164165166167168169170171172173174175176177178179180181182183184185186187188189190191192193194195196197198199200201202203204205206207208209210211212213214215216217218219220221222223224225226227228229230231232233234235236237238239240241242243244245246247248249250251252253254255256257258259260261262263264265266267268269270271272273274275276277278279280281282283284285286287288289290291292293294295296297298299300301302303304305306307308309310311312313314315316317318319320321322323324325326327328329330331332333334
  1. ;(function () { // closure for web browsers
  2. if (typeof module === 'object' && module.exports) {
  3. module.exports = LRUCache
  4. } else {
  5. // just set the global for non-node platforms.
  6. this.LRUCache = LRUCache
  7. }
  8. function hOP (obj, key) {
  9. return Object.prototype.hasOwnProperty.call(obj, key)
  10. }
  11. function naiveLength () { return 1 }
  12. var didTypeWarning = false
  13. function typeCheckKey(key) {
  14. if (!didTypeWarning && typeof key !== 'string' && typeof key !== 'number') {
  15. didTypeWarning = true
  16. console.error(new TypeError("LRU: key must be a string or number. Almost certainly a bug! " + typeof key).stack)
  17. }
  18. }
  19. function LRUCache (options) {
  20. if (!(this instanceof LRUCache))
  21. return new LRUCache(options)
  22. if (typeof options === 'number')
  23. options = { max: options }
  24. if (!options)
  25. options = {}
  26. this._max = options.max
  27. // Kind of weird to have a default max of Infinity, but oh well.
  28. if (!this._max || !(typeof this._max === "number") || this._max <= 0 )
  29. this._max = Infinity
  30. this._lengthCalculator = options.length || naiveLength
  31. if (typeof this._lengthCalculator !== "function")
  32. this._lengthCalculator = naiveLength
  33. this._allowStale = options.stale || false
  34. this._maxAge = options.maxAge || null
  35. this._dispose = options.dispose
  36. this.reset()
  37. }
  38. // resize the cache when the max changes.
  39. Object.defineProperty(LRUCache.prototype, "max",
  40. { set : function (mL) {
  41. if (!mL || !(typeof mL === "number") || mL <= 0 ) mL = Infinity
  42. this._max = mL
  43. if (this._length > this._max) trim(this)
  44. }
  45. , get : function () { return this._max }
  46. , enumerable : true
  47. })
  48. // resize the cache when the lengthCalculator changes.
  49. Object.defineProperty(LRUCache.prototype, "lengthCalculator",
  50. { set : function (lC) {
  51. if (typeof lC !== "function") {
  52. this._lengthCalculator = naiveLength
  53. this._length = this._itemCount
  54. for (var key in this._cache) {
  55. this._cache[key].length = 1
  56. }
  57. } else {
  58. this._lengthCalculator = lC
  59. this._length = 0
  60. for (var key in this._cache) {
  61. this._cache[key].length = this._lengthCalculator(this._cache[key].value)
  62. this._length += this._cache[key].length
  63. }
  64. }
  65. if (this._length > this._max) trim(this)
  66. }
  67. , get : function () { return this._lengthCalculator }
  68. , enumerable : true
  69. })
  70. Object.defineProperty(LRUCache.prototype, "length",
  71. { get : function () { return this._length }
  72. , enumerable : true
  73. })
  74. Object.defineProperty(LRUCache.prototype, "itemCount",
  75. { get : function () { return this._itemCount }
  76. , enumerable : true
  77. })
  78. LRUCache.prototype.forEach = function (fn, thisp) {
  79. thisp = thisp || this
  80. var i = 0
  81. var itemCount = this._itemCount
  82. for (var k = this._mru - 1; k >= 0 && i < itemCount; k--) if (this._lruList[k]) {
  83. i++
  84. var hit = this._lruList[k]
  85. if (isStale(this, hit)) {
  86. del(this, hit)
  87. if (!this._allowStale) hit = undefined
  88. }
  89. if (hit) {
  90. fn.call(thisp, hit.value, hit.key, this)
  91. }
  92. }
  93. }
  94. LRUCache.prototype.keys = function () {
  95. var keys = new Array(this._itemCount)
  96. var i = 0
  97. for (var k = this._mru - 1; k >= 0 && i < this._itemCount; k--) if (this._lruList[k]) {
  98. var hit = this._lruList[k]
  99. keys[i++] = hit.key
  100. }
  101. return keys
  102. }
  103. LRUCache.prototype.values = function () {
  104. var values = new Array(this._itemCount)
  105. var i = 0
  106. for (var k = this._mru - 1; k >= 0 && i < this._itemCount; k--) if (this._lruList[k]) {
  107. var hit = this._lruList[k]
  108. values[i++] = hit.value
  109. }
  110. return values
  111. }
  112. LRUCache.prototype.reset = function () {
  113. if (this._dispose && this._cache) {
  114. for (var k in this._cache) {
  115. this._dispose(k, this._cache[k].value)
  116. }
  117. }
  118. this._cache = Object.create(null) // hash of items by key
  119. this._lruList = Object.create(null) // list of items in order of use recency
  120. this._mru = 0 // most recently used
  121. this._lru = 0 // least recently used
  122. this._length = 0 // number of items in the list
  123. this._itemCount = 0
  124. }
  125. LRUCache.prototype.dump = function () {
  126. var arr = []
  127. var i = 0
  128. for (var k = this._mru - 1; k >= 0 && i < this._itemCount; k--) if (this._lruList[k]) {
  129. var hit = this._lruList[k]
  130. if (!isStale(this, hit)) {
  131. //Do not store staled hits
  132. ++i
  133. arr.push({
  134. k: hit.key,
  135. v: hit.value,
  136. e: hit.now + (hit.maxAge || 0)
  137. });
  138. }
  139. }
  140. //arr has the most read first
  141. return arr
  142. }
  143. LRUCache.prototype.dumpLru = function () {
  144. return this._lruList
  145. }
  146. LRUCache.prototype.set = function (key, value, maxAge) {
  147. maxAge = maxAge || this._maxAge
  148. typeCheckKey(key)
  149. var now = maxAge ? Date.now() : 0
  150. var len = this._lengthCalculator(value)
  151. if (hOP(this._cache, key)) {
  152. if (len > this._max) {
  153. del(this, this._cache[key])
  154. return false
  155. }
  156. // dispose of the old one before overwriting
  157. if (this._dispose)
  158. this._dispose(key, this._cache[key].value)
  159. this._cache[key].now = now
  160. this._cache[key].maxAge = maxAge
  161. this._cache[key].value = value
  162. this._length += (len - this._cache[key].length)
  163. this._cache[key].length = len
  164. this.get(key)
  165. if (this._length > this._max)
  166. trim(this)
  167. return true
  168. }
  169. var hit = new Entry(key, value, this._mru++, len, now, maxAge)
  170. // oversized objects fall out of cache automatically.
  171. if (hit.length > this._max) {
  172. if (this._dispose) this._dispose(key, value)
  173. return false
  174. }
  175. this._length += hit.length
  176. this._lruList[hit.lu] = this._cache[key] = hit
  177. this._itemCount ++
  178. if (this._length > this._max)
  179. trim(this)
  180. return true
  181. }
  182. LRUCache.prototype.has = function (key) {
  183. typeCheckKey(key)
  184. if (!hOP(this._cache, key)) return false
  185. var hit = this._cache[key]
  186. if (isStale(this, hit)) {
  187. return false
  188. }
  189. return true
  190. }
  191. LRUCache.prototype.get = function (key) {
  192. typeCheckKey(key)
  193. return get(this, key, true)
  194. }
  195. LRUCache.prototype.peek = function (key) {
  196. typeCheckKey(key)
  197. return get(this, key, false)
  198. }
  199. LRUCache.prototype.pop = function () {
  200. var hit = this._lruList[this._lru]
  201. del(this, hit)
  202. return hit || null
  203. }
  204. LRUCache.prototype.del = function (key) {
  205. typeCheckKey(key)
  206. del(this, this._cache[key])
  207. }
  208. LRUCache.prototype.load = function (arr) {
  209. //reset the cache
  210. this.reset();
  211. var now = Date.now()
  212. //A previous serialized cache has the most recent items first
  213. for (var l = arr.length - 1; l >= 0; l-- ) {
  214. var hit = arr[l]
  215. typeCheckKey(hit.k)
  216. var expiresAt = hit.e || 0
  217. if (expiresAt === 0) {
  218. //the item was created without expiration in a non aged cache
  219. this.set(hit.k, hit.v)
  220. } else {
  221. var maxAge = expiresAt - now
  222. //dont add already expired items
  223. if (maxAge > 0) this.set(hit.k, hit.v, maxAge)
  224. }
  225. }
  226. }
  227. function get (self, key, doUse) {
  228. typeCheckKey(key)
  229. var hit = self._cache[key]
  230. if (hit) {
  231. if (isStale(self, hit)) {
  232. del(self, hit)
  233. if (!self._allowStale) hit = undefined
  234. } else {
  235. if (doUse) use(self, hit)
  236. }
  237. if (hit) hit = hit.value
  238. }
  239. return hit
  240. }
  241. function isStale(self, hit) {
  242. if (!hit || (!hit.maxAge && !self._maxAge)) return false
  243. var stale = false;
  244. var diff = Date.now() - hit.now
  245. if (hit.maxAge) {
  246. stale = diff > hit.maxAge
  247. } else {
  248. stale = self._maxAge && (diff > self._maxAge)
  249. }
  250. return stale;
  251. }
  252. function use (self, hit) {
  253. shiftLU(self, hit)
  254. hit.lu = self._mru ++
  255. self._lruList[hit.lu] = hit
  256. }
  257. function trim (self) {
  258. while (self._lru < self._mru && self._length > self._max)
  259. del(self, self._lruList[self._lru])
  260. }
  261. function shiftLU (self, hit) {
  262. delete self._lruList[ hit.lu ]
  263. while (self._lru < self._mru && !self._lruList[self._lru]) self._lru ++
  264. }
  265. function del (self, hit) {
  266. if (hit) {
  267. if (self._dispose) self._dispose(hit.key, hit.value)
  268. self._length -= hit.length
  269. self._itemCount --
  270. delete self._cache[ hit.key ]
  271. shiftLU(self, hit)
  272. }
  273. }
  274. // classy, since V8 prefers predictable objects.
  275. function Entry (key, value, lu, length, now, maxAge) {
  276. this.key = key
  277. this.value = value
  278. this.lu = lu
  279. this.length = length
  280. this.now = now
  281. if (maxAge) this.maxAge = maxAge
  282. }
  283. })()