nish/collections
The global Map and Set (docs/wp32-map.md).
import {
Map,
Set,
forEachElement,
forEachEntry,
forEachValue,
} from "nish/collections";
const counts = new Map<string, i32>()
const seen = new Set<string>()
for (const w of ["to", "be", "or", "not", "to", "be"]) {
counts.set(w, (counts.get(w) ?? 0) + 1)
seen.add(w)
}
for (const w of counts.keys()) {
console.log(`${w} ${counts.get(w) ?? 0}`) // "to 2", "be 2", "or 1", ...
}
seen.size // 4, and seen.has("or") is true
forEachElement
Calls f with each element of s, in insertion order: what s.forEach(f) compiles to.
forEachEntry
Calls f with the value and the key of each entry of m, in insertion order: what m.forEach(f) compiles to when f takes two parameters.
forEachValue
Calls f with the value of each entry of m, in insertion order: what m.forEach(f) compiles to when f takes one parameter.
Map
A key-value table in insertion order, with JavaScript's semantics: keys are compared by SameValueZero, a key set again keeps its place, and a deleted key set again goes to the end.
Set
A set of keys in insertion order: Map's table with no values, and the same probe.
A program does not import this module. Naming Map or Set is what loads
it, unless the module declares or imports a Map or Set of its own, and
the compiler emits every instance used, and every function here that it
reaches, into the module that uses it as internal functions. So this file
writes no .ll of its own, and a one-file program that names Map is still
one module (§4.1). Under Node, and under tsc, Map and Set are the
platform's, so nothing here runs there.
The layout is §2's
Entries sit in insertion order in parallel arrays,
entryKeys, entryValues and entryHashes, and entryHashes holds the
full 32-bit hash of each. The bucket table slots is open addressing with
linear probing, and a bucket is one u32:
bits 31..24 the top eight bits of the key's hash (the fingerprint)
bits 23..0 the entry's index plus one
An empty bucket is 0. A deleted entry's bucket is 0x01000000 (16777216),
fingerprint 1 and index field 0, which no live entry has; its stored hash is
set to 0, which is why a computed hash of 0 is moved to 1. A probe reads the
entry arrays only when a bucket's fingerprint matches, and compares the
stored hash before the key, so a miss almost never touches a key, and a hit
compares one. Growth and compaction re-file the buckets from the stored
hashes and never hash a key again.
Every operation is one probe
probe answers a packed i64: the entry
it found and the bucket that points at it, or the empty bucket it stopped at
and the key's hash. set and add insert through that result, and nothing
here asks has and then set. probe, valueAt, setValueAt and
insertAt are the pieces a fused lookup writes through, and they write
nothing but what their names say: probe writes no memory at all.
A program sees only the JavaScript members (§7), size, get, set/add,
has, delete and clear, and keys() and values() as the iterable of
a for...of. Neither get nor the iterators has a method here: get's
V | undefined never crosses a call, so the compiler lowers it to probe
and, where found, valueAt (§3.2), and an iterator is not a value, so a
for...of over one is lowered to walkOpen, walkNext, keyAt or
valueAt, and walkClose (§6.2). The rest of this file is refused by name
outside it.
Functions
forEachElement
Calls f with each element of s, in insertion order: what s.forEach(f)
compiles to. The walk is a for...of over s, with its rule for elements
the callback adds or deletes.
const forEachElement: <T>(
s: Set<T>,
f: (value: T) => void,
) => void
sSet<T>requiredthe set walked; the callback may change it.
f(value: T) => voidrequiredcalled once per live element.
forEachEntry
Calls f with the value and the key of each entry of m, in insertion
order: what m.forEach(f) compiles to when f takes two parameters. It is
the walk a for...of over m.keys() makes, and reads the value from the
entry the walk is on, so each entry costs no probe. An entry the callback
adds is visited and one it deletes is not, as Map.prototype.forEach does.
Placed after storedKey so that no earlier line moved.
const forEachEntry: <K, V>(
m: Map<K, V>,
f: (value: V, key: K) => void,
) => void
mMap<K, V>requiredthe table walked; the callback may change it.
f(value: V, key: K) => voidrequiredcalled once per live entry, with its value and then its key.
forEachValue
Calls f with the value of each entry of m, in insertion order: what
m.forEach(f) compiles to when f takes one parameter. The walk is
forEachEntry's.
const forEachValue: <K, V>(
m: Map<K, V>,
f: (value: V) => void,
) => void
mMap<K, V>requiredthe table walked; the callback may change it.
f(value: V) => voidrequiredcalled once per live entry, with its value.
Classes
Map
A key-value table in insertion order, with JavaScript's semantics: keys are compared by SameValueZero, a key set again keeps its place, and a deleted key set again goes to the end.
class Map<K, V>
| Member | |
|---|---|
new Map<K, V>() |
An empty map. |
size: number |
How many entries are live. The one field a program may read, and it may not write it. |
clear(): void |
Empty the table in place: the buckets are zeroed and the entries truncated, or, while a loop walks the table, marked dead and kept (§6.1). |
delete(key: K): boolean |
Removes the entry for key, if there is one; the others keep their order. |
has(key: K): boolean |
Whether the map has an entry for key. |
set(key: K, value: V): Map<K, V> |
Set key to value, in place when it is there and at the end when it is not: one probe. |
Set
A set of keys in insertion order: Map's table with no values, and the same probe.
class Set<T>
| Member | |
|---|---|
new Set<T>() |
An empty set. |
size: number |
How many elements are live. The one field a program may read, and it may not write it. |
add(key: T): Set<T> |
Add key at the end when it is not there already: one probe. |
clear(): void |
Removes every key, keeping the table's memory. |
delete(key: T): boolean |
Removes key, if it is there; the others keep their order. |
has(key: T): boolean |
Whether key is in the set. |

