This app provides monitoring and information features for the common freifunk user and the technical stuff of a freifunk community.
Code base is taken from a TUM Practical Course project and added here to see if Freifunk Altdorf can use it.
https://www.freifunk-altdorf.de
You can not select more than 25 topics
Topics must start with a letter or number, can include dashes ('-') and can be up to 35 characters long.
467 lines
10 KiB
467 lines
10 KiB
'use strict' |
|
|
|
module.exports = LRUCache |
|
|
|
// This will be a proper iterable 'Map' in engines that support it, |
|
// or a fakey-fake PseudoMap in older versions. |
|
var Map = require('pseudomap') |
|
var util = require('util') |
|
|
|
// A linked list to keep track of recently-used-ness |
|
var Yallist = require('yallist') |
|
|
|
// use symbols if possible, otherwise just _props |
|
var hasSymbol = typeof Symbol === 'function' |
|
var makeSymbol |
|
if (hasSymbol) { |
|
makeSymbol = function (key) { |
|
return Symbol(key) |
|
} |
|
} else { |
|
makeSymbol = function (key) { |
|
return '_' + key |
|
} |
|
} |
|
|
|
var MAX = makeSymbol('max') |
|
var LENGTH = makeSymbol('length') |
|
var LENGTH_CALCULATOR = makeSymbol('lengthCalculator') |
|
var ALLOW_STALE = makeSymbol('allowStale') |
|
var MAX_AGE = makeSymbol('maxAge') |
|
var DISPOSE = makeSymbol('dispose') |
|
var NO_DISPOSE_ON_SET = makeSymbol('noDisposeOnSet') |
|
var LRU_LIST = makeSymbol('lruList') |
|
var CACHE = makeSymbol('cache') |
|
|
|
function naiveLength () { return 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. |
|
function LRUCache (options) { |
|
if (!(this instanceof LRUCache)) { |
|
return new LRUCache(options) |
|
} |
|
|
|
if (typeof options === 'number') { |
|
options = { max: options } |
|
} |
|
|
|
if (!options) { |
|
options = {} |
|
} |
|
|
|
var max = this[MAX] = options.max |
|
// Kind of weird to have a default max of Infinity, but oh well. |
|
if (!max || |
|
!(typeof max === 'number') || |
|
max <= 0) { |
|
this[MAX] = Infinity |
|
} |
|
|
|
var lc = options.length || naiveLength |
|
if (typeof lc !== 'function') { |
|
lc = naiveLength |
|
} |
|
this[LENGTH_CALCULATOR] = lc |
|
|
|
this[ALLOW_STALE] = options.stale || false |
|
this[MAX_AGE] = options.maxAge || 0 |
|
this[DISPOSE] = options.dispose |
|
this[NO_DISPOSE_ON_SET] = options.noDisposeOnSet || false |
|
this.reset() |
|
} |
|
|
|
// resize the cache when the max changes. |
|
Object.defineProperty(LRUCache.prototype, 'max', { |
|
set: function (mL) { |
|
if (!mL || !(typeof mL === 'number') || mL <= 0) { |
|
mL = Infinity |
|
} |
|
this[MAX] = mL |
|
trim(this) |
|
}, |
|
get: function () { |
|
return this[MAX] |
|
}, |
|
enumerable: true |
|
}) |
|
|
|
Object.defineProperty(LRUCache.prototype, 'allowStale', { |
|
set: function (allowStale) { |
|
this[ALLOW_STALE] = !!allowStale |
|
}, |
|
get: function () { |
|
return this[ALLOW_STALE] |
|
}, |
|
enumerable: true |
|
}) |
|
|
|
Object.defineProperty(LRUCache.prototype, 'maxAge', { |
|
set: function (mA) { |
|
if (!mA || !(typeof mA === 'number') || mA < 0) { |
|
mA = 0 |
|
} |
|
this[MAX_AGE] = mA |
|
trim(this) |
|
}, |
|
get: function () { |
|
return this[MAX_AGE] |
|
}, |
|
enumerable: true |
|
}) |
|
|
|
// resize the cache when the lengthCalculator changes. |
|
Object.defineProperty(LRUCache.prototype, 'lengthCalculator', { |
|
set: function (lC) { |
|
if (typeof lC !== 'function') { |
|
lC = naiveLength |
|
} |
|
if (lC !== this[LENGTH_CALCULATOR]) { |
|
this[LENGTH_CALCULATOR] = lC |
|
this[LENGTH] = 0 |
|
this[LRU_LIST].forEach(function (hit) { |
|
hit.length = this[LENGTH_CALCULATOR](hit.value, hit.key) |
|
this[LENGTH] += hit.length |
|
}, this) |
|
} |
|
trim(this) |
|
}, |
|
get: function () { return this[LENGTH_CALCULATOR] }, |
|
enumerable: true |
|
}) |
|
|
|
Object.defineProperty(LRUCache.prototype, 'length', { |
|
get: function () { return this[LENGTH] }, |
|
enumerable: true |
|
}) |
|
|
|
Object.defineProperty(LRUCache.prototype, 'itemCount', { |
|
get: function () { return this[LRU_LIST].length }, |
|
enumerable: true |
|
}) |
|
|
|
LRUCache.prototype.rforEach = function (fn, thisp) { |
|
thisp = thisp || this |
|
for (var walker = this[LRU_LIST].tail; walker !== null;) { |
|
var prev = walker.prev |
|
forEachStep(this, fn, walker, thisp) |
|
walker = prev |
|
} |
|
} |
|
|
|
function forEachStep (self, fn, node, thisp) { |
|
var 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) |
|
} |
|
} |
|
|
|
LRUCache.prototype.forEach = function (fn, thisp) { |
|
thisp = thisp || this |
|
for (var walker = this[LRU_LIST].head; walker !== null;) { |
|
var next = walker.next |
|
forEachStep(this, fn, walker, thisp) |
|
walker = next |
|
} |
|
} |
|
|
|
LRUCache.prototype.keys = function () { |
|
return this[LRU_LIST].toArray().map(function (k) { |
|
return k.key |
|
}, this) |
|
} |
|
|
|
LRUCache.prototype.values = function () { |
|
return this[LRU_LIST].toArray().map(function (k) { |
|
return k.value |
|
}, this) |
|
} |
|
|
|
LRUCache.prototype.reset = function () { |
|
if (this[DISPOSE] && |
|
this[LRU_LIST] && |
|
this[LRU_LIST].length) { |
|
this[LRU_LIST].forEach(function (hit) { |
|
this[DISPOSE](hit.key, hit.value) |
|
}, this) |
|
} |
|
|
|
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 |
|
} |
|
|
|
LRUCache.prototype.dump = function () { |
|
return this[LRU_LIST].map(function (hit) { |
|
if (!isStale(this, hit)) { |
|
return { |
|
k: hit.key, |
|
v: hit.value, |
|
e: hit.now + (hit.maxAge || 0) |
|
} |
|
} |
|
}, this).toArray().filter(function (h) { |
|
return h |
|
}) |
|
} |
|
|
|
LRUCache.prototype.dumpLru = function () { |
|
return this[LRU_LIST] |
|
} |
|
|
|
LRUCache.prototype.inspect = function (n, opts) { |
|
var str = 'LRUCache {' |
|
var extras = false |
|
|
|
var as = this[ALLOW_STALE] |
|
if (as) { |
|
str += '\n allowStale: true' |
|
extras = true |
|
} |
|
|
|
var max = this[MAX] |
|
if (max && max !== Infinity) { |
|
if (extras) { |
|
str += ',' |
|
} |
|
str += '\n max: ' + util.inspect(max, opts) |
|
extras = true |
|
} |
|
|
|
var maxAge = this[MAX_AGE] |
|
if (maxAge) { |
|
if (extras) { |
|
str += ',' |
|
} |
|
str += '\n maxAge: ' + util.inspect(maxAge, opts) |
|
extras = true |
|
} |
|
|
|
var lc = this[LENGTH_CALCULATOR] |
|
if (lc && lc !== naiveLength) { |
|
if (extras) { |
|
str += ',' |
|
} |
|
str += '\n length: ' + util.inspect(this[LENGTH], opts) |
|
extras = true |
|
} |
|
|
|
var didFirst = false |
|
this[LRU_LIST].forEach(function (item) { |
|
if (didFirst) { |
|
str += ',\n ' |
|
} else { |
|
if (extras) { |
|
str += ',\n' |
|
} |
|
didFirst = true |
|
str += '\n ' |
|
} |
|
var key = util.inspect(item.key).split('\n').join('\n ') |
|
var val = { value: item.value } |
|
if (item.maxAge !== maxAge) { |
|
val.maxAge = item.maxAge |
|
} |
|
if (lc !== naiveLength) { |
|
val.length = item.length |
|
} |
|
if (isStale(this, item)) { |
|
val.stale = true |
|
} |
|
|
|
val = util.inspect(val, opts).split('\n').join('\n ') |
|
str += key + ' => ' + val |
|
}) |
|
|
|
if (didFirst || extras) { |
|
str += '\n' |
|
} |
|
str += '}' |
|
|
|
return str |
|
} |
|
|
|
LRUCache.prototype.set = function (key, value, maxAge) { |
|
maxAge = maxAge || this[MAX_AGE] |
|
|
|
var now = maxAge ? Date.now() : 0 |
|
var len = this[LENGTH_CALCULATOR](value, key) |
|
|
|
if (this[CACHE].has(key)) { |
|
if (len > this[MAX]) { |
|
del(this, this[CACHE].get(key)) |
|
return false |
|
} |
|
|
|
var node = this[CACHE].get(key) |
|
var 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 |
|
} |
|
|
|
var 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 |
|
} |
|
|
|
LRUCache.prototype.has = function (key) { |
|
if (!this[CACHE].has(key)) return false |
|
var hit = this[CACHE].get(key).value |
|
if (isStale(this, hit)) { |
|
return false |
|
} |
|
return true |
|
} |
|
|
|
LRUCache.prototype.get = function (key) { |
|
return get(this, key, true) |
|
} |
|
|
|
LRUCache.prototype.peek = function (key) { |
|
return get(this, key, false) |
|
} |
|
|
|
LRUCache.prototype.pop = function () { |
|
var node = this[LRU_LIST].tail |
|
if (!node) return null |
|
del(this, node) |
|
return node.value |
|
} |
|
|
|
LRUCache.prototype.del = function (key) { |
|
del(this, this[CACHE].get(key)) |
|
} |
|
|
|
LRUCache.prototype.load = function (arr) { |
|
// reset the cache |
|
this.reset() |
|
|
|
var now = Date.now() |
|
// A previous serialized cache has the most recent items first |
|
for (var l = arr.length - 1; l >= 0; l--) { |
|
var hit = arr[l] |
|
var 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 { |
|
var maxAge = expiresAt - now |
|
// dont add already expired items |
|
if (maxAge > 0) { |
|
this.set(hit.k, hit.v, maxAge) |
|
} |
|
} |
|
} |
|
} |
|
|
|
LRUCache.prototype.prune = function () { |
|
var self = this |
|
this[CACHE].forEach(function (value, key) { |
|
get(self, key, false) |
|
}) |
|
} |
|
|
|
function get (self, key, doUse) { |
|
var node = self[CACHE].get(key) |
|
if (node) { |
|
var hit = node.value |
|
if (isStale(self, hit)) { |
|
del(self, node) |
|
if (!self[ALLOW_STALE]) hit = undefined |
|
} else { |
|
if (doUse) { |
|
self[LRU_LIST].unshiftNode(node) |
|
} |
|
} |
|
if (hit) hit = hit.value |
|
} |
|
return hit |
|
} |
|
|
|
function isStale (self, hit) { |
|
if (!hit || (!hit.maxAge && !self[MAX_AGE])) { |
|
return false |
|
} |
|
var stale = false |
|
var diff = Date.now() - hit.now |
|
if (hit.maxAge) { |
|
stale = diff > hit.maxAge |
|
} else { |
|
stale = self[MAX_AGE] && (diff > self[MAX_AGE]) |
|
} |
|
return stale |
|
} |
|
|
|
function trim (self) { |
|
if (self[LENGTH] > self[MAX]) { |
|
for (var 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. |
|
var prev = walker.prev |
|
del(self, walker) |
|
walker = prev |
|
} |
|
} |
|
} |
|
|
|
function del (self, node) { |
|
if (node) { |
|
var 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) |
|
} |
|
} |
|
|
|
// classy, since V8 prefers predictable objects. |
|
function Entry (key, value, length, now, maxAge) { |
|
this.key = key |
|
this.value = value |
|
this.length = length |
|
this.now = now |
|
this.maxAge = maxAge || 0 |
|
}
|
|
|