tur/mutmap
MutableMap[K V]: mutable open-addressed hash table.
Uses linear probing. Unlike tur/map, mutations happen in-place.
Since: Phase F5
MutableMap
(defstruct MutableMap :heap [K V] (storage :ptr<void>))
parameterized in-place hash table with key K, value V.
Since: Phase F5 (cross-plan-followups)
mutmap-new
(mutmap-new [K V])
create a new empty MutableMap[K V] with default initial capacity (16 slots).
An empty MutableMap[K V]. K/V are inferred from later use (e.g. the first mutmap-set!), like vec-new's element type.
(mutmap-new) ; => empty MutableMap
Since: Phase F5
mutmap-len
(mutmap-len [K V])
live entry count (excludes tombstones).
| m | MutableMap[K V] |
Number of live (key, value) entries.
(mutmap-len mm) ; => 0
Since: Phase F5
mutmap-set!
(mutmap-set! [K V])
insert or update (key, value). Mutates m in place.
| m | MutableMap[K V] | |
| h | precomputed hash of key (Hash[K]) | |
| key | key | |
| val | value |
nil.
(mutmap-set! mm 1 1 100)
Since: Phase F5
mutmap-get
(mutmap-get [K V])
look up the value bound to key, or 0 if absent.
| m | MutableMap[K V] | |
| h | precomputed hash of key (Hash[K]) | |
| key | key |
The bound value, or 0 if key is not present. Callers needing to distinguish "absent" from "value = 0" should use mutmap-has? first.
(mutmap-get mm 1 1) ; => 100
Since: Phase F5
mutmap-has?
(mutmap-has? [K V])
check whether key is present.
| m | MutableMap[K V] | |
| h | precomputed hash of key | |
| key | key |
true if key is present (value of any kind), false otherwise.
(mutmap-has? mm 1 1) ; => true
Since: Phase F5
mutmap-delete!
(mutmap-delete! [K V])
remove (key, value) if present. Mutates m in place. Leaves a tombstone so probe chains stay intact.
| m | MutableMap[K V] | |
| h | precomputed hash of key | |
| key | key |
true if key was present (and is now removed), false otherwise.
(mutmap-delete! mm 1 1) ; => true
Since: Phase F5
mutmap-cap
(mutmap-cap [K V])
slot-array capacity (number of probe slots, a power of two).
| m | MutableMap[K V] |
The backing storage capacity (>= mutmap-len; includes EMPTY and DELETED slots). Used as the iteration bound for mutmap-slot-* walks.
(mutmap-cap mm) ; => 16
Since: Phase F5
mutmap-slot-occupied?
(mutmap-slot-occupied? [K V])
is slot i a live (OCCUPIED) entry?
| m | MutableMap[K V] | |
| i | slot index in [0, mutmap-cap m) |
true iff slot i holds a live entry (not EMPTY, not a DELETED tombstone).
(mutmap-slot-occupied? mm 0) ; => true / false
Since: Phase F5
mutmap-slot-hash
(mutmap-slot-hash [K V])
precomputed hash stored in slot i.
| m | MutableMap[K V] | |
| i | slot index in [0, mutmap-cap m) |
The hash recorded for slot i (meaningful only when the slot is OCCUPIED).
(mutmap-slot-hash mm 0)
Since: Phase F5
mutmap-slot-key
(mutmap-slot-key [K V])
key stored in slot i.
| m | MutableMap[K V] | |
| i | slot index in [0, mutmap-cap m) |
The key in slot i (meaningful only when the slot is OCCUPIED).
(mutmap-slot-key mm 0)
Since: Phase F5
mutmap-slot-value
(mutmap-slot-value [K V])
value stored in slot i.
| m | MutableMap[K V] | |
| i | slot index in [0, mutmap-cap m) |
The value in slot i (meaningful only when the slot is OCCUPIED).
(mutmap-slot-value mm 0)
Since: Phase F5
mutmap-eq-storage?
(mutmap-eq-storage? [V])
structural equality over two raw storage pointers.
mutmap-eq-loop
(mutmap-eq-loop [K V])
pure-Turmeric structural-equality walk (self-tail slot loop).
Path A specializes this per (K V) at the Eq [MutableMap] dispatch site; the self-tail-recursive spec is turned into a loop by the C compiler's sibling-call optimization (the same shape as vec-eq-loop's typed spec), so a large table iterates in constant stack (verified: a 200k-entry .eq? runs in a 512KB stack). Unlike the inline-C mutmap-eq-storage? carrier core (kept for the public mutmap-eq? wrapper / abstract callers), the receivers flow by their honest (MutableMap K V) type and the iteration is expressed with the mutmap-slot-* accessors -- no fat-closure inline-C dispatch. For each live slot of m1 the matching key is looked up in m2 (via mutmap-has?/mutmap-get) and the values compared by val-cmp.
| m1 | first MutableMap[K V] | |
| m2 | second MutableMap[K V] | |
| i | current slot index (start at 0) | |
| cap | slot bound (mutmap-cap m1) | |
| val-cmp | value comparator fn [a :V b :V] :bool |
true iff every live entry of m1[i..cap) is present in m2 with an equal value under val-cmp.
(mutmap-eq-loop a b 0 (mutmap-cap a) (fn [x y] (= x y)))
Since: Phase F5
mutmap-eq?
(mutmap-eq? [K V W])
structural equality. Two MutableMap[K V]s are equal iff they have the same live (key, value) entries (any order) per a supplied value comparator. This public wrapper reads each map's K/V-agnostic storage field directly and delegates to the shared inline-C core (mutmap-eq-storage?, a stack-safe C loop) so it is safe for direct / abstract callers of any size. The Eq [MutableMap] instance instead dispatches through the pure-Turmeric mutmap-eq-loop (TCO'd inside its by-value spec).
| m1 | MutableMap[K V] | |
| m2 | MutableMap[K V] | |
| val-cmp | comparator fn [a :int b :int] :bool for values |
true iff m1 and m2 have the same set of (key, value) pairs.
(mutmap-eq? ma mb (fn [a b] (= a b)))
Since: Phase F5
mutmap-free
(mutmap-free [K V])
free the storage and wrapper.
| m | MutableMap[K V] to free |
(mutmap-free mm)
Since: Phase F5
Eq[MutableMap]
(definstance Eq [MutableMap])
structural equality using the value type's Eq.