aboutsummaryrefslogtreecommitdiff
diff options
context:
space:
mode:
authortoasted-nutbread <toasted-nutbread@users.noreply.github.com>2021-01-21 22:49:54 -0500
committerGitHub <noreply@github.com>2021-01-21 22:49:54 -0500
commitcf57c4e38d619d979ca39328bd9ec4821f284816 (patch)
tree0bd80612cc5200218f76ae51ab4025c33a7c26a6
parent0bc5a4a971126adca1787d90db36b13716638290 (diff)
Simplify CacheMap (#1287)
* Simplify CacheMap, removing support for array path keys * Update keys * Update JsonSchemaValidator * Update AudioSystem
-rw-r--r--ext/bg/js/json-schema.js10
-rw-r--r--ext/mixed/js/audio-system.js2
-rw-r--r--ext/mixed/js/cache-map.js172
-rw-r--r--test/test-cache-map.js183
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);
}
}