Hash_Map

moduleextensionSource

Available on macOS, Linux, Windows, Wasm·since 0.23.0

#import "Extensions/Hash_Map";

An opt-in hash map that probes sixteen slots at a time.

Example↗

Map :: #import "Extensions/Hash_Map";

ages: Map.Map(string, int);
defer Map.deinit(*ages);

Map.insert(*ages, "ada", 36);
age := Map.get(*ages, "ada");
for value, name: ages print("% is %\n", name, value);

Iteration order is whatever the layout gives, and changes whenever the map grows.

Module parameters#

SCALAR_GROUPS := false: Compare the sixteen control bytes of a group with the vector unit. Set it to true to use plain loops instead (wasm targets always do), which gives the same answers.

Procedures#

insertsince 0.23.0Source

(map: *Map, key: map.Key, value: map.Value) -> (previous: map.Value, replaced: bool)

Stores the value under the key. Returns the value it replaced (zero if there was none) and whether there was one.

Hash_Map :: #import "Extensions/Hash_Map";

map: Hash_Map.Map(string, int);
defer Hash_Map.deinit(*map);

_, replaced := Hash_Map.insert(*map, "a", 1);
assert(!replaced);
previous, replaced2 := Hash_Map.insert(*map, "a", 2);
assert(replaced2 && previous == 1);

↗

findsince 0.23.0Source

(map: *Map, key: map.Key) -> *map.Value

A pointer to the key's value, or null if it is missing. The pointer stays valid until the map is next rebuilt by an insert or entry.

Hash_Map :: #import "Extensions/Hash_Map";

map: Hash_Map.Map(string, int);
defer Hash_Map.deinit(*map);

Hash_Map.insert(*map, "hits", 1);
hits := Hash_Map.find(*map, "hits");
hits.* += 1;
assert(Hash_Map.get(*map, "hits") == 2);
assert(Hash_Map.find(*map, "misses") == null);

↗

getsince 0.23.0Source

(map: *Map, key: map.Key, default: map.Value = .{}) -> map.Value

A copy of the key's value, or default if it is missing.

Hash_Map :: #import "Extensions/Hash_Map";

map: Hash_Map.Map(string, int);
defer Hash_Map.deinit(*map);

Hash_Map.insert(*map, "a", 1);
assert(Hash_Map.get(*map, "a") == 1);
assert(Hash_Map.get(*map, "b", -1) == -1);

↗

entrysince 0.23.0Source

(map: *Map, key: map.Key) -> (value: *map.Value, added: bool)

A pointer to the key's value, adding a zero-initialized one if the key is missing. added says whether it was added. Handy for counting.

Hash_Map :: #import "Extensions/Hash_Map";

counts: Hash_Map.Map(string, int);
defer Hash_Map.deinit(*counts);

for word: string.["a", "b", "a"] {
    count := Hash_Map.entry(*counts, word);
    count.* += 1;
}
assert(Hash_Map.get(*counts, "a") == 2);

↗

deletesince 0.23.0Source

(map: *Map, key: map.Key) -> (value: map.Value, removed: bool)

Removes the key. Returns its value (zero if it was missing) and whether it was there.

Hash_Map :: #import "Extensions/Hash_Map";

map: Hash_Map.Map(string, int);
defer Hash_Map.deinit(*map);

Hash_Map.insert(*map, "a", 1);
value, removed := Hash_Map.delete(*map, "a");
assert(removed && value == 1 && map.count == 0);

↗

containssince 0.23.0Source

(map: *Map, key: map.Key) -> bool

Whether the key is in the map.

Hash_Map :: #import "Extensions/Hash_Map";

map: Hash_Map.Map(string, int);
defer Hash_Map.deinit(*map);

Hash_Map.insert(*map, "a", 1);
assert(Hash_Map.contains(*map, "a") && !Hash_Map.contains(*map, "b"));

↗

reservesince 0.23.0Source

(map: *Map, expected_count: s64)

Room for expected_count entries in total, so inserting up to that many never rebuilds the map.

Hash_Map :: #import "Extensions/Hash_Map";

map: Hash_Map.Map(int, int);
defer Hash_Map.deinit(*map);

Hash_Map.reserve(*map, 1000);
capacity := map.capacity;
for 0..999 Hash_Map.insert(*map, it, it);
assert(map.capacity == capacity);

↗

clearsince 0.23.0Source

(map: *Map)

Removes every entry and keeps the memory.

Hash_Map :: #import "Extensions/Hash_Map";

map: Hash_Map.Map(int, int);
defer Hash_Map.deinit(*map);

Hash_Map.insert(*map, 1, 1);
Hash_Map.clear(*map);
assert(map.count == 0 && map.capacity > 0);

↗

deinitsince 0.23.0Source

(map: *Map)

Removes every entry and frees the memory. The map can be used again afterwards.

Hash_Map :: #import "Extensions/Hash_Map";

map: Hash_Map.Map(int, int);
Hash_Map.insert(*map, 1, 1);
Hash_Map.deinit(*map);
assert(map.count == 0 && map.capacity == 0);

↗

for_expansionsince 0.23.0Source

(map: *$T/Map, body: Code, flags: For_Flags)

for value, key: map {...} visits every entry: it is the value (a pointer to it under for *), it_index the key. remove it takes the current entry out. Anything else that changes the map inside the loop, adding included, invalidates the loop.

Hash_Map :: #import "Extensions/Hash_Map";

map: Hash_Map.Map(int, int);
defer Hash_Map.deinit(*map);

for 1..5 Hash_Map.insert(*map, it, it * 10);
for value, key: map if key % 2 == 0 remove value;
total := 0;
for value: map total += value;
assert(total == 90);

↗

Types#

Mapstructsince 0.23.0Source

:: struct

A hash map from Key to Value. Strings and anything Hash.get_hash handles work as keys out of the box; pass hash and equal for other types. The zero value is an empty map that allocates on the first insert; free it with deinit.

count: int: Entries in the map. Read only.
capacity: int: Slots in the map: zero before the first insert, then a power of two, at least GROUP_SIZE. Read only.
growth_left: int: Empty slots that may still be filled before the map has to be rebuilt.
allocator: Allocator
control: *u8: One byte per slot, followed in the same allocation by the entries.
entries: *Entry

Hash_Map :: #import "Extensions/Hash_Map";

map: Hash_Map.Map(string, int);
defer Hash_Map.deinit(*map);

Hash_Map.insert(*map, "one", 1);
assert(map.count == 1 && Hash_Map.get(*map, "one") == 1);

↗

Constants#

GROUP_SIZEsince 0.23.0Source

:: 16