Table
#import "std/table"
Table is generic data container aka hash table or hash map storing data entries as pairs of Key and Value. Table provides fast lookup on large amount of data.
Internally, the table is implemented as preallocated array of slots and dynamic array of keys
and values. The slots array holds information about mapping of each key-value pair (inserted into keys
and values arrays) and corresponding 32 bit hash value calculated from the key value.
The kays and values arrays are actually regular dynamic arrays holding inserted keys and values,
so it can be iterated as usual. The ordering of arrays is unstable after erase operation.
Performance of insert and lookup is getting worse when the table is starting to be full, to minimize
this problem, the table grows when the maximum load factor is reached (i.e. 70%). In such a situation
only the slots array is reallocated and whole table mapping is recalculated. This operation can be
expensive on large tables. However, keys and values arrays stays as it is and reallocates as regular
dynamic arrays (in case there is no preallocated space left).
Warning: Table data array ordering corresponds to the order of inserts until any element is erased from the table.
Warning: The key types are limited to numbers, strings and pointers (this may change in the future).
Example
#import "std/table"
main :: fn () s32 {
using std;
table: Table(string_view, s32);
defer tbl_terminate(&table);
// Insert some data into the table.
tbl_insert(&table, "Martin", 32);
tbl_insert(&table, "Lisa", 29);
tbl_insert(&table, "John", 40);
// Lookup data by key.
value, found :: tbl_lookup(&table, "Martin");
if found {
print("%\n", value);
}
// Iterate over the table
loop i := 0; i < table.len; i += 1 {
print("[%] %\n", table.keys[i], table.values[i]);
}
return 0;
}
std.Table
Table :: fn (TKey: type, TValue: type) type
Create a new Table type. The TKey must be a number, string or pointer type.
Table :: struct {
keys: [..]TKey;
values: [..]TValue;
len: s64;
}
File: table.bl
std.tbl_init
tbl_init :: fn (tbl: *?T, expected_size :: DEFAULT_ENTRIES_COUNT, allocator : *Allocator: null)
Initialize the tbl table. It's not necessary to call this method in case the table is
already zero-initialized. The expected_size can be specified as hint telling the table how many
elements we're going to store. Memory preallocation is performed using allocator.
File: table.bl
std.tbl_terminate
tbl_terminate :: fn (tbl: *?T)
Release all memory resources used by the table and set the tbl instance to the default state.
File: table.bl
std.tbl_typeof_key
tbl_typeof_key :: fn (TTable: type) type
Resolve type of key from table type in compile-time.
File: table.bl
std.tbl_typeof_value
tbl_typeof_value :: fn (TTable: type) type
Resolve type of value from table type in compile-time.
File: table.bl
std.tbl_insert
tbl_insert :: fn {
impl_insert_empty;
impl_insert;
}
Overloaded table insert function adding a new element (associated with the key) into the table.
The key value must be unique (not already existing in the table), this is checked in debug
mode and panic is invoked in case of collision.
Overloads:
fn (tbl: *?T, key: tbl_typeof_key(T), value: tbl_typeof_value(T)) *tbl_typeof_value(T) #inline
fn (tbl: *?T, key: tbl_typeof_key(T)) *tbl_typeof_value(T) #inline
Function returns pointer to the newly inserted value in the values array.
Note: When no value is explicitly inserted, returned pointer points to non-initialized memory.
File: table.bl
std.tbl_lookup_ptr
tbl_lookup_ptr :: fn (tbl: *?T, key: ) * #inline
Lookup entry associated with the key and returns pointer its value or null when no such key
was found.
File: table.bl
std.tbl_lookup
tbl_lookup :: fn (tbl: *?T, key: ) (value: , found: bool) #inline
Lookup entry associated with the key and returns its value and true or uninitialized value of type TValue
and false when no such key was found in the table.
File: table.bl
std.tbl_lookup_index
tbl_lookup_index :: fn (tbl: *?T, key: ) s32 #inline
Lookup entry associated with the key and returns index of found element (appliable to keys or values
arrays) or -1 when no such key was found.
File: table.bl
std.tbl_erase
tbl_erase :: fn (tbl: *?T, key: ) bool #inline
Erase an entry associated with key from the table and returns true in case the entry was
found.
Note: Ordering of the values and keys may change.
File: table.bl
std.tbl_contains
tbl_contains :: fn (tbl: *?T, key: ) bool #inline
Checks whether the table tbl contains the key.
File: table.bl
std.tbl_clear
tbl_clear :: fn (tbl: *?T) #inline
Clears the table, but keeps allocated memory.
File: table.bl