| 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
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227 |
2x
80x
43x
43x
37x
37x
37x
2x
46x
32x
14x
14x
12x
12x
12x
12x
2x
2x
2x
2x
14x
2x
9x
3x
6x
9x
7x
2x
9x
2x
8x
8x
8x
8x
8x
2x
96x
96x
19x
77x
8x
77x
14x
14x
14x
1x
14x
14x
14x
16x
16x
3x
16x
14x
14x
14x
92x
92x
80x
80x
80x
80x
80x
12x
12x
12x
14x
64x
64x
30x
34x
34x
14x
71x
71x
14x
14x
10x
10x
1x
9x
9x
14x
3x
3x
6x
6x
14x
50x
50x
50x
69x
69x
50x
14x
50x
42x
42x
42x
42x
14x
|
/* eslint-disable no-param-reassign */
const addNewest = (entry, entryList) => {
if (entryList.newest === null) {
entryList.newest = entry;
entryList.oldest = entry;
}
else {
entryList.newest.next = entry;
entry.prev = entryList.newest;
entryList.newest = entry;
}
};
/* eslint-disable no-param-reassign */
const makeNewest = (entry, entryList) => {
if (entry === entryList.newest) {
// entry already is newest
return;
}
entryList.newest.next = entry;
if (entry.prev === null) {
// entry is current oldest (and not newest)
entry.prev = entryList.newest;
entry.next.prev = null;
entryList.oldest = entry.next;
entry.next = null;
}
else {
// entry is neither newest, nor oldest
entry.prev.next = entry.next;
entry.next.prev = entry.prev;
entry.prev = entryList.newest;
entry.next = null;
}
entryList.newest = entry;
};
/* eslint-disable no-param-reassign */
const removeEntry = (entry, entryList, keyToEntry) => {
if (entry.next === null) {
entryList.newest = entry.prev;
}
else {
entry.next.prev = entry.prev;
}
if (entry.prev === null) {
entryList.oldest = entry.next;
}
else {
entry.prev.next = entry.next;
}
keyToEntry.delete(entry.key);
};
const removeOldest = (entryList, keyToEntry) => {
// As maxSize cannot be <1 and removeOldest is only called, if maxSize exceeded,
// we can be sure that at least two entries exist.
const removedEntry = entryList.oldest;
keyToEntry.delete(entryList.oldest.key);
entryList.oldest = entryList.oldest.next;
entryList.oldest.prev = null;
return {key: removedEntry.key, value: removedEntry.value};
};
const shrinkToMaxSize = (maxSize, entryList, keyToEntry) => {
const removals = [];
if (maxSize === null) {
return removals;
}
while (keyToEntry.size > maxSize) {
removals.push(removeOldest(entryList, keyToEntry));
}
return removals;
};
/** Map object that provides LRU logic, removing oldest entry in case adding a new one exceeds the set max size
* @param {int} maxSize - maximum size for the LRU Map. If null or not specified, then the size is unlimited
* @return {LruMap} - an object with methods setMaxSize, getMaxSize, getSize, set, get, delete, clear, forEach and map
*/
export function LruMap(maxSize = null) {
const self = this instanceof LruMap ? this : Object.create(LruMap.prototype);
let sizeLimit = maxSize;
if (sizeLimit === 0) {
sizeLimit = null;
}
const keyToEntry = new Map();
const entryList = {
newest: null,
oldest: null,
};
/** Change the max size of the LruMap.
* Will return an array of removed entries as key-value-objects (empty in case the existing Map had not to be shrinked)
* @param {int} newMaxSize - The new maximum size of the Map
* @return {Array} An array containing all Map entries that were removed due to exceeded max size
*/
self.setMaxSize = newMaxSize => {
sizeLimit = newMaxSize;
if (sizeLimit < 1) {
sizeLimit = null;
}
return shrinkToMaxSize(sizeLimit, entryList, keyToEntry);
};
/** Return current maxSize
* @return {int} The current max size of the Map
*/
self.getMaxSize = () => sizeLimit;
/** Return current size (number of Map entries)
* @return {int} Current number of cache entries
*/
self.getSize = () => keyToEntry.size;
/** Insert or update Map entry.
* If the key already exists in the Map, the corresponding item will be replaced by the given one.
* Whether inserted or updated, the entry will become the most recently used/updated entry.
* In case of maxSize being exceeded, the removed entry will be returned (as object with key and value), else null
* @param {string} key - The key of the entry
* @param {object} value - The value of the entry
* @return {object | null} LRU-removed entry or null
*/
self.set = (key, value) => {
let entry = keyToEntry.get(key);
if (typeof entry === "undefined") {
entry = {
key,
value,
next: null,
prev: null,
};
keyToEntry.set(key, entry);
addNewest(entry, entryList);
const removals = shrinkToMaxSize(sizeLimit, entryList, keyToEntry);
return removals.length === 1 ? removals[0] : null;
}
else {
entry.value = value;
makeNewest(entry, entryList);
return null;
}
};
/** Return value for key (undefined if not exists).
* Makes the entry the most recently used
* @param {string} key - The entry key
* @return {object} The corresponding value or undefined
*/
self.get = key => {
const entry = keyToEntry.get(key);
if (typeof entry === "undefined") {
return entry;
}
makeNewest(entry, entryList);
return entry.value;
};
/** Like 'get', but not making the corresponding entry the most recently used.
* @param {string} key - The entry key
* @return {object} The corresponding value or undefined
*/
self.getWithoutLruChange = key => {
const entry = keyToEntry.get(key);
return typeof entry === "undefined" ? entry : entry.value;
};
/** Return whether the LruMap contains key
* @param {string} key - The entry key
* @return {boolean} true, if the given key is in the LruMap
*/
self.has = key => keyToEntry.has(key);
/** Remove the entry with the given key from the map. Returns false, in case the key was not in the map
* @param {string} key - The entry key
* @return {boolean} true in case the key existed in the Map
*/
self.delete = key => {
const entry = keyToEntry.get(key);
if (typeof entry === "undefined") {
return false;
}
removeEntry(entry, entryList, keyToEntry);
return true;
};
/** Given callback will receive value as first parameter and key as second parameter. Iterates from oldest to newest
* @param {function} callback - function that will be called with (value, key) for each entry
* @return {undefined} void
*/
self.forEach = callback => {
let next = entryList.oldest;
while (next !== null) {
callback(next.value, next.key); // eslint-disable-line callback-return
next = next.next;
}
};
/** Given callback will receive value as first parameter and key as second parameter. Returns an array. Iterates from oldest to newest
* @param {function} callback - function that will be called with (value, key) for each entry and returns an item for the resulting array
* @return {Array} Array of return values from the callback function
*/
self.map = callback => {
let next = entryList.oldest;
const result = [];
while (next !== null) {
result.push(callback(next.value, next.key)); // eslint-disable-line callback-return
next = next.next;
}
return result;
};
/** Will clear the map and return an array with the removed entries
* @return {Array} Array of all entries (key-value-pairs) that were in the Map prior to clear
*/
self.clear = () => {
const result = self.map((value, key) => ({key, value}));
keyToEntry.clear();
entryList.newest = null;
entryList.oldest = null;
return result;
};
return self;
}
|