feat(cache): add TLRUCache

thi-ng · Apr 21, 2018 · 574b5d9 · 574b5d9
1 parent c4a9c07
commit 574b5d9
Show file tree

Hide file tree

Showing 2 changed files with 101 additions and 0 deletions.
diff --git a/packages/cache/src/index.ts b/packages/cache/src/index.ts
@@ -1,3 +1,4 @@
 export * from "./api";
 export * from "./lru";
 export * from "./mru";
+export * from "./tlru";
diff --git a/packages/cache/src/tlru.ts b/packages/cache/src/tlru.ts
@@ -0,0 +1,100 @@
+import { ConsCell, DCons } from "@thi.ng/dcons";
+
+import { CacheEntry, CacheOpts } from "./api";
+import { LRUCache } from "./lru";
+
+export interface TLRUCacheOpts<K, V> extends CacheOpts<K, V> {
+    ttl: number;
+}
+
+export interface TLRUCacheEntry<K, V> extends CacheEntry<K, V> {
+    t: number;
+}
+
+/**
+ * Time-aware LRU cache. Extends LRU strategy with TTL (time-to-live)
+ * values associated to each entry. `has()` will only return true and
+ * `get()` only returns a cached value if its TTL hasn't yet expired.
+ * When adding a new value to the cache, first removes expired entries
+ * and if still not sufficient space then removes entries in LRU order.
+ * `set()` takes an optional entry specific `ttl` arg. If not given,
+ * uses the cache instance's default (provided via ctor option arg).
+ * If no instance TTL is given, TTL defaults to 1 hour.
+ */
+export class TLRUCache<K, V> extends LRUCache<K, V> {
+
+    protected opts: TLRUCacheOpts<K, V>;
+    protected map: Map<K, ConsCell<TLRUCacheEntry<K, V>>>;
+    protected items: DCons<TLRUCacheEntry<K, V>>;
+
+    constructor(pairs?: Iterable<[K, V]>, opts?: Partial<TLRUCacheOpts<K, V>>) {
+        opts = Object.assign({ ttl: 60 * 60 * 1000 }, opts)
+        super(pairs, opts);
+    }
+
+    empty(): TLRUCache<K, V> {
+        return new TLRUCache<K, V>(null, this.opts);
+    }
+
+    has(key: K) {
+        return this.get(key) !== undefined;
+    }
+
+    get(key: K, notFound?: any) {
+        const e = this.map.get(key);
+        if (e) {
+            if (e.value.t >= Date.now()) {
+                return e.value.v;
+            }
+            this.removeEntry(e);
+        }
+        return notFound;
+    }
+
+    set(key: K, value: V, ttl = this.opts.ttl) {
+        const size = this.opts.ksize(key) + this.opts.vsize(value);
+        const e = this.map.get(key);
+        if (e) {
+            this._size -= e.value.s;
+        }
+        this._size += size;
+        if (this.ensureSize()) {
+            const t = Date.now() + ttl;
+            if (e) {
+                e.value.v = value;
+                e.value.s = size;
+                e.value.t = t;
+                this.items.asTail(e);
+            } else {
+                this.items.push({
+                    k: key,
+                    v: value,
+                    s: size,
+                    t,
+                });
+                this.map.set(key, this.items.tail);
+            }
+        }
+        return value;
+    }
+
+    protected ensureSize() {
+        const release = this.opts.release;
+        const maxs = this.opts.maxsize;
+        const maxl = this.opts.maxlen;
+        const now = Date.now();
+        let cell = this.items.head;
+        while (cell && (this._size > maxs || this.length >= maxl)) {
+            if (cell.value.t < now) {
+                this.removeEntry(cell);
+            }
+            cell = cell.next;
+        }
+        cell = this.items.head;
+        while (cell && (this._size > maxs || this.length >= maxl)) {
+            this.removeEntry(cell);
+            cell = cell.next;
+        }
+        return true;
+    }
+}