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

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.

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.

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