Table

A hash table from Key_Type to Value_Type: open addressing with linear probing, in one array of entries.

A zero-initialized Table is ready to use and owns no memory until the first add. The first growth takes the allocator from context.allocator and the table keeps it; free everything with deinit (or table_reset). The slot count is a power of two, at least 32, and doubles when the table is more than LOAD_FACTOR_PERCENT full counting removed entries, so adds are amortized constant time.

Keys are hashed with Hash.get_hash and compared with ==, which suits integers, enums, pointers and strings (by content). Pass given_hash_function and given_compare_function for anything else. Adding a key that is already present does not replace it: table_add keeps both entries, table_set replaces the value. The first is how to make a multi-map, see table_find_multiple.

count is the number of entries. Removed entries leave a marker that a later add reuses when REFILL_REMOVED is true (the default); with false markers stay until the table grows. Pointers to values and keys are stable only until the table grows, i.e. until the next add that fills it, expand, table_resize or table_ensure_space.

The order of iteration is by slot, which depends on the hashes, and is not the insertion order. Do not rely on it, nor on it staying the same after the table grows.

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);