+++ /dev/null
-'use strict'
-
-// A linked list to keep track of recently-used-ness
-const Yallist = require('yallist')
-
-const MAX = Symbol('max')
-const LENGTH = Symbol('length')
-const LENGTH_CALCULATOR = Symbol('lengthCalculator')
-const ALLOW_STALE = Symbol('allowStale')
-const MAX_AGE = Symbol('maxAge')
-const DISPOSE = Symbol('dispose')
-const NO_DISPOSE_ON_SET = Symbol('noDisposeOnSet')
-const LRU_LIST = Symbol('lruList')
-const CACHE = Symbol('cache')
-const UPDATE_AGE_ON_GET = Symbol('updateAgeOnGet')
-
-const naiveLength = () => 1
-
-// lruList is a yallist where the head is the youngest
-// item, and the tail is the oldest. the list contains the Hit
-// objects as the entries.
-// Each Hit object has a reference to its Yallist.Node. This
-// never changes.
-//
-// cache is a Map (or PseudoMap) that matches the keys to
-// the Yallist.Node object.
-class LRUCache {
- constructor (options) {
- if (typeof options === 'number')
- options = { max: options }
-
- if (!options)
- options = {}
-
- if (options.max && (typeof options.max !== 'number' || options.max < 0))
- throw new TypeError('max must be a non-negative number')
- // Kind of weird to have a default max of Infinity, but oh well.
- const max = this[MAX] = options.max || Infinity
-
- const lc = options.length || naiveLength
- this[LENGTH_CALCULATOR] = (typeof lc !== 'function') ? naiveLength : lc
- this[ALLOW_STALE] = options.stale || false
- if (options.maxAge && typeof options.maxAge !== 'number')
- throw new TypeError('maxAge must be a number')
- this[MAX_AGE] = options.maxAge || 0
- this[DISPOSE] = options.dispose
- this[NO_DISPOSE_ON_SET] = options.noDisposeOnSet || false
- this[UPDATE_AGE_ON_GET] = options.updateAgeOnGet || false
- this.reset()
- }
-
- // resize the cache when the max changes.
- set max (mL) {
- if (typeof mL !== 'number' || mL < 0)
- throw new TypeError('max must be a non-negative number')
-
- this[MAX] = mL || Infinity
- trim(this)
- }
- get max () {
- return this[MAX]
- }
-
- set allowStale (allowStale) {
- this[ALLOW_STALE] = !!allowStale
- }
- get allowStale () {
- return this[ALLOW_STALE]
- }
-
- set maxAge (mA) {
- if (typeof mA !== 'number')
- throw new TypeError('maxAge must be a non-negative number')
-
- this[MAX_AGE] = mA
- trim(this)
- }
- get maxAge () {
- return this[MAX_AGE]
- }
-
- // resize the cache when the lengthCalculator changes.
- set lengthCalculator (lC) {
- if (typeof lC !== 'function')
- lC = naiveLength
-
- if (lC !== this[LENGTH_CALCULATOR]) {
- this[LENGTH_CALCULATOR] = lC
- this[LENGTH] = 0
- this[LRU_LIST].forEach(hit => {
- hit.length = this[LENGTH_CALCULATOR](hit.value, hit.key)
- this[LENGTH] += hit.length
- })
- }
- trim(this)
- }
- get lengthCalculator () { return this[LENGTH_CALCULATOR] }
-
- get length () { return this[LENGTH] }
- get itemCount () { return this[LRU_LIST].length }
-
- rforEach (fn, thisp) {
- thisp = thisp || this
- for (let walker = this[LRU_LIST].tail; walker !== null;) {
- const prev = walker.prev
- forEachStep(this, fn, walker, thisp)
- walker = prev
- }
- }
-
- forEach (fn, thisp) {
- thisp = thisp || this
- for (let walker = this[LRU_LIST].head; walker !== null;) {
- const next = walker.next
- forEachStep(this, fn, walker, thisp)
- walker = next
- }
- }
-
- keys () {
- return this[LRU_LIST].toArray().map(k => k.key)
- }
-
- values () {
- return this[LRU_LIST].toArray().map(k => k.value)
- }
-
- reset () {
- if (this[DISPOSE] &&
- this[LRU_LIST] &&
- this[LRU_LIST].length) {
- this[LRU_LIST].forEach(hit => this[DISPOSE](hit.key, hit.value))
- }
-
- this[CACHE] = new Map() // hash of items by key
- this[LRU_LIST] = new Yallist() // list of items in order of use recency
- this[LENGTH] = 0 // length of items in the list
- }
-
- dump () {
- return this[LRU_LIST].map(hit =>
- isStale(this, hit) ? false : {
- k: hit.key,
- v: hit.value,
- e: hit.now + (hit.maxAge || 0)
- }).toArray().filter(h => h)
- }
-
- dumpLru () {
- return this[LRU_LIST]
- }
-
- set (key, value, maxAge) {
- maxAge = maxAge || this[MAX_AGE]
-
- if (maxAge && typeof maxAge !== 'number')
- throw new TypeError('maxAge must be a number')
-
- const now = maxAge ? Date.now() : 0
- const len = this[LENGTH_CALCULATOR](value, key)
-
- if (this[CACHE].has(key)) {
- if (len > this[MAX]) {
- del(this, this[CACHE].get(key))
- return false
- }
-
- const node = this[CACHE].get(key)
- const item = node.value
-
- // dispose of the old one before overwriting
- // split out into 2 ifs for better coverage tracking
- if (this[DISPOSE]) {
- if (!this[NO_DISPOSE_ON_SET])
- this[DISPOSE](key, item.value)
- }
-
- item.now = now
- item.maxAge = maxAge
- item.value = value
- this[LENGTH] += len - item.length
- item.length = len
- this.get(key)
- trim(this)
- return true
- }
-
- const hit = new Entry(key, value, len, now, maxAge)
-
- // oversized objects fall out of cache automatically.
- if (hit.length > this[MAX]) {
- if (this[DISPOSE])
- this[DISPOSE](key, value)
-
- return false
- }
-
- this[LENGTH] += hit.length
- this[LRU_LIST].unshift(hit)
- this[CACHE].set(key, this[LRU_LIST].head)
- trim(this)
- return true
- }
-
- has (key) {
- if (!this[CACHE].has(key)) return false
- const hit = this[CACHE].get(key).value
- return !isStale(this, hit)
- }
-
- get (key) {
- return get(this, key, true)
- }
-
- peek (key) {
- return get(this, key, false)
- }
-
- pop () {
- const node = this[LRU_LIST].tail
- if (!node)
- return null
-
- del(this, node)
- return node.value
- }
-
- del (key) {
- del(this, this[CACHE].get(key))
- }
-
- load (arr) {
- // reset the cache
- this.reset()
-
- const now = Date.now()
- // A previous serialized cache has the most recent items first
- for (let l = arr.length - 1; l >= 0; l--) {
- const hit = arr[l]
- const expiresAt = hit.e || 0
- if (expiresAt === 0)
- // the item was created without expiration in a non aged cache
- this.set(hit.k, hit.v)
- else {
- const maxAge = expiresAt - now
- // dont add already expired items
- if (maxAge > 0) {
- this.set(hit.k, hit.v, maxAge)
- }
- }
- }
- }
-
- prune () {
- this[CACHE].forEach((value, key) => get(this, key, false))
- }
-}
-
-const get = (self, key, doUse) => {
- const node = self[CACHE].get(key)
- if (node) {
- const hit = node.value
- if (isStale(self, hit)) {
- del(self, node)
- if (!self[ALLOW_STALE])
- return undefined
- } else {
- if (doUse) {
- if (self[UPDATE_AGE_ON_GET])
- node.value.now = Date.now()
- self[LRU_LIST].unshiftNode(node)
- }
- }
- return hit.value
- }
-}
-
-const isStale = (self, hit) => {
- if (!hit || (!hit.maxAge && !self[MAX_AGE]))
- return false
-
- const diff = Date.now() - hit.now
- return hit.maxAge ? diff > hit.maxAge
- : self[MAX_AGE] && (diff > self[MAX_AGE])
-}
-
-const trim = self => {
- if (self[LENGTH] > self[MAX]) {
- for (let walker = self[LRU_LIST].tail;
- self[LENGTH] > self[MAX] && walker !== null;) {
- // We know that we're about to delete this one, and also
- // what the next least recently used key will be, so just
- // go ahead and set it now.
- const prev = walker.prev
- del(self, walker)
- walker = prev
- }
- }
-}
-
-const del = (self, node) => {
- if (node) {
- const hit = node.value
- if (self[DISPOSE])
- self[DISPOSE](hit.key, hit.value)
-
- self[LENGTH] -= hit.length
- self[CACHE].delete(hit.key)
- self[LRU_LIST].removeNode(node)
- }
-}
-
-class Entry {
- constructor (key, value, length, now, maxAge) {
- this.key = key
- this.value = value
- this.length = length
- this.now = now
- this.maxAge = maxAge || 0
- }
-}
-
-const forEachStep = (self, fn, node, thisp) => {
- let hit = node.value
- if (isStale(self, hit)) {
- del(self, node)
- if (!self[ALLOW_STALE])
- hit = undefined
- }
- if (hit)
- fn.call(thisp, hit.value, hit.key, self)
-}
-
-module.exports = LRUCache
projects / dotfiles / .git / blobdiff