envzn
0.8 · beta · not released

Library / Collections / Dictionaries / ProHashDictionary

CLASSIMPLEMENTS Dictionary<BinaryWord, V, H>

ProHashDictionary

The DoS-RESISTANT dictionary, rebuilt on the byte-keyed substrate that made StringKeyedDictionary beat C. Pure Envzn, zero-dep beyond the SipHash key shim.

Constructors 1

INIT()

Methods 27

MODIFY METHOD insertSlice(REFERENCE binary[] buf, int64 off, int64 len, V value) RETURNS STATUS
modifies
METHOD lookupFastSlice(REFERENCE binary[] buf, int64 off, int64 len) RETURNS boolean
reads

Comma-return lookup — no pipe-XOR (V | STATUS) tuple on the hot path.

METHOD containsSlice(REFERENCE binary[] buf, int64 off, int64 len) RETURNS boolean
reads
MODIFY METHOD removeSlice(REFERENCE binary[] buf, int64 off, int64 len) RETURNS boolean
modifies

Remove. Unlinks the entry from the bucket's member chain, then RE-INDEXES the bucket: a treeified bucket that has fallen to the untreeify threshold drops its red-black index and reverts to a plain chain (hysteresis: treeify at >8, untreeify at <=6, so churn around the boundary cannot thrash); one still above it rebuilds the index. Rebuilding rather than running the CLRS red-black delete-fixup is a deliberate, bounded simplification (O(depth)) — labelled, not hidden. It keeps the single most bug-prone routine in a red-black tree out of the kernel, and remove is not the hot path; lookup and insert use the real tree.

MODIFY METHOD insert(REFERENCE binary[] key, V value) RETURNS STATUS
modifies
METHOD lookupFast(REFERENCE binary[] key) RETURNS boolean
reads
METHOD __op_index__(REFERENCE binary[] key) RETURNS V
reads

Direct value read — d[key]. V default (0) on a miss. No pipe-XOR.

METHOD lookup(REFERENCE binary[] key) RETURNS | V
reads

Pipe-XOR lookup — the kernel idiom, kept OFF the hot path.

METHOD lookupRef(REFERENCE binary[] key) RETURNS | MUTABLE REFERENCE V
reads
METHOD contains(REFERENCE binary[] key) RETURNS boolean
reads
MODIFY METHOD remove(REFERENCE binary[] key) RETURNS boolean
modifies
METHOD isEmpty() RETURNS boolean
reads
METHOD size() RETURNS int64
reads
MODIFY METHOD clear() RETURNS void
modifies
METHOD bucketIndexOf(REFERENCE binary[] key) RETURNS int64
reads

The bucket a key currently maps to.

Exposed for TESTABILITY of the adaptive tier. SipHash keying means an attacker cannot force colliding keys — which also means a TEST cannot, so the chain->tree escalation would otherwise be unreachable, untested kernel code. This lets a test group keys that share a bucket and drive the escalation deterministically.

It does NOT weaken the DoS guarantee: hash-flooding's threat model is "the attacker supplies KEYS (data) that the victim hashes", not "the attacker calls methods on the victim's dictionary". Anyone able to invoke this already has code execution in-process, at which point the hash is not the weak link. Do not, however, echo the result across a trust boundary — that WOULD hand out a collision oracle.

METHOD maxBucketDepth() RETURNS int64
reads

Deepest bucket in the table — the clustering metric the adaptive tier bounds.

METHOD treeifiedBuckets() RETURNS int64
reads

How many buckets have escalated to a red-black tree. Zero under normal load — non-zero means collisions got deep (the adaptive tier is doing its job). Exposed so the escalation is TESTABLE and observable, not a silent internal.

METHOD iterator() RETURNS ReferenceIterator[BinaryWord]
reads

One BinaryWord per live entry, borrowed from this dictionary's key pool. Valid only while the dictionary is unmodified: an insert may grow the pool and a rehash may move it.

METHOD keys() RETURNS LinkedList[BinaryWord]
reads
MODIFY METHOD insertCopy(REFERENCE BinaryWord key, REFERENCE V value) RETURNS STATUS
modifies
MODIFY METHOD insert(BinaryWord key, V value) RETURNS STATUS
modifies
METHOD lookupFast(REFERENCE BinaryWord key) RETURNS boolean
reads

Dictionary.lookupFast — the interface-shaped (BinaryWord-keyed) peer of the binary[] slice form above. K is BinaryWord for this class, so this is the overload that satisfies the interface; the slice form stays for the zero-copy call sites that already hold a buffer and a range.

METHOD lookup(REFERENCE BinaryWord key) RETURNS | MUTABLE REFERENCE V
reads
METHOD contains(REFERENCE BinaryWord key) RETURNS boolean
reads
MODIFY METHOD remove(REFERENCE BinaryWord key) RETURNS | BinaryWord
modifies

The removed key is a word over this dictionary's own pool. A freed entry is recycled through freeHead but its BYTES stay in the pool, so the returned word reads correctly until the pool is next compacted.

METHOD equals(REFERENCE Dictionary[BinaryWord, V, H] other) RETURNS boolean
reads

Equal when both hold the same keys mapped to the same values. Walks the smaller surface — this dictionary's entries — and asks the other by lookup, so the cost is one hash per key rather than a cross product. Two dictionaries are equal when they hold the SAME ASSOCIATIONS: the same keys, each mapping to an EQUAL VALUE.

Not merely the same KEYSET. That would rank {a:1} equal to {a:2}, so two "equal" dictionaries would answer lookup(a) differently and neither could stand in for the other — which is the whole point of an equivalence. Keys-AND-values is what C++ (map and unordered_map), Rust, Swift, Julia, Python and Java all specify. Keyset equality is a perfectly good relation, but it is equality of the DOMAIN rather than of the dictionary, and it deserves its own name (hasSameKeys) rather than this one.

Equal sizes plus a one-way walk is sufficient: with the counts already equal, other cannot carry a key this one lacks unless this one also carries a key other lacks — and the walk would have found that.

METHOD clone() RETURNS Dictionary[BinaryWord, V, H]
reads

Deep copy. Returns the Dictionary INTERFACE, not the concrete class — the class is HIDDEN, so its name may appear only as a CREATE target. The copy goes in through the interface's own insert, since insertSlice is this class's and not the interface's.