| 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; } |