(table: *Table, slots_to_allocate: s64 = 0)
Deprecated and not needed: a zero-initialized Table is ready to use. With slots_to_allocate greater than zero it
reserves that many slots (rounded up) through expand.
#import "Hash_Table";
Table(Key, Value) maps keys to values.
table: Table(string, int);
table_add(*table, "one", 1);
found, value := table_find(*table, "one");
assert(found && value == 1);Module parameters#
- COUNT_COLLISIONS := false
- Counts the collisions of each table, in
add_collisionsandfind_collisions.
Procedures#
(x: int) -> int
The smallest power of two that is at least x, and 1 for anything below that. Fails an assert when the result would not fit an int.
assert(next_power_of_two(33) == 64);
assert(next_power_of_two(64) == 64);
assert(next_power_of_two(0) == 1);(table: *Table, new_allocated := -1)
Rehashes every entry into a new array of new_allocated slots, and frees the old one.
(table: *Table, items: s64)
Makes sure items more entries can be added without the table growing again.
table: Table(int, int);
table_ensure_space(*table, 500);
slots := table.allocated;
for 0..499 table_add(*table, it, it);
assert(table.allocated == slots);
deinit(*table);(table: *Table, expected_count: s64)
Rehashes the table so that expected_count entries (or the current count, if larger) fit within the load factor.
table: Table(int, int);
table_resize(*table, 1000);
slots := table.allocated;
for 0..999 table_add(*table, it, it);
assert(table.allocated == slots && table.count == 1000); // no growth in between
deinit(*table);(table: *Table, key: table.Key_Type, value: table.Value_Type) -> *table.Value_Type
Adds an entry, even when key is already present, and returns a pointer to the stored value.
table: Table(int, string);
slot := table_add(*table, 1, "one");
slot.* = "uno";
found, value := table_find(*table, 1);
assert(found && value == "uno");
deinit(*table);(table: *Table, key: table.Key_Type, value: table.Value_Type) -> *table.Value_Type
Sets the value of key, replacing the first entry with an equal key, or adding one if there is none. Returns a pointer to the stored value.
table: Table(string, int);
table_set(*table, "hits", 1);
table_set(*table, "hits", 2);
found, value := table_find(*table, "hits");
assert(found && value == 2 && table.count == 1);
deinit(*table);(table: *Table, key: table.Key_Type) -> *table.Value_Type
A pointer to the value stored for key, or null when there is none, so the value can be changed in place.
counts: Table(string, int);
table_add(*counts, "a", 1);
pointer := table_find_pointer(*counts, "a");
pointer.* += 1;
assert(table_find_pointer(*counts, "a").* == 2);
assert(table_find_pointer(*counts, "b") == null);
deinit(*counts);(table: *Table, key: table.Key_Type) -> bool
table: Table(int, string);
table_add(*table, 7, "seven");
assert(table_contains(*table, 7) && !table_contains(*table, 8));(table: *Table, key: table.Key_Type) -> (success: bool, table.Value_Type)
Looks up key; returns whether it was found and a copy of the value (the default value of the type when it was not).
table: Table(int, float);
table_add(*table, 3, 1.5);
found, value := table_find(*table, 3);
assert(found && value == 1.5);
found, value = table_find(*table, 4);
assert(!found && value == 0);
deinit(*table);(table: *Table, key: table.Key_Type) -> [] table.Value_Type
Every value stored under key, as a view into temporary storage (talloc), or an empty view when there are none.
table: Table(int, string);
table_add(*table, 1, "a");
table_add(*table, 1, "b");
table_add(*table, 2, "c");
assert(table_find_multiple(*table, 1).count == 2);
assert(table_find_multiple(*table, 9).count == 0);
deinit(*table);(table: *Table, key: table.Key_Type) -> (success: bool, value: table.Value_Type)
Removes one entry with this key; returns whether there was one and its value.
table: Table(int, string);
table_add(*table, 5, "five");
removed, value := table_remove(*table, 5);
assert(removed && value == "five" && table.count == 0);
removed, value = table_remove(*table, 5);
assert(!removed);
deinit(*table);(table: *Table, key: table.Key_Type) -> num_removed: s64
Removes every entry with this key and returns how many there were.
(table: *Table, key: table.Key_Type) -> (entry: *table.Value_Type, newly_added: bool)
Finds the value for key, adding a zero-initialized one if there is none. Returns a pointer to it and whether it was just added.
counts: Table(string, int);
for word: string.["a", "b", "a"] {
count, added := find_or_add(*counts, word);
count.* += 1;
}
assert(table_find_pointer(*counts, "a").* == 2 && counts.count == 2);
deinit(*counts);(table: *Table)
Removes every entry but keeps the allocated slots, so refilling the table up to its old size allocates nothing.
table: Table(int, int);
table_add(*table, 1, 1);
slots := table.allocated;
table_reset_keeping_memory(*table);
assert(table.count == 0 && table.allocated == slots);
deinit(*table);(table: *Table)
Removes every entry and frees the slot array through the table's allocator. The table is usable again afterwards and allocates from scratch.
table: Table(int, int);
table_add(*table, 1, 1);
table_reset(*table);
assert(table.count == 0 && table.allocated == 0);(table: *Table)
Frees the table's memory, as table_reset does. Call it when the table is no longer needed.
(table: *$T/Table, body: Code, flags: For_Flags)
Lets a table be used in a for loop: it is the value and it_index the key.
(code: Code)
Low-level macro that visits the slots a lookup of key would probe, in order, up to the first never-used slot.
table: Table(int, string);
table_add(*table, 7, "seven");
key := 7;
matches := 0;
Walk_Table(#code {
if table_while_loop == hash && table.entries[index].key == key matches += 1;
});
assert(matches == 1);
deinit(*table);Types#
:: struct
A hash table from Key_Type to Value_Type: open addressing with linear probing, in one array of entries.
- count: int
- allocated: int
- slots_filled: int
- allocator: Allocator
- entries: [] Entry
table: Table(string, int);
table_add(*table, "one", 1);
table_set(*table, "two", 2);
table_set(*table, "two", 22); // replaces
found, value := table_find(*table, "two");
assert(found && value == 22 && table.count == 2);
total := 0;
for number, name: table total += number; // `it` is the value, `it_index` the key
assert(total == 23);
deinit(*table);Constants#
:: 0
:: 1
:: 2