1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91 | import { fromHex, toHex } from "./util";
/**
* Memory-compact set + insertion-ordered list of object ids. A JS
* Set<string> of 40-char hex strings costs ~100 bytes per entry — at
* Linux scale (10M objects) that is gigabytes. This stores raw 20-byte
* digests in typed arrays: ~20B per entry plus a u32 open-addressing table.
*/
export class OidSet {
private table: Uint32Array; // 1-based indices into the entry list; 0 = empty
private mask: number;
private data: Uint8Array; // 20 bytes per entry, insertion order
private count = 0;
constructor(expected = 1024) {
let cap = 2048;
while (cap < expected * 2) cap *= 2;
this.table = new Uint32Array(cap);
this.mask = cap - 1;
this.data = new Uint8Array(Math.max(expected, 1024) * 20);
}
get size(): number {
return this.count;
}
private hashAt(bytes: Uint8Array, off: number): number {
// oids are uniformly random; the first 4 bytes are a fine hash
return ((bytes[off] << 24) | (bytes[off + 1] << 16) | (bytes[off + 2] << 8) | bytes[off + 3]) >>> 0;
}
private equalsEntry(idx: number, bytes: Uint8Array, off: number): boolean {
const base = idx * 20;
for (let i = 0; i < 20; i++) {
if (this.data[base + i] !== bytes[off + i]) return false;
}
return true;
}
private grow(): void {
const newTable = new Uint32Array(this.table.length * 2);
const newMask = newTable.length - 1;
for (let i = 0; i < this.count; i++) {
let slot = this.hashAt(this.data, i * 20) & newMask;
while (newTable[slot] !== 0) slot = (slot + 1) & newMask;
newTable[slot] = i + 1;
}
this.table = newTable;
this.mask = newMask;
}
/** Adds a hex oid; returns false if it was already present. */
addHex(hex: string): boolean {
return this.addBytes(fromHex(hex), 0);
}
addBytes(bytes: Uint8Array, off: number): boolean {
if ((this.count + 1) * 2 > this.table.length) this.grow();
let slot = this.hashAt(bytes, off) & this.mask;
while (this.table[slot] !== 0) {
if (this.equalsEntry(this.table[slot] - 1, bytes, off)) return false;
slot = (slot + 1) & this.mask;
}
if ((this.count + 1) * 20 > this.data.length) {
const bigger = new Uint8Array(this.data.length * 2);
bigger.set(this.data);
this.data = bigger;
}
this.data.set(bytes.subarray(off, off + 20), this.count * 20);
this.table[slot] = ++this.count;
return true;
}
hasHex(hex: string): boolean {
return this.hasBytes(fromHex(hex), 0);
}
hasBytes(bytes: Uint8Array, off: number): boolean {
let slot = this.hashAt(bytes, off) & this.mask;
while (this.table[slot] !== 0) {
if (this.equalsEntry(this.table[slot] - 1, bytes, off)) return true;
slot = (slot + 1) & this.mask;
}
return false;
}
/** Hex oid of the i-th inserted entry. */
atHex(i: number): string {
return toHex(this.data.subarray(i * 20, i * 20 + 20));
}
}
|