core/map
Shared: available on every enabled target.
An insertion-ordered hash map, key equality and hash evidence, and explicit entry walks.
The module supplies equality and hashing for ten integer scalars, bool and []u8. core/text adds UTF-8 evidence. Alternative policies use a distinct wrapper. Keep keys and their backing stable while stored, and restart cursors after any mutation. Floating-point keys need an explicit equality and hashing policy.
Complete map workloads can exceed the Cortex-M0 test profile of 32 KiB flash. The bounded example below checks the empty-map surface; it does not demonstrate that a populated map fits that profile.
Items
- equatable concept
- hashable concept
- cursor type
- entry type
- map type
- end_of_entries atom
- missing atom
- at function
- capacity function
- clear function
- contains function
- entries function
- get function
- insert function
- length function
- new function
- next_entry function
- release function
- remove function
- reserve function
Executable example
This complete program is maintained in the repository runtime tests. View source.
import core/map exercise: () -> (ok: bool) ! map.missing = ok = false mut value := map.new(key: u32, item: i32) return when map.length(value) <> 0 or map.capacity(value) <> 0 return when map.contains(value, u32(42)) mut refused: bool = false _ = map.at(value, u32(42)) else (problem) return when problem <> map.missing refused = true end return when not refused _ = map.get(value, u32(42)) else (problem) ok = problem == map.missing return end end exercise public main: () -> (code: i32) = code = 1 ok := exercise() else false if ok then code = 42 end if end main
equatable concept
public equatable: type = concept (key: type)
--- Compare keys under a stable equivalence relation.
eq: (left: key, right: key) -> (same: bool)
end equatableEquality evidence for keys. eq must define a consistent equivalence relation while the keys are stored.
hashable concept
public hashable: type = concept (key: type) is equatable
--- Return a stable hash; keys equal under eq must hash equally.
hash: (value: key) -> (result: u64)
end hashableHash evidence composing equatable. Equal keys must have equal hashes; key equality and hashes must remain stable while stored. Hashes are not cryptographic.
A hashable conformance composes equatable, but [1340] still requires a concrete key type to declare both conformances explicitly.
cursor type
public cursor: type = struct
next_slot: usize
end cursorPosition in an insertion-order entry walk. Start with entries; do not mutate the map during a walk.
Enumeration deliberately exposes ordinary public value shapes, matching map's public-composition boundary above. A cursor is a manual live-bucket position, not an ownership or snapshot token: it has no map identity or generation check and is not transferable between maps. Any mutation, including insert, remove, rehash, clear and release, invalidates an active walk; callers must discard its cursor and restart.
entry type
public entry: type (key: type, item: type) = struct
key: key
item: item
end entryA copied key/value pair returned by next_entry. References inside either value still depend on their original backing.
map type
public map: type (key: type is hashable, item: type) = struct
buckets: mem.storage(bucket)
keys: mem.storage(key)
values: mem.storage(item)
count: usize
tombstones: usize
first_used: usize
last_used: usize
end mapInsertion-ordered hash map with public composition of slot metadata and dense key/value prefixes. Keep those fields consistent by using the module operations. Providers are supplied per operation.
This is deliberately a public composition, not an encapsulated object. Callers can pass each storage to mem's public operations, can reach the initialized K/V prefixes (including removed dense entries), and can copy inferred whole bucket values despite bucket's private identity. They must preserve equal capacities, a fully initialized bucket array, paired K/V prefixes, one valid used/dead bucket per dense position, exact count/tombstone totals, and a linked walk of exactly the used buckets when composing below the map operations.
end_of_entries atom
public end_of_entries: atomThe insertion-order cursor has reached the end of the map.
missing atom
public missing: atomNo live entry has the requested key.
at function
public at: (key: type is hashable, item: type,
inout value: map(key, item), wanted: key)
-> (slot: ptr mut item from value) ! missingLend a writable pointer to an existing value. Reports missing if absent. End the pointer before mutating the map's structure or releasing backing.
A writable slot for the present key's item, for in-place update. While the result lives the map binding may not be passed inout or sink [0800]; let it end before the next insert, remove or release.
capacity function
public capacity: (key: type is hashable, item: type,
value: map(key, item)) -> (count: usize)Return the current hash-slot capacity. Hash-slot occupancy can require rebuilding before every slot is used.
clear function
public clear: (key: type is hashable, item: type,
inout value: map(key, item)) -> noneDiscard all entries and tombstones while retaining allocations. End existing pointers and walks first; referenced resources remain the caller's responsibility.
Forget every entry but keep the bucket capacity. Every bucket is rewritten free and both dense prefixes are emptied; values in them are discarded, and resources they refer to remain the caller's.
contains function
public contains: (key: type is hashable, item: type,
value: map(key, item), wanted: key) -> (yes: bool)Return whether a live entry has the requested key, without allocating.
entries function
public entries: () -> (position: cursor)Create a cursor positioned before the first entry. The walk follows current insertion order.
get function
public get: (key: type is hashable, item: type,
value: map(key, item), wanted: key)
-> (result: item from value) ! missingCopy the value associated with a key. Reports missing if absent; references inside the copy retain their origin.
insert function
public insert: (key: type is hashable, item: type,
provider: type is mem.allocator,
inout value: map(key, item), inout state: provider,
escaping added_key: key, escaping added_value: item)
-> none ! mem.out_of_memoryInsert a new key/value pair or replace the value of an equal key. New keys append in insertion order; replacement keeps its position. Allocation failure preserves the previous map. Growth can invalidate views.
length function
public length: (key: type is hashable, item: type,
value: map(key, item)) -> (count: usize)Return the number of live key/value entries.
new function
public new: (key: type is hashable, item: type)
-> (result: map(key, item))Create an empty map without allocating backing.
next_entry function
public next_entry: (key: type is hashable, item: type,
value: map(key, item), inout position: cursor)
-> (result: entry(key, item) from value) ! end_of_entriesCopy the next live key/value pair and advance the cursor. Reports end_of_entries at the end; keep the map unchanged during the walk.
Each call follows one live link. Across an unmodified walk, every live entry is returned once in insertion order and the walk costs O(count), including the exhausted call. The result retains from value because K or V may hold references into the map's initialized storage.
release function
public release: (key: type is hashable, item: type,
provider: type is mem.allocator,
inout value: map(key, item),
inout state: provider) -> noneDiscard all entries, free the map's backing through its original provider and reset it. Nested resources referred to by keys or values are not freed automatically.
remove function
public remove: (key: type is hashable, item: type,
inout value: map(key, item), wanted: key)
-> none ! missingRemove a key/value entry without returning it. Reports missing if absent; preserves the relative order of remaining entries. End existing value pointers and cursors before mutation.
reserve function
public reserve: (key: type is hashable, item: type,
provider: type is mem.allocator,
inout value: map(key, item), inout state: provider,
want: usize) -> none ! mem.out_of_memoryEnsure capacity for at least want entries without adding any. Allocates replacement key, value and hash-slot storage before committing it. Any allocation failure frees the partial replacement and preserves all original entries and capacities. Success can invalidate pointers and cursors.
Room for want entries without a growth allocation: the capacity is doubled from eight until want sits below the crowding threshold, and the map is rebuilt once at that size. A map already that large is left alone, including its tombstones.