From cf57c4e38d619d979ca39328bd9ec4821f284816 Mon Sep 17 00:00:00 2001 From: toasted-nutbread Date: Thu, 21 Jan 2021 22:49:54 -0500 Subject: Simplify CacheMap (#1287) * Simplify CacheMap, removing support for array path keys * Update keys * Update JsonSchemaValidator * Update AudioSystem --- ext/bg/js/json-schema.js | 10 ++- ext/mixed/js/audio-system.js | 2 +- ext/mixed/js/cache-map.js | 172 ++++++++++++---------------------------- test/test-cache-map.js | 183 +++++++++++-------------------------------- 4 files changed, 102 insertions(+), 265 deletions(-) diff --git a/ext/bg/js/json-schema.js b/ext/bg/js/json-schema.js index 85ced354..7b6b9c53 100644 --- a/ext/bg/js/json-schema.js +++ b/ext/bg/js/json-schema.js @@ -125,7 +125,7 @@ class JsonSchemaProxyHandler { class JsonSchemaValidator { constructor() { - this._regexCache = new CacheMap(100, ([pattern, flags]) => new RegExp(pattern, flags)); + this._regexCache = new CacheMap(100); } createProxy(target, schema) { @@ -705,8 +705,12 @@ class JsonSchemaValidator { } _getRegex(pattern, flags) { - const regex = this._regexCache.getOrCreate([pattern, flags]); - regex.lastIndex = 0; + const key = `${flags}:${pattern}`; + let regex = this._regexCache.get(key); + if (typeof regex === 'undefined') { + regex = new RegExp(pattern, flags); + this._regexCache.set(key, regex); + } return regex; } } diff --git a/ext/mixed/js/audio-system.js b/ext/mixed/js/audio-system.js index f42fd657..584da2b1 100644 --- a/ext/mixed/js/audio-system.js +++ b/ext/mixed/js/audio-system.js @@ -37,7 +37,7 @@ class AudioSystem { } async createExpressionAudio(sources, expression, reading, details) { - const key = [expression, reading]; + const key = JSON.stringify([expression, reading]); const cacheValue = this._cache.get(key); if (typeof cacheValue !== 'undefined') { diff --git a/ext/mixed/js/cache-map.js b/ext/mixed/js/cache-map.js index 57430848..c7d72e6b 100644 --- a/ext/mixed/js/cache-map.js +++ b/ext/mixed/js/cache-map.js @@ -16,29 +16,24 @@ */ /** - * Class which caches a map of values using an arbitrary length path, - * keeping the most recently accessed values. + * Class which caches a map of values, keeping the most recently accessed values. */ class CacheMap { /** * Creates a new CacheMap. - * @param maxCount The maximum number of entries able to be stored in the cache. - * @param create A function to create a value for the corresponding path. - * The signature is: create(path) + * @param maxSize The maximum number of entries able to be stored in the cache. */ - constructor(maxCount, create) { + constructor(maxSize) { if (!( - typeof maxCount === 'number' && - Number.isFinite(maxCount) && - maxCount >= 0 && - Math.floor(maxCount) === maxCount + typeof maxSize === 'number' && + Number.isFinite(maxSize) && + maxSize >= 0 && + Math.floor(maxSize) === maxSize )) { throw new Error('Invalid maxCount'); } - this._maxCount = maxCount; - this._create = create; - this._count = 0; + this._maxSize = maxSize; this._map = new Map(); this._listFirst = this._createNode(null, null); this._listLast = this._createNode(null, null); @@ -48,54 +43,62 @@ class CacheMap { /** * Returns the number of items in the cache. */ - get count() { - return this._count; + get size() { + return this._map.size; } /** * Returns the maximum number of items that can be added to the cache. */ - get maxCount() { - return this._maxCount; + get maxSize() { + return this._maxSize; } /** - * Returns whether or not an item exists at the given path. - * @param path Array corresponding to the key of the cache. - * @returns A boolean indicating whether ot not the item exists. + * Returns whether or not an element exists at the given key. + * @param key The key of the element. + * @returns `true` if an element with the specified key exists, `false` otherwise. */ - has(path) { - const node = this._accessNode(false, false, null, false, path); - return (node !== null); + has(key) { + return this._map.has(key); } /** - * Gets an item at the given path, if it exists. Otherwise, returns undefined. - * @param path Array corresponding to the key of the cache. - * @returns The existing value at the path, if any; otherwise, undefined. + * Gets an element at the given key, if it exists. Otherwise, returns undefined. + * @param key The key of the element. + * @returns The existing value at the key, if any; `undefined` otherwise. */ - get(path) { - const node = this._accessNode(false, false, null, true, path); - return (node !== null ? node.value : void 0); + get(key) { + const node = this._map.get(key); + if (typeof node === 'undefined') { return void 0; } + this._updateRecency(node); + return node.value; } /** - * Gets an item at the given path, if it exists. Otherwise, creates a new item - * and adds it to the cache. If the count exceeds the maximum count, items will be removed. - * @param path Array corresponding to the key of the cache. - * @returns The existing value at the path, if any; otherwise, a newly created value. - */ - getOrCreate(path) { - return this._accessNode(true, false, null, true, path).value; - } - - /** - * Sets a value at a given path. - * @param path Array corresponding to the key of the cache. + * Sets a value at a given key. + * @param key The key of the element. * @param value The value to store in the cache. */ - set(path, value) { - this._accessNode(false, true, value, true, path); + set(key, value) { + let node = this._map.get(key); + if (typeof node !== 'undefined') { + this._updateRecency(node); + node.value = value; + } else { + if (this._maxSize <= 0) { return; } + + node = this._createNode(key, value); + this._addNode(node, this._listFirst); + this._map.set(key, node); + + // Remove + for (let removeCount = this._map.size - this._maxSize; removeCount > 0; --removeCount) { + node = this._listLast.previous; + this._removeNode(node); + this._map.delete(node.key); + } + } } /** @@ -103,73 +106,18 @@ class CacheMap { */ clear() { this._map.clear(); - this._count = 0; this._resetEndNodes(); } // Private - _accessNode(create, set, value, updateRecency, path) { - let ii = path.length; - if (ii === 0) { throw new Error('Invalid path'); } - - let map = this._map; - let i = 0; - for (; i < ii; ++i) { - const map2 = map.get(path[i]); - if (typeof map2 === 'undefined') { break; } - map = map2; - } - - if (i === ii) { - // Found (map should now be a node) - if (updateRecency) { this._updateRecency(map); } - if (set) { map.value = value; } - return map; - } - - // Create new - if (create) { - value = this._create(path); - } else if (!set) { - return null; - } - - // Create mapping - --ii; - for (; i < ii; ++i) { - const map2 = new Map(); - map.set(path[i], map2); - map = map2; - } - - // Assign - const node = this._createNode(value, path); - this._addNode(node, this._listFirst); - map.set(path[ii], node); - ++this._count; - - this._updateCount(); - - return node; - } - _updateRecency(node) { this._removeNode(node); this._addNode(node, this._listFirst); } - _updateCount() { - for (let removeCount = this._count - this._maxCount; removeCount > 0; --removeCount) { - const node = this._listLast.previous; - this._removeNode(node); - this._removeMapping(node.path); - --this._count; - } - } - - _createNode(value, path) { - return {value, path, previous: null, next: null}; + _createNode(key, value) { + return {key, value, previous: null, next: null}; } _addNode(node, previous) { @@ -185,30 +133,6 @@ class CacheMap { node.previous.next = node.next; } - _removeMapping(path) { - const ii = path.length - 1; - let i = 0; - const maps = []; - let map = this._map; - for (; i < ii; ++i) { - const map2 = map.get(path[i]); - if (typeof map2 === 'undefined') { return; } - maps.push([map, map2]); - map = map2; - } - - // Delete node - map.delete(path[ii]); - - // Clear empty paths - for (i = ii - 1; i >= 0; --i) { - let map2; - [map, map2] = maps[i]; - if (map2.size > 0) { return; } - map.delete(path[i]); - } - } - _resetEndNodes() { this._listFirst.next = this._listLast; this._listLast.previous = this._listFirst; diff --git a/test/test-cache-map.js b/test/test-cache-map.js index 2ecdd401..4d19015b 100644 --- a/test/test-cache-map.js +++ b/test/test-cache-map.js @@ -28,14 +28,14 @@ const CacheMap = vm.get('CacheMap'); function testConstructor() { const data = [ - [false, () => new CacheMap(0, () => null)], - [false, () => new CacheMap(1, () => null)], - [false, () => new CacheMap(Number.MAX_VALUE, () => null)], - [true, () => new CacheMap(-1, () => null)], - [true, () => new CacheMap(1.5, () => null)], - [true, () => new CacheMap(Number.NaN, () => null)], - [true, () => new CacheMap(Number.POSITIVE_INFINITY, () => null)], - [true, () => new CacheMap('a', () => null)] + [false, () => new CacheMap(0)], + [false, () => new CacheMap(1)], + [false, () => new CacheMap(Number.MAX_VALUE)], + [true, () => new CacheMap(-1)], + [true, () => new CacheMap(1.5)], + [true, () => new CacheMap(Number.NaN)], + [true, () => new CacheMap(Number.POSITIVE_INFINITY)], + [true, () => new CacheMap('a')] ]; for (const [throws, create] of data) { @@ -50,155 +50,64 @@ function testConstructor() { function testApi() { const data = [ { - maxCount: 1, - expectedCount: 0, + maxSize: 1, + expectedSize: 0, calls: [] }, { - maxCount: 1, - expectedCount: 1, + maxSize: 10, + expectedSize: 1, calls: [ - {func: 'getOrCreate', args: [['a', 'b', 'c']]} + {func: 'get', args: ['a1-b-c'], returnValue: void 0}, + {func: 'has', args: ['a1-b-c'], returnValue: false}, + {func: 'set', args: ['a1-b-c', 32], returnValue: void 0}, + {func: 'get', args: ['a1-b-c'], returnValue: 32}, + {func: 'has', args: ['a1-b-c'], returnValue: true} ] }, { - maxCount: 10, - expectedCount: 1, + maxSize: 10, + expectedSize: 2, calls: [ - {func: 'getOrCreate', args: [['a', 'b', 'c']]}, - {func: 'getOrCreate', args: [['a', 'b', 'c']]}, - {func: 'getOrCreate', args: [['a', 'b', 'c']]} + {func: 'set', args: ['a1-b-c', 32], returnValue: void 0}, + {func: 'get', args: ['a1-b-c'], returnValue: 32}, + {func: 'set', args: ['a1-b-c', 64], returnValue: void 0}, + {func: 'get', args: ['a1-b-c'], returnValue: 64}, + {func: 'set', args: ['a2-b-c', 96], returnValue: void 0}, + {func: 'get', args: ['a2-b-c'], returnValue: 96} ] }, { - maxCount: 10, - expectedCount: 3, + maxSize: 2, + expectedSize: 2, calls: [ - {func: 'getOrCreate', args: [['a1', 'b', 'c']]}, - {func: 'getOrCreate', args: [['a2', 'b', 'c']]}, - {func: 'getOrCreate', args: [['a3', 'b', 'c']]} - ] - }, - { - maxCount: 10, - expectedCount: 3, - calls: [ - {func: 'getOrCreate', args: [['a', 'b1', 'c']]}, - {func: 'getOrCreate', args: [['a', 'b2', 'c']]}, - {func: 'getOrCreate', args: [['a', 'b3', 'c']]} - ] - }, - { - maxCount: 10, - expectedCount: 3, - calls: [ - {func: 'getOrCreate', args: [['a', 'b', 'c1']]}, - {func: 'getOrCreate', args: [['a', 'b', 'c2']]}, - {func: 'getOrCreate', args: [['a', 'b', 'c3']]} - ] - }, - { - maxCount: 1, - expectedCount: 1, - calls: [ - {func: 'getOrCreate', args: [['a1', 'b', 'c']]}, - {func: 'getOrCreate', args: [['a2', 'b', 'c']]}, - {func: 'getOrCreate', args: [['a3', 'b', 'c']]} - ] - }, - { - maxCount: 1, - expectedCount: 1, - calls: [ - {func: 'getOrCreate', args: [['a', 'b1', 'c']]}, - {func: 'getOrCreate', args: [['a', 'b2', 'c']]}, - {func: 'getOrCreate', args: [['a', 'b3', 'c']]} - ] - }, - { - maxCount: 1, - expectedCount: 1, - calls: [ - {func: 'getOrCreate', args: [['a', 'b', 'c1']]}, - {func: 'getOrCreate', args: [['a', 'b', 'c2']]}, - {func: 'getOrCreate', args: [['a', 'b', 'c3']]} - ] - }, - { - maxCount: 10, - expectedCount: 0, - calls: [ - {func: 'getOrCreate', args: [['a', 'b', 'c1']]}, - {func: 'getOrCreate', args: [['a', 'b', 'c2']]}, - {func: 'getOrCreate', args: [['a', 'b', 'c3']]}, - {func: 'clear', args: []} - ] - }, - { - maxCount: 0, - expectedCount: 0, - calls: [ - {func: 'getOrCreate', args: [['a1', 'b', 'c']]}, - {func: 'getOrCreate', args: [['a', 'b2', 'c']]}, - {func: 'getOrCreate', args: [['a', 'b', 'c3']]} - ] - }, - { - maxCount: 10, - expectedCount: 1, - calls: [ - {func: 'get', args: [['a1', 'b', 'c']], returnValue: void 0}, - {func: 'has', args: [['a1', 'b', 'c']], returnValue: false}, - {func: 'set', args: [['a1', 'b', 'c'], 32], returnValue: void 0}, - {func: 'get', args: [['a1', 'b', 'c']], returnValue: 32}, - {func: 'has', args: [['a1', 'b', 'c']], returnValue: true} - ] - }, - { - maxCount: 10, - expectedCount: 2, - calls: [ - {func: 'set', args: [['a1', 'b', 'c'], 32], returnValue: void 0}, - {func: 'get', args: [['a1', 'b', 'c']], returnValue: 32}, - {func: 'set', args: [['a1', 'b', 'c'], 64], returnValue: void 0}, - {func: 'get', args: [['a1', 'b', 'c']], returnValue: 64}, - {func: 'set', args: [['a2', 'b', 'c'], 96], returnValue: void 0}, - {func: 'get', args: [['a2', 'b', 'c']], returnValue: 96} - ] - }, - { - maxCount: 2, - expectedCount: 2, - calls: [ - {func: 'has', args: [['a1', 'b', 'c']], returnValue: false}, - {func: 'has', args: [['a2', 'b', 'c']], returnValue: false}, - {func: 'has', args: [['a3', 'b', 'c']], returnValue: false}, - {func: 'set', args: [['a1', 'b', 'c'], 1], returnValue: void 0}, - {func: 'has', args: [['a1', 'b', 'c']], returnValue: true}, - {func: 'has', args: [['a2', 'b', 'c']], returnValue: false}, - {func: 'has', args: [['a3', 'b', 'c']], returnValue: false}, - {func: 'set', args: [['a2', 'b', 'c'], 2], returnValue: void 0}, - {func: 'has', args: [['a1', 'b', 'c']], returnValue: true}, - {func: 'has', args: [['a2', 'b', 'c']], returnValue: true}, - {func: 'has', args: [['a3', 'b', 'c']], returnValue: false}, - {func: 'set', args: [['a3', 'b', 'c'], 3], returnValue: void 0}, - {func: 'has', args: [['a1', 'b', 'c']], returnValue: false}, - {func: 'has', args: [['a2', 'b', 'c']], returnValue: true}, - {func: 'has', args: [['a3', 'b', 'c']], returnValue: true} + {func: 'has', args: ['a1-b-c'], returnValue: false}, + {func: 'has', args: ['a2-b-c'], returnValue: false}, + {func: 'has', args: ['a3-b-c'], returnValue: false}, + {func: 'set', args: ['a1-b-c', 1], returnValue: void 0}, + {func: 'has', args: ['a1-b-c'], returnValue: true}, + {func: 'has', args: ['a2-b-c'], returnValue: false}, + {func: 'has', args: ['a3-b-c'], returnValue: false}, + {func: 'set', args: ['a2-b-c', 2], returnValue: void 0}, + {func: 'has', args: ['a1-b-c'], returnValue: true}, + {func: 'has', args: ['a2-b-c'], returnValue: true}, + {func: 'has', args: ['a3-b-c'], returnValue: false}, + {func: 'set', args: ['a3-b-c', 3], returnValue: void 0}, + {func: 'has', args: ['a1-b-c'], returnValue: false}, + {func: 'has', args: ['a2-b-c'], returnValue: true}, + {func: 'has', args: ['a3-b-c'], returnValue: true} ] } ]; - const create = (args) => args.join(','); - for (const {maxCount, expectedCount, calls} of data) { - const cache = new CacheMap(maxCount, create); - assert.strictEqual(cache.maxCount, maxCount); + for (const {maxSize, expectedSize, calls} of data) { + const cache = new CacheMap(maxSize); + assert.strictEqual(cache.maxSize, maxSize); for (const call of calls) { const {func, args} = call; let returnValue; switch (func) { case 'get': returnValue = cache.get(...args); break; - case 'getOrCreate': returnValue = cache.getOrCreate(...args); break; case 'set': returnValue = cache.set(...args); break; case 'has': returnValue = cache.has(...args); break; case 'clear': returnValue = cache.clear(...args); break; @@ -208,7 +117,7 @@ function testApi() { assert.deepStrictEqual(returnValue, expectedReturnValue); } } - assert.strictEqual(cache.count, expectedCount); + assert.strictEqual(cache.size, expectedSize); } } -- cgit v1.2.3