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

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>required

the set walked; the callback may change it.

f(value: T) => voidrequired

called 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>required

the table walked; the callback may change it.

f(value: V, key: K) => voidrequired

called 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>required

the table walked; the callback may change it.

f(value: V) => voidrequired

called 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.