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
anf 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 :: , allocator : *Allocator: )
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