spica - npm Package Compare versions

Comparing version 0.0.716 to 0.0.717

clock.test.ts

@@ -41,2 +41,15 @@ import { Clock } from './clock';
       assert(clock.get(2) === 2);
+      assert(clock.delete(2) === true);
+      clock.set(2, 2);
+      assert(clock.delete(31) === true);
+      clock.set(32, 32);
+      assert(clock.get(3) === 3);
+      assert(clock.length === 32);
+      assert(clock.delete(30) === true);
+      assert(clock.delete(29) === true);
+      clock.set(33, 33);
+      clock.set(34, 34);
+      assert(clock.get(4) === 4);
+      assert(clock.get(5) === undefined);
+      assert(clock.length === 31);
     });
@@ -43,0 +56,0 @@

clock.ts

@@ -10,3 +10,7 @@ import { ceil, log2 } from './alias';
 
+type empty = typeof empty;
+const empty = Symbol('empty');
+
 export class Clock<K, V> implements IterableDict<K, V> {
+  // Capacity is rounded up to multiples of 32.
   constructor(
@@ -20,3 +24,3 @@ private readonly capacity: number,
   private keys: (K | undefined)[] = [];
-  private values: (V | undefined)[] = [];
+  private values: (V | undefined | empty)[] = [];
   private refs: Uint32Array;
@@ -37,14 +41,16 @@ private hand = 0;
   }
+  private initial: 1 | 0 = 1;
   private locate(hand: number, key: K, value: V): void {
-    this.$length === this.capacity
-      ? this.dict.delete(this.keys[hand]!)
+    const { capacity, dict, keys, values } = this;
+    this.$length === capacity || this.initial === 0 && values[hand] !== empty
+      ? dict.delete(keys[hand]!)
       : ++this.$length;
     assert(!this.dict.has(key));
-    this.dict.set(key, hand);
+    dict.set(key, hand);
     assert(this.dict.size <= this.capacity);
     assert(this.$length === this.dict.size);
-    this.keys[hand] = key;
-    this.values[hand] = value;
-    this.hand = ++hand === this.capacity
-      ? 0
+    keys[hand] = key;
+    values[hand] = value;
+    this.hand = ++hand === capacity
+      ? this.initial = 0
       : hand;
@@ -80,3 +86,2 @@ }
     if (index === undefined) return this.add(key, value);
-    this.mark(index);
     this.values[index] = value;
@@ -93,3 +98,3 @@ return index;
     this.mark(index);
-    return this.values[index];
+    return this.values[index] as V;
   }
@@ -102,8 +107,18 @@ public has(key: K): boolean {
     if (index === undefined) return false;
-    this.dict.delete(key);
-    this.keys[index] = undefined;
-    this.values[index] = undefined;
-    this.unmark(index);
+    // 末尾と削除対象を交換して削除する。
+    // 次の挿入の前に次の削除が行われると交換できないが稀なため対処しない。
+    const { hand, dict, keys, values, refs } = this;
+    dict.delete(key);
     --this.$length;
     assert(this.$length === this.dict.size);
+    const k = keys[index] = keys[hand];
+    const v = values[index] = values[hand];
+    keys[hand] = undefined;
+    values[hand] = empty;
+    this.unmark(index);
+    if (index === hand || v === empty) return true;
+    assert(this.dict.has(k!));
+    dict.set(k!, index);
+    refs[index >>> DIGIT] |= refs[hand >>> DIGIT] & 1 << (hand & MASK);
+    this.unmark(hand);
     return true;
@@ -122,3 +137,3 @@ }
     for (const index of this.dict.values()) {
-      yield [keys[index]!, values[index]!];
+      yield [keys[index]!, values[index]! as V];
     }
@@ -125,0 +140,0 @@ return;

package.json

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

src/clock.test.ts

@@ -41,2 +41,15 @@ import { Clock } from './clock';
       assert(clock.get(2) === 2);
+      assert(clock.delete(2) === true);
+      clock.set(2, 2);
+      assert(clock.delete(31) === true);
+      clock.set(32, 32);
+      assert(clock.get(3) === 3);
+      assert(clock.length === 32);
+      assert(clock.delete(30) === true);
+      assert(clock.delete(29) === true);
+      clock.set(33, 33);
+      clock.set(34, 34);
+      assert(clock.get(4) === 4);
+      assert(clock.get(5) === undefined);
+      assert(clock.length === 31);
     });
@@ -43,0 +56,0 @@

src/clock.ts

@@ -10,3 +10,7 @@ import { ceil, log2 } from './alias';
 
+type empty = typeof empty;
+const empty = Symbol('empty');
+
 export class Clock<K, V> implements IterableDict<K, V> {
+  // Capacity is rounded up to multiples of 32.
   constructor(
@@ -20,3 +24,3 @@ private readonly capacity: number,
   private keys: (K | undefined)[] = [];
-  private values: (V | undefined)[] = [];
+  private values: (V | undefined | empty)[] = [];
   private refs: Uint32Array;
@@ -37,14 +41,16 @@ private hand = 0;
   }
+  private initial: 1 | 0 = 1;
   private locate(hand: number, key: K, value: V): void {
-    this.$length === this.capacity
-      ? this.dict.delete(this.keys[hand]!)
+    const { capacity, dict, keys, values } = this;
+    this.$length === capacity || this.initial === 0 && values[hand] !== empty
+      ? dict.delete(keys[hand]!)
       : ++this.$length;
     assert(!this.dict.has(key));
-    this.dict.set(key, hand);
+    dict.set(key, hand);
     assert(this.dict.size <= this.capacity);
     assert(this.$length === this.dict.size);
-    this.keys[hand] = key;
-    this.values[hand] = value;
-    this.hand = ++hand === this.capacity
-      ? 0
+    keys[hand] = key;
+    values[hand] = value;
+    this.hand = ++hand === capacity
+      ? this.initial = 0
       : hand;
@@ -80,3 +86,2 @@ }
     if (index === undefined) return this.add(key, value);
-    this.mark(index);
     this.values[index] = value;
@@ -93,3 +98,3 @@ return index;
     this.mark(index);
-    return this.values[index];
+    return this.values[index] as V;
   }
@@ -102,8 +107,18 @@ public has(key: K): boolean {
     if (index === undefined) return false;
-    this.dict.delete(key);
-    this.keys[index] = undefined;
-    this.values[index] = undefined;
-    this.unmark(index);
+    // 末尾と削除対象を交換して削除する。
+    // 次の挿入の前に次の削除が行われると交換できないが稀なため対処しない。
+    const { hand, dict, keys, values, refs } = this;
+    dict.delete(key);
     --this.$length;
     assert(this.$length === this.dict.size);
+    const k = keys[index] = keys[hand];
+    const v = values[index] = values[hand];
+    keys[hand] = undefined;
+    values[hand] = empty;
+    this.unmark(index);
+    if (index === hand || v === empty) return true;
+    assert(this.dict.has(k!));
+    dict.set(k!, index);
+    refs[index >>> DIGIT] |= refs[hand >>> DIGIT] & 1 << (hand & MASK);
+    this.unmark(hand);
     return true;
@@ -122,3 +137,3 @@ }
     for (const index of this.dict.values()) {
-      yield [keys[index]!, values[index]!];
+      yield [keys[index]!, values[index]! as V];
     }
@@ -125,0 +140,0 @@ return;

No alert changes

Improved metrics

Total package byte prevSize

1150545

increased by0.2%

Lines of code

32195

increased by0.17%

No dependency changes