aboutsummaryrefslogtreecommitdiff
path: root/ext
diff options
context:
space:
mode:
authortoasted-nutbread <toasted-nutbread@users.noreply.github.com>2020-08-09 13:15:56 -0400
committerGitHub <noreply@github.com>2020-08-09 13:15:56 -0400
commitd856e4caac0d3ddf8277ff20d92de4af8e351c16 (patch)
tree6e4561325d807422cc73eddc791da39603e11f23 /ext
parent8ee717cdf7c7701b9ec2d72799fcdcb621703e9e (diff)
CacheMap (#715)
* Create CacheMap class * Add test
Diffstat (limited to 'ext')
-rw-r--r--ext/mixed/js/cache-map.js177
1 files changed, 177 insertions, 0 deletions
diff --git a/ext/mixed/js/cache-map.js b/ext/mixed/js/cache-map.js
new file mode 100644
index 00000000..7953e2cc
--- /dev/null
+++ b/ext/mixed/js/cache-map.js
@@ -0,0 +1,177 @@
+/*
+ * Copyright (C) 2020 Yomichan Authors
+ *
+ * This program is free software: you can redistribute it and/or modify
+ * it under the terms of the GNU General Public License as published by
+ * the Free Software Foundation, either version 3 of the License, or
+ * (at your option) any later version.
+ *
+ * This program is distributed in the hope that it will be useful,
+ * but WITHOUT ANY WARRANTY; without even the implied warranty of
+ * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
+ * GNU General Public License for more details.
+ *
+ * You should have received a copy of the GNU General Public License
+ * along with this program. If not, see <https://www.gnu.org/licenses/>.
+ */
+
+/**
+ * Class which caches a map of values using an arbitrary length path,
+ * 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)
+ */
+ constructor(maxCount, create) {
+ if (!(
+ typeof maxCount === 'number' &&
+ Number.isFinite(maxCount) &&
+ maxCount >= 0 &&
+ Math.floor(maxCount) === maxCount
+ )) {
+ throw new Error('Invalid maxCount');
+ }
+
+ this._maxCount = maxCount;
+ this._create = create;
+ this._count = 0;
+ this._map = new Map();
+ this._listFirst = this._createNode(null, null);
+ this._listLast = this._createNode(null, null);
+ this._resetEndNodes();
+ }
+
+ /**
+ * Returns the number of items in the cache.
+ */
+ get count() {
+ return this._count;
+ }
+
+ /**
+ * Returns the maximum number of items that can be added to the cache.
+ */
+ get maxCount() {
+ return this._maxCount;
+ }
+
+ /**
+ * 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 Arguments corresponding to the key of the cache.
+ */
+ get(...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 is now a node)
+ this._updateRecency(map);
+ return map.value;
+ }
+
+ // Create new
+ const value = this._create(...path);
+
+ // 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 value;
+ }
+
+ /**
+ * Clears the cache.
+ */
+ clear() {
+ this._map.clear();
+ this._count = 0;
+ this._resetEndNodes();
+ }
+
+ // Private
+
+ _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};
+ }
+
+ _addNode(node, previous) {
+ const next = previous.next;
+ node.next = next;
+ node.previous = previous;
+ previous.next = node;
+ next.previous = node;
+ }
+
+ _removeNode(node) {
+ node.next.previous = node.previous;
+ 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;
+ }
+}