1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
|
;(function () { // closure for web browsers
if (module) {
module.exports = LRUCache
} else {
// just set the global for non-node platforms.
;(function () { return this })().LRUCache = LRUCache
}
function hOP (obj, key) {
return Object.prototype.hasOwnProperty.call(obj, key)
}
function LRUCache (maxLength) {
if (!(this instanceof LRUCache)) {
return new LRUCache(maxLength)
}
var cache = {} // hash of items by key
, lruList = {} // list of items in order of use recency
, lru = 0 // least recently used
, mru = 0 // most recently used
, length = 0 // number of items in the list
// resize the cache when the maxLength changes.
Object.defineProperty(this, "maxLength",
{ set : function (mL) {
if (!mL || !(typeof mL === "number") || mL <= 0 ) mL = Infinity
maxLength = mL
// if it gets above double maxLength, trim right away.
// otherwise, do it whenever it's convenient.
if (length > maxLength) trim()
}
, get : function () { return maxLength }
, enumerable : true
})
this.maxLength = maxLength
Object.defineProperty(this, "length",
{ get : function () { return length }
, enumerable : true
})
this.reset = function () {
cache = {}
lruList = {}
lru = 0
mru = 0
length = 0
}
this.set = function (key, value) {
if (hOP(cache, key)) {
this.get(key)
cache[key].value = value
return undefined
}
var hit = {key:key, value:value, lu:mru++}
lruList[hit.lu] = cache[key] = hit
length ++
if (length > maxLength) trim()
}
this.get = function (key) {
if (!hOP(cache, key)) return undefined
var hit = cache[key]
delete lruList[hit.lu]
if (hit.lu === lru) lruWalk()
hit.lu = mru ++
lruList[hit.lu] = hit
return hit.value
}
this.del = function (key) {
if (!hOP(cache, key)) return undefined
var hit = cache[key]
delete cache[key]
delete lruList[hit.lu]
if (hit.lu === lru) lruWalk()
length --
}
function lruWalk () {
// lru has been deleted, hop up to the next hit.
lru = Object.keys(lruList).shift()
}
function trim () {
if (length <= maxLength) return undefined
var prune = Object.keys(lruList).slice(0, length - maxLength)
for (var i = 0, l = (length - maxLength); i < l; i ++) {
delete cache[ lruList[prune[i]].key ]
delete lruList[prune[i]]
}
length = maxLength
lruWalk()
}
}
})()
|
