spica - npm Package Compare versions

Comparing version 0.0.703 to 0.0.704

cache.test.ts

@@ -341,2 +341,22 @@ import { Cache } from './cache';
 
+    it('verify', function () {
+      this.timeout(10 * 1e3);
+
+      const capacity = 100;
+      const cache = new Cache<number, number>(capacity);
+
+      const trials = capacity * 1000;
+      const random = pcg32.random(pcg32.seed(0n, 0n));
+      for (let i = 0; i < trials; ++i) {
+        const key = random() * capacity * 10 | 0;
+        if (cache.has(key)) {
+          assert(cache.get(key) === ~key);
+        }
+        else {
+          cache.add(key, ~key);
+        }
+      }
+      assert(cache.length === capacity);
+    });
+
     if (!navigator.userAgent.includes('Chrome')) return;
@@ -362,3 +382,3 @@
         stats.lru += lru.get(key) ?? +lru.set(key, 1) & 0;
-        stats.dwc += dwc.get(key) ?? +dwc.put(key, 1) & 0;
+        stats.dwc += dwc.get(key) ?? +dwc.add(key, 1) & 0;
       }
@@ -393,3 +413,3 @@ assert(dwc['LRU'].length + dwc['LFU'].length === dwc['dict'].size);
         stats.lru += lru.get(key) ?? +lru.set(key, 1) & 0;
-        stats.dwc += dwc.get(key) ?? +dwc.put(key, 1) & 0;
+        stats.dwc += dwc.get(key) ?? +dwc.add(key, 1) & 0;
       }
@@ -423,3 +443,3 @@ assert(dwc['LRU'].length + dwc['LFU'].length === dwc['dict'].size);
         stats.lru += lru.get(key) ?? +lru.set(key, 1) & 0;
-        stats.dwc += dwc.get(key) ?? +dwc.put(key, 1) & 0;
+        stats.dwc += dwc.get(key) ?? +dwc.add(key, 1) & 0;
       }
@@ -456,3 +476,3 @@ assert(dwc['LRU'].length + dwc['LFU'].length === dwc['dict'].size);
         stats.lru += lru.get(key) ?? +lru.set(key, 1) & 0;
-        stats.dwc += dwc.get(key) ?? +dwc.put(key, 1) & 0;
+        stats.dwc += dwc.get(key) ?? +dwc.add(key, 1) & 0;
       }
@@ -487,3 +507,3 @@ assert(dwc['LRU'].length + dwc['LFU'].length === dwc['dict'].size);
         stats.lru += lru.get(key) ?? +lru.set(key, 1) & 0;
-        stats.dwc += dwc.get(key) ?? +dwc.put(key, 1) & 0;
+        stats.dwc += dwc.get(key) ?? +dwc.add(key, 1) & 0;
       }
@@ -517,4 +537,4 @@ assert(dwc['LRU'].length + dwc['LFU'].length === dwc['dict'].size);
           : random() * capacity / -1 | 0;
-        stats.lru += lru.get(key)! & +(key < 0) || +lru.set(key, 1) & 0;
-        stats.dwc += dwc.get(key)! & +(key < 0) || +dwc.put(key, 1) & 0;
+        stats.lru += lru.get(key) ?? +lru.set(key, 1) & 0;
+        stats.dwc += dwc.get(key) ?? +dwc.add(key, 1) & 0;
       }
@@ -530,3 +550,3 @@ assert(dwc['LRU'].length + dwc['LFU'].length === dwc['dict'].size);
       console.debug('DWC overlap', dwc['overlapLFU'] / dwc['LRU'].length * 100 | 0, dwc['overlapLRU'] / dwc['LFU'].length * 100 | 0);
-      assert(stats.dwc / stats.lru * 100 >>> 0 === 83);
+      assert(stats.dwc / stats.lru * 100 >>> 0 === 95);
     });
@@ -546,3 +566,3 @@
         stats.lru += lru.get(key) ?? +lru.set(key, 1) & 0;
-        stats.dwc += dwc.get(key) ?? +dwc.put(key, 1) & 0;
+        stats.dwc += dwc.get(key) ?? +dwc.add(key, 1) & 0;
       }
@@ -576,3 +596,3 @@ assert(dwc['LRU'].length + dwc['LFU'].length === dwc['dict'].size);
         stats.lru += lru.get(key) ?? +lru.set(key, 1) & 0;
-        stats.dwc += dwc.get(key) ?? +dwc.put(key, 1) & 0;
+        stats.dwc += dwc.get(key) ?? +dwc.add(key, 1) & 0;
       }
@@ -615,3 +635,3 @@ assert(dwc['LRU'].length + dwc['LFU'].length === dwc['dict'].size);
         stats.lru += lru.get(key) ?? +lru.set(key, 1) & 0;
-        stats.dwc += dwc.get(key) ?? +dwc.put(key, 1) & 0;
+        stats.dwc += dwc.get(key) ?? +dwc.add(key, 1) & 0;
         if (trials - i !== capacity) continue;
@@ -661,3 +681,3 @@ stats.lru = 0;
         stats.lru += lru.get(key) ?? +lru.set(key, 1) & 0;
-        stats.dwc += dwc.get(key) ?? +dwc.put(key, 1) & 0;
+        stats.dwc += dwc.get(key) ?? +dwc.add(key, 1) & 0;
         if (trials - i !== capacity) continue;
@@ -707,3 +727,3 @@ stats.lru = 0;
         stats.lru += lru.get(key) ?? +lru.set(key, 1) & 0;
-        stats.dwc += dwc.get(key) ?? +dwc.put(key, 1) & 0;
+        stats.dwc += dwc.get(key) ?? +dwc.add(key, 1) & 0;
         if (trials - i !== capacity) continue;
@@ -741,3 +761,3 @@ stats.lru = 0;
         stats.lru += lru.get(key) ?? +lru.set(key, 1) & 0;
-        stats.dwc += dwc.get(key) ?? +dwc.put(key, 1) & 0;
+        stats.dwc += dwc.get(key) ?? +dwc.add(key, 1) & 0;
       }
@@ -744,0 +764,0 @@ assert(dwc['LRU'].length + dwc['LFU'].length === dwc['dict'].size);

cache.ts

@@ -374,5 +374,28 @@ import { max, min, ceil, round } from './alias';
   }
-  public put(key: K, value: V, opts?: { size?: number; age?: number; }): boolean;
-  public put(this: Cache<K, undefined>, key: K, value?: V, opts?: { size?: number; age?: number; }): boolean;
-  public put(key: K, value: V, { size = 1, age = this.age }: { size?: number; age?: number; } = {}): boolean {
+  private update(entry: Entry<K, V>, key: K, value: V, size: number, expiration: number): void {
+    assert(entry.next);
+    const key$ = entry.key;
+    const value$ = entry.value;
+    entry.key = key;
+    entry.value = value;
+    this.$size += size - entry.size;
+    assert(0 < this.size && this.size <= this.resource);
+    entry.size = size;
+    entry.expiration = expiration;
+    if (this.expiration && this.expirations !== undefined && expiration !== Infinity) {
+      entry.enode !== undefined
+        ? this.expirations.update(entry.enode, expiration)
+        : entry.enode = this.expirations.insert(entry, expiration);
+      assert(this.expirations.length <= this.length);
+    }
+    else if (entry.enode !== undefined) {
+      this.expirations!.delete(entry.enode);
+      entry.enode = undefined;
+    }
+    assert(this.LRU.length + this.LFU.length === this.dict.size);
+    this.disposer?.(value$, key$);
+  }
+  public add(key: K, value: V, opts?: { size?: number; age?: number; }, entry?: Entry<K, V>): boolean;
+  public add(this: Cache<K, undefined>, key: K, value?: V, opts?: { size?: number; age?: number; }, entry?: Entry<K, V>): boolean;
+  public add(key: K, value: V, { size = 1, age = this.age }: { size?: number; age?: number; } = {}, entry?: Entry<K, V>): boolean {
     if (size < 1 || this.resource < size || age <= 0) {
@@ -383,2 +406,3 @@ this.disposer?.(value, key);
 
+    assert(!this.dict.has(key));
     const { LRU } = this;
@@ -388,4 +412,2 @@ const expiration = age === Infinity
       : now() + age;
-    let entry = this.dict.get(key);
-    const match = entry !== undefined;
     entry = this.ensure(size, entry, true);
@@ -413,38 +435,37 @@ if (entry === undefined) {
       }
+      return true;
+    }
+
+    assert(entry === LRU.head!.prev);
+    entry.region === 'LFU' && --this.overlapLFU;
+    assert(this.overlapLFU >= 0);
+    this.dict.delete(entry.key);
+    this.dict.set(key, entry);
+    assert(this.LRU.length + this.LFU.length === this.dict.size);
+    assert(this.dict.size <= this.capacity);
+    entry.region = 'LRU';
+    LRU.head = entry;
+    this.update(entry, key, value, size, expiration);
+    return true;
+  }
+  public put(key: K, value: V, opts?: { size?: number; age?: number; }): boolean;
+  public put(this: Cache<K, undefined>, key: K, value?: V, opts?: { size?: number; age?: number; }): boolean;
+  public put(key: K, value: V, { size = 1, age = this.age }: { size?: number; age?: number; } = {}): boolean {
+    if (size < 1 || this.resource < size || age <= 0) {
+      this.disposer?.(value, key);
       return false;
     }
 
-    assert(entry.next);
-    const key$ = entry.key;
-    const value$ = entry.value;
-    if (!match) {
-      assert(entry === LRU.head!.prev);
-      entry.region === 'LFU' && --this.overlapLFU;
-      assert(this.overlapLFU >= 0);
-      this.dict.delete(key$);
-      this.dict.set(key, entry);
-      assert(this.LRU.length + this.LFU.length === this.dict.size);
-      assert(this.dict.size <= this.capacity);
-      entry.key = key;
-      entry.region = 'LRU';
-      LRU.head = entry;
+    let entry = this.dict.get(key);
+    const match = entry !== undefined;
+    entry = this.ensure(size, entry, true);
+    if (!match || entry === undefined) {
+      this.add(key, value, { size, age }, entry);
+      return match;
     }
-    assert(this.dict.has(key));
-    entry.value = value;
-    this.$size += size - entry.size;
-    assert(0 < this.size && this.size <= this.resource);
-    entry.size = size;
-    entry.expiration = expiration;
-    if (this.expiration && this.expirations !== undefined && expiration !== Infinity) {
-      entry.enode !== undefined
-        ? this.expirations.update(entry.enode, expiration)
-        : entry.enode = this.expirations.insert(entry, expiration);
-      assert(this.expirations.length <= this.length);
-    }
-    else if (entry.enode !== undefined) {
-      this.expirations!.delete(entry.enode);
-      entry.enode = undefined;
-    }
-    assert(this.LRU.length + this.LFU.length === this.dict.size);
-    this.disposer?.(value$, key$);
+
+    const expiration = age === Infinity
+      ? age
+      : now() + age;
+    this.update(entry, key, value, size, expiration);
     return match;
@@ -469,3 +490,3 @@ }
     }
-    this.update(entry);
+    this.replace(entry);
     return entry.value;
@@ -535,3 +556,3 @@ }
   }
-  private update(entry: Entry<K, V>): void {
+  private replace(entry: Entry<K, V>): void {
     const { LRU, LFU } = this;
@@ -538,0 +559,0 @@ this.sweeper.hit();

clock.test.ts

@@ -42,2 +42,25 @@ import { Clock, CLOCK } from './clock';
 
+    it('verify', function () {
+      this.timeout(10 * 1e3);
+
+      const capacity = 96;
+      const clock = new Clock<number, number>(capacity);
+
+      const trials = capacity * 1000;
+      const random = pcg32.random(pcg32.seed(0n, 0n));
+      for (let i = 0; i < trials; ++i) {
+        const key = random() * capacity * 10 | 0;
+        if (clock.has(key)) {
+          assert(clock.get(key) === ~key);
+        }
+        else {
+          clock.add(key, ~key);
+        }
+        assert(clock.length <= capacity);
+        assert(clock['values'].length === clock.length);
+        assert(clock['values'].length === clock['dict'].size);
+      }
+      assert(clock.length === capacity);
+    });
+
     class Stats {
@@ -44,0 +67,0 @@ clock = 0;

clock.ts

@@ -49,9 +49,3 @@ import { ceil } from './alias';
   }
-  public put(key: K, value: V): number {
-    const index = this.dict.get(key);
-    if (index !== undefined) {
-      this.mark(index);
-      this.values[index] = value;
-      return index;
-    }
+  public add(key: K, value: V): number {
     const { capacity, refs } = this;
@@ -81,2 +75,9 @@ let hand = this.hand;
   }
+  public put(key: K, value: V): number {
+    const index = this.dict.get(key);
+    if (index === undefined) return this.add(key, value);
+    this.mark(index);
+    this.values[index] = value;
+    return index;
+  }
   public set(key: K, value: V): this {
@@ -182,2 +183,5 @@ this.put(key, value);
   }
+  public peek(index: number): T | undefined {
+    return this.values[index];
+  }
   public get(index: number): T | undefined {
@@ -187,5 +191,2 @@ this.mark(index);
   }
-  public peek(index: number): T | undefined {
-    return this.values[index];
-  }
   public del(index: number): void {
@@ -192,0 +193,0 @@ this.values[index] = undefined;

dict.ts

@@ -0,5 +1,8 @@
+import type { NonNull } from './type';
+
 export interface Dict<K, V> {
+  add?(key: K, value: V): NonNull;
+  set(key: K, value: V): this;
+  get(key: K): V | undefined;
   has(key: K): boolean;
-  get(key: K): V | undefined;
-  set(key: K, value: V): this;
   delete(key: K): boolean;
@@ -6,0 +9,0 @@ }

dict/multimap.ts

@@ -22,8 +22,15 @@ import { IterableDict } from '../dict';
   }
+  public add(key: K, value: V): boolean {
+    const vs = new Ring<V>();
+    vs.push(value);
+    this.memory.set(key, vs);
+    return true;
+  }
   public set(key: K, value: V): this {
-    let vs = this.memory.get(key);
-    if (vs) return vs.push(value), this;
-    vs = new Ring();
+    const vs = this.memory.get(key);
+    if (vs === undefined) {
+      this.add(key, value);
+      return this;
+    }
     vs.push(value);
-    this.memory.set(key, vs);
     return this;
@@ -30,0 +37,0 @@ }

lru.test.ts

@@ -7,2 +7,22 @@ import { LRU } from './lru';
   describe('LRU', () => {
+    it('verify', function () {
+      this.timeout(10 * 1e3);
+
+      const capacity = 100;
+      const cache = new LRU<number, number>(capacity);
+
+      const trials = capacity * 1000;
+      const random = pcg32.random(pcg32.seed(0n, 0n));
+      for (let i = 0; i < trials; ++i) {
+        const key = random() * capacity * 10 | 0;
+        if (cache.has(key)) {
+          assert(cache.get(key) === ~key);
+        }
+        else {
+          cache.add(key, ~key);
+        }
+      }
+      assert(cache.length === capacity);
+    });
+
     class Stats {
@@ -9,0 +29,0 @@ lru = 0;

lru.ts

@@ -42,14 +42,18 @@ import { IterableDict } from './dict';
   }
+  public add(key: K, value: V): boolean {
+    const { dict, list } = this;
+    if (list.length === this.capacity) {
+      this.replace(key, value);
+    }
+    else {
+      const node = new Node(key, value);
+      dict.set(key, node);
+      list.unshift(node);
+    }
+    return true;
+  }
   public set(key: K, value: V): this {
-    const { dict, list } = this;
-    const node = dict.get(key);
+    const node = this.dict.get(key);
     if (node === undefined) {
-      if (list.length === this.capacity) {
-        this.replace(key, value);
-      }
-      else {
-        const node = new Node(key, value);
-        dict.set(key, node);
-        list.unshift(node);
-      }
+      this.add(key, value);
     }
@@ -56,0 +60,0 @@ else {

memoize.ts

@@ -43,3 +43,3 @@ import { isArray } from './alias';
     nullish ||= z === undefined;
-    memory.set(b, z);
+    memory.add?.(b, z) ?? memory.set(b, z);
     return z;
@@ -46,0 +46,0 @@ };

package.json

 {
   "name": "spica",
-  "version": "0.0.703",
+  "version": "0.0.704",
   "description": "Supervisor, Coroutine, Channel, select, AtomicPromise, Cancellation, Cache, List, Queue, Stack, and some utils.",
@@ -5,0 +5,0 @@ "private": false,

src/cache.test.ts

@@ -341,2 +341,22 @@ import { Cache } from './cache';
 
+    it('verify', function () {
+      this.timeout(10 * 1e3);
+
+      const capacity = 100;
+      const cache = new Cache<number, number>(capacity);
+
+      const trials = capacity * 1000;
+      const random = pcg32.random(pcg32.seed(0n, 0n));
+      for (let i = 0; i < trials; ++i) {
+        const key = random() * capacity * 10 | 0;
+        if (cache.has(key)) {
+          assert(cache.get(key) === ~key);
+        }
+        else {
+          cache.add(key, ~key);
+        }
+      }
+      assert(cache.length === capacity);
+    });
+
     if (!navigator.userAgent.includes('Chrome')) return;
@@ -362,3 +382,3 @@
         stats.lru += lru.get(key) ?? +lru.set(key, 1) & 0;
-        stats.dwc += dwc.get(key) ?? +dwc.put(key, 1) & 0;
+        stats.dwc += dwc.get(key) ?? +dwc.add(key, 1) & 0;
       }
@@ -393,3 +413,3 @@ assert(dwc['LRU'].length + dwc['LFU'].length === dwc['dict'].size);
         stats.lru += lru.get(key) ?? +lru.set(key, 1) & 0;
-        stats.dwc += dwc.get(key) ?? +dwc.put(key, 1) & 0;
+        stats.dwc += dwc.get(key) ?? +dwc.add(key, 1) & 0;
       }
@@ -423,3 +443,3 @@ assert(dwc['LRU'].length + dwc['LFU'].length === dwc['dict'].size);
         stats.lru += lru.get(key) ?? +lru.set(key, 1) & 0;
-        stats.dwc += dwc.get(key) ?? +dwc.put(key, 1) & 0;
+        stats.dwc += dwc.get(key) ?? +dwc.add(key, 1) & 0;
       }
@@ -456,3 +476,3 @@ assert(dwc['LRU'].length + dwc['LFU'].length === dwc['dict'].size);
         stats.lru += lru.get(key) ?? +lru.set(key, 1) & 0;
-        stats.dwc += dwc.get(key) ?? +dwc.put(key, 1) & 0;
+        stats.dwc += dwc.get(key) ?? +dwc.add(key, 1) & 0;
       }
@@ -487,3 +507,3 @@ assert(dwc['LRU'].length + dwc['LFU'].length === dwc['dict'].size);
         stats.lru += lru.get(key) ?? +lru.set(key, 1) & 0;
-        stats.dwc += dwc.get(key) ?? +dwc.put(key, 1) & 0;
+        stats.dwc += dwc.get(key) ?? +dwc.add(key, 1) & 0;
       }
@@ -517,4 +537,4 @@ assert(dwc['LRU'].length + dwc['LFU'].length === dwc['dict'].size);
           : random() * capacity / -1 | 0;
-        stats.lru += lru.get(key)! & +(key < 0) || +lru.set(key, 1) & 0;
-        stats.dwc += dwc.get(key)! & +(key < 0) || +dwc.put(key, 1) & 0;
+        stats.lru += lru.get(key) ?? +lru.set(key, 1) & 0;
+        stats.dwc += dwc.get(key) ?? +dwc.add(key, 1) & 0;
       }
@@ -530,3 +550,3 @@ assert(dwc['LRU'].length + dwc['LFU'].length === dwc['dict'].size);
       console.debug('DWC overlap', dwc['overlapLFU'] / dwc['LRU'].length * 100 | 0, dwc['overlapLRU'] / dwc['LFU'].length * 100 | 0);
-      assert(stats.dwc / stats.lru * 100 >>> 0 === 83);
+      assert(stats.dwc / stats.lru * 100 >>> 0 === 95);
     });
@@ -546,3 +566,3 @@
         stats.lru += lru.get(key) ?? +lru.set(key, 1) & 0;
-        stats.dwc += dwc.get(key) ?? +dwc.put(key, 1) & 0;
+        stats.dwc += dwc.get(key) ?? +dwc.add(key, 1) & 0;
       }
@@ -576,3 +596,3 @@ assert(dwc['LRU'].length + dwc['LFU'].length === dwc['dict'].size);
         stats.lru += lru.get(key) ?? +lru.set(key, 1) & 0;
-        stats.dwc += dwc.get(key) ?? +dwc.put(key, 1) & 0;
+        stats.dwc += dwc.get(key) ?? +dwc.add(key, 1) & 0;
       }
@@ -615,3 +635,3 @@ assert(dwc['LRU'].length + dwc['LFU'].length === dwc['dict'].size);
         stats.lru += lru.get(key) ?? +lru.set(key, 1) & 0;
-        stats.dwc += dwc.get(key) ?? +dwc.put(key, 1) & 0;
+        stats.dwc += dwc.get(key) ?? +dwc.add(key, 1) & 0;
         if (trials - i !== capacity) continue;
@@ -661,3 +681,3 @@ stats.lru = 0;
         stats.lru += lru.get(key) ?? +lru.set(key, 1) & 0;
-        stats.dwc += dwc.get(key) ?? +dwc.put(key, 1) & 0;
+        stats.dwc += dwc.get(key) ?? +dwc.add(key, 1) & 0;
         if (trials - i !== capacity) continue;
@@ -707,3 +727,3 @@ stats.lru = 0;
         stats.lru += lru.get(key) ?? +lru.set(key, 1) & 0;
-        stats.dwc += dwc.get(key) ?? +dwc.put(key, 1) & 0;
+        stats.dwc += dwc.get(key) ?? +dwc.add(key, 1) & 0;
         if (trials - i !== capacity) continue;
@@ -741,3 +761,3 @@ stats.lru = 0;
         stats.lru += lru.get(key) ?? +lru.set(key, 1) & 0;
-        stats.dwc += dwc.get(key) ?? +dwc.put(key, 1) & 0;
+        stats.dwc += dwc.get(key) ?? +dwc.add(key, 1) & 0;
       }
@@ -744,0 +764,0 @@ assert(dwc['LRU'].length + dwc['LFU'].length === dwc['dict'].size);

src/cache.ts

@@ -374,5 +374,28 @@ import { max, min, ceil, round } from './alias';
   }
-  public put(key: K, value: V, opts?: { size?: number; age?: number; }): boolean;
-  public put(this: Cache<K, undefined>, key: K, value?: V, opts?: { size?: number; age?: number; }): boolean;
-  public put(key: K, value: V, { size = 1, age = this.age }: { size?: number; age?: number; } = {}): boolean {
+  private update(entry: Entry<K, V>, key: K, value: V, size: number, expiration: number): void {
+    assert(entry.next);
+    const key$ = entry.key;
+    const value$ = entry.value;
+    entry.key = key;
+    entry.value = value;
+    this.$size += size - entry.size;
+    assert(0 < this.size && this.size <= this.resource);
+    entry.size = size;
+    entry.expiration = expiration;
+    if (this.expiration && this.expirations !== undefined && expiration !== Infinity) {
+      entry.enode !== undefined
+        ? this.expirations.update(entry.enode, expiration)
+        : entry.enode = this.expirations.insert(entry, expiration);
+      assert(this.expirations.length <= this.length);
+    }
+    else if (entry.enode !== undefined) {
+      this.expirations!.delete(entry.enode);
+      entry.enode = undefined;
+    }
+    assert(this.LRU.length + this.LFU.length === this.dict.size);
+    this.disposer?.(value$, key$);
+  }
+  public add(key: K, value: V, opts?: { size?: number; age?: number; }, entry?: Entry<K, V>): boolean;
+  public add(this: Cache<K, undefined>, key: K, value?: V, opts?: { size?: number; age?: number; }, entry?: Entry<K, V>): boolean;
+  public add(key: K, value: V, { size = 1, age = this.age }: { size?: number; age?: number; } = {}, entry?: Entry<K, V>): boolean {
     if (size < 1 || this.resource < size || age <= 0) {
@@ -383,2 +406,3 @@ this.disposer?.(value, key);
 
+    assert(!this.dict.has(key));
     const { LRU } = this;
@@ -388,4 +412,2 @@ const expiration = age === Infinity
       : now() + age;
-    let entry = this.dict.get(key);
-    const match = entry !== undefined;
     entry = this.ensure(size, entry, true);
@@ -413,38 +435,37 @@ if (entry === undefined) {
       }
+      return true;
+    }
+
+    assert(entry === LRU.head!.prev);
+    entry.region === 'LFU' && --this.overlapLFU;
+    assert(this.overlapLFU >= 0);
+    this.dict.delete(entry.key);
+    this.dict.set(key, entry);
+    assert(this.LRU.length + this.LFU.length === this.dict.size);
+    assert(this.dict.size <= this.capacity);
+    entry.region = 'LRU';
+    LRU.head = entry;
+    this.update(entry, key, value, size, expiration);
+    return true;
+  }
+  public put(key: K, value: V, opts?: { size?: number; age?: number; }): boolean;
+  public put(this: Cache<K, undefined>, key: K, value?: V, opts?: { size?: number; age?: number; }): boolean;
+  public put(key: K, value: V, { size = 1, age = this.age }: { size?: number; age?: number; } = {}): boolean {
+    if (size < 1 || this.resource < size || age <= 0) {
+      this.disposer?.(value, key);
       return false;
     }
 
-    assert(entry.next);
-    const key$ = entry.key;
-    const value$ = entry.value;
-    if (!match) {
-      assert(entry === LRU.head!.prev);
-      entry.region === 'LFU' && --this.overlapLFU;
-      assert(this.overlapLFU >= 0);
-      this.dict.delete(key$);
-      this.dict.set(key, entry);
-      assert(this.LRU.length + this.LFU.length === this.dict.size);
-      assert(this.dict.size <= this.capacity);
-      entry.key = key;
-      entry.region = 'LRU';
-      LRU.head = entry;
+    let entry = this.dict.get(key);
+    const match = entry !== undefined;
+    entry = this.ensure(size, entry, true);
+    if (!match || entry === undefined) {
+      this.add(key, value, { size, age }, entry);
+      return match;
     }
-    assert(this.dict.has(key));
-    entry.value = value;
-    this.$size += size - entry.size;
-    assert(0 < this.size && this.size <= this.resource);
-    entry.size = size;
-    entry.expiration = expiration;
-    if (this.expiration && this.expirations !== undefined && expiration !== Infinity) {
-      entry.enode !== undefined
-        ? this.expirations.update(entry.enode, expiration)
-        : entry.enode = this.expirations.insert(entry, expiration);
-      assert(this.expirations.length <= this.length);
-    }
-    else if (entry.enode !== undefined) {
-      this.expirations!.delete(entry.enode);
-      entry.enode = undefined;
-    }
-    assert(this.LRU.length + this.LFU.length === this.dict.size);
-    this.disposer?.(value$, key$);
+
+    const expiration = age === Infinity
+      ? age
+      : now() + age;
+    this.update(entry, key, value, size, expiration);
     return match;
@@ -469,3 +490,3 @@ }
     }
-    this.update(entry);
+    this.replace(entry);
     return entry.value;
@@ -535,3 +556,3 @@ }
   }
-  private update(entry: Entry<K, V>): void {
+  private replace(entry: Entry<K, V>): void {
     const { LRU, LFU } = this;
@@ -538,0 +559,0 @@ this.sweeper.hit();

src/clock.test.ts

@@ -42,2 +42,25 @@ import { Clock, CLOCK } from './clock';
 
+    it('verify', function () {
+      this.timeout(10 * 1e3);
+
+      const capacity = 96;
+      const clock = new Clock<number, number>(capacity);
+
+      const trials = capacity * 1000;
+      const random = pcg32.random(pcg32.seed(0n, 0n));
+      for (let i = 0; i < trials; ++i) {
+        const key = random() * capacity * 10 | 0;
+        if (clock.has(key)) {
+          assert(clock.get(key) === ~key);
+        }
+        else {
+          clock.add(key, ~key);
+        }
+        assert(clock.length <= capacity);
+        assert(clock['values'].length === clock.length);
+        assert(clock['values'].length === clock['dict'].size);
+      }
+      assert(clock.length === capacity);
+    });
+
     class Stats {
@@ -44,0 +67,0 @@ clock = 0;

src/clock.ts

@@ -49,9 +49,3 @@ import { ceil } from './alias';
   }
-  public put(key: K, value: V): number {
-    const index = this.dict.get(key);
-    if (index !== undefined) {
-      this.mark(index);
-      this.values[index] = value;
-      return index;
-    }
+  public add(key: K, value: V): number {
     const { capacity, refs } = this;
@@ -81,2 +75,9 @@ let hand = this.hand;
   }
+  public put(key: K, value: V): number {
+    const index = this.dict.get(key);
+    if (index === undefined) return this.add(key, value);
+    this.mark(index);
+    this.values[index] = value;
+    return index;
+  }
   public set(key: K, value: V): this {
@@ -182,2 +183,5 @@ this.put(key, value);
   }
+  public peek(index: number): T | undefined {
+    return this.values[index];
+  }
   public get(index: number): T | undefined {
@@ -187,5 +191,2 @@ this.mark(index);
   }
-  public peek(index: number): T | undefined {
-    return this.values[index];
-  }
   public del(index: number): void {
@@ -192,0 +193,0 @@ this.values[index] = undefined;

src/dict.ts

@@ -0,5 +1,8 @@
+import type { NonNull } from './type';
+
 export interface Dict<K, V> {
+  add?(key: K, value: V): NonNull;
+  set(key: K, value: V): this;
+  get(key: K): V | undefined;
   has(key: K): boolean;
-  get(key: K): V | undefined;
-  set(key: K, value: V): this;
   delete(key: K): boolean;
@@ -6,0 +9,0 @@ }

src/dict/multimap.ts

@@ -22,8 +22,15 @@ import { IterableDict } from '../dict';
   }
+  public add(key: K, value: V): boolean {
+    const vs = new Ring<V>();
+    vs.push(value);
+    this.memory.set(key, vs);
+    return true;
+  }
   public set(key: K, value: V): this {
-    let vs = this.memory.get(key);
-    if (vs) return vs.push(value), this;
-    vs = new Ring();
+    const vs = this.memory.get(key);
+    if (vs === undefined) {
+      this.add(key, value);
+      return this;
+    }
     vs.push(value);
-    this.memory.set(key, vs);
     return this;
@@ -30,0 +37,0 @@ }

src/lru.test.ts

@@ -7,2 +7,22 @@ import { LRU } from './lru';
   describe('LRU', () => {
+    it('verify', function () {
+      this.timeout(10 * 1e3);
+
+      const capacity = 100;
+      const cache = new LRU<number, number>(capacity);
+
+      const trials = capacity * 1000;
+      const random = pcg32.random(pcg32.seed(0n, 0n));
+      for (let i = 0; i < trials; ++i) {
+        const key = random() * capacity * 10 | 0;
+        if (cache.has(key)) {
+          assert(cache.get(key) === ~key);
+        }
+        else {
+          cache.add(key, ~key);
+        }
+      }
+      assert(cache.length === capacity);
+    });
+
     class Stats {
@@ -9,0 +29,0 @@ lru = 0;

src/lru.ts

@@ -42,14 +42,18 @@ import { IterableDict } from './dict';
   }
+  public add(key: K, value: V): boolean {
+    const { dict, list } = this;
+    if (list.length === this.capacity) {
+      this.replace(key, value);
+    }
+    else {
+      const node = new Node(key, value);
+      dict.set(key, node);
+      list.unshift(node);
+    }
+    return true;
+  }
   public set(key: K, value: V): this {
-    const { dict, list } = this;
-    const node = dict.get(key);
+    const node = this.dict.get(key);
     if (node === undefined) {
-      if (list.length === this.capacity) {
-        this.replace(key, value);
-      }
-      else {
-        const node = new Node(key, value);
-        dict.set(key, node);
-        list.unshift(node);
-      }
+      this.add(key, value);
     }
@@ -56,0 +60,0 @@ else {

src/memoize.ts

@@ -43,3 +43,3 @@ import { isArray } from './alias';
     nullish ||= z === undefined;
-    memory.set(b, z);
+    memory.add?.(b, z) ?? memory.set(b, z);
     return z;
@@ -46,0 +46,0 @@ };

src/type.ts

 import { isArray, toString, ObjectGetPrototypeOf } from './alias';
 
-type Falsy = undefined | false | 0 | '' | null | void;
+export type NonNull = boolean | number | bigint | string | symbol | object;
+type Falsy = undefined | false | 0 | 0n | '' | null | void;
 type Unique = typeof Unique;
@@ -5,0 +6,0 @@ declare const Unique: unique symbol;

type.ts

 import { isArray, toString, ObjectGetPrototypeOf } from './alias';
 
-type Falsy = undefined | false | 0 | '' | null | void;
+export type NonNull = boolean | number | bigint | string | symbol | object;
+type Falsy = undefined | false | 0 | 0n | '' | null | void;
 type Unique = typeof Unique;
@@ -5,0 +6,0 @@ declare const Unique: unique symbol;

No alert changes

Improved metrics

Total package byte prevSize

1158112

increased by0.54%

Lines of code

32453

increased by0.55%

No dependency changes