dsa.map

Hash maps with optional lookup, indexed access, removal, and entry iteration.

All modules · Writing docstrings

Imports and exports

import core.{Opt, Hash, GetItem, SetItem}
import mem.{Ptr, Buf, heap}
import dsa.arr.{Arr}

Slot

enum Slot[K, V]

A backing-table slot. Applications normally work with Map instead.

Source, line 11

Slot.Empty

Empty

A slot that has never held an entry.

Source, line 13

Slot.Del

Del

A removed entry, retained as a probe-chain marker.

Source, line 15

Slot.Used

Used(K, V)

A live key and value.

Source, line 17

Map

kind Map[K, V]

A hash map from K to V. Keys need compatible hash and equality behavior. Iteration order follows the backing table and is not insertion order.

let counts = Map[Str, Int].new()
counts["kata"] = 2
print(counts.get("kata").unwrap())
print(counts.has("missing"))
print(counts.del("kata"))
print(counts.len())

2
false
true
0

Source, line 37

Map.slots

slots: Arr[Slot[K, V]]

Backing slots; direct mutation can violate the map’s invariants.

Source, line 39

Map.count

count: Int

Number of live entries.

Source, line 41

Map.cap

cap: Int

Number of allocated slots.

Source, line 43

Map[@K, @V]

impl Map[@K, @V]

Source, line 46

Map[@K, @V].new

func new(): Map[K, V]

Create an empty map with eight initial slots.

Source, line 48

Map[@K, @V]._idx

func _idx(self, key: K): Int

Implementation helper: compute the key’s first probe position.

Source, line 67

Map[@K, @V]._find

func _find(self, key: K): Tup[Int, Bool]

Implementation helper: return a slot index and whether the key was found.

Source, line 72

Map[@K, @V]._grow

func _grow(self)

Implementation helper: double the backing table and reinsert live entries.

Source, line 95

Map[@K, @V].get

func get(self, key: K): Opt[V]

Return the stored value, or Non when the key is absent.

Source, line 124

Map[@K, @V].set

func set(self, key: K, val: V)

Insert a key or replace its value. Grow the table when needed.

let labels = Map[Int, Str].new()
labels.set(1, "first")
labels.set(1, "updated")
print(labels[1])
print(labels.len())

updated
1

Source, line 149

Map[@K, @V].del

func del(self, key: K): Bool

Remove the key. Return true if an entry was removed, otherwise false.

Source, line 161

Map[@K, @V].has

func has(self, key: K): Bool

Whether the key has a live entry.

Source, line 172

Map[@K, @V].len

func len(self): Int

Return the number of live entries.

Source, line 178

Map[@K, @V] as GetItem[K, V]

impl Map[@K, @V] as GetItem[K, V]

Source, line 183

Map[@K, @V] as GetItem[K, V].get_item

func get_item(self, key: K): V

Implement map[key]. Stop with an error if the key is absent.

Source, line 185

Map[@K, @V] as SetItem[K, V]

impl Map[@K, @V] as SetItem[K, V]

Source, line 198

Map[@K, @V] as SetItem[K, V].set_item

func set_item(self, key: K, val: V)

Implement map[key] = val, inserting or replacing the entry.

Source, line 200

MapIter

kind MapIter[K, V]

An iterator over live (key, value) tuples in backing-table order.

Source, line 206

MapIter.slots

slots: Arr[Slot[K, V]]

Slots visited by the iterator.

Source, line 208

MapIter.cap

cap: Int

Number of slots to inspect.

Source, line 210

MapIter.idx

idx: Int

Next slot index.

Source, line 212

MapIter[@K, @V] as Iter[Tup[K, V]]

impl MapIter[@K, @V] as Iter[Tup[K, V]]

Source, line 215

MapIter[@K, @V] as Iter[Tup[K, V]].next

func next(self): Opt[Tup[K, V]]

Yield the next live entry, skipping empty and deleted slots.

Source, line 217

Map[@K, @V] as ToIter[Tup[K, V]]

impl Map[@K, @V] as ToIter[Tup[K, V]]

Source, line 230

Map[@K, @V] as ToIter[Tup[K, V]].to_iter

func to_iter(self): MapIter[K, V]

Create an entry iterator. Avoid mutating the map during iteration.

Source, line 232