ust

#include <ust.h>

The CTL ust, analogous to the std::unordered_set, is a container specializing in fast O(1) ideal time key-value lookup, erase, and insert operations. The ust template is implemented as a contiguous resizable array of pointers to forward linked list nodes. Pointers to elements within an ust remain valid as new elements are inserted and deleted to and from an ust.

An ust may be used in place of a set when a performance gain at the cost of memory consumption is required.

Example: Hashing Strings

#include <stdio.h>
#include <str.h>

#define T str
#include <ust.h>

size_t
str_hash(str* s)
{
    size_t hash = 5381;
    int c;
    char* temp = s->value;
    while(c = *temp++)
        hash = ((hash << 5) + hash) + c;
    return hash;
}

int
str_equal(str* a, str* b)
{
    return str_key_compare(a, b) == 0;
}

int
main(void)
{
    ust_str strs = ust_str_init(str_hash, str_equal);
    ust_str_insert(&strs, str_init("this"));
    ust_str_insert(&strs, str_init("is"));
    ust_str_insert(&strs, str_init("a"));
    ust_str_insert(&strs, str_init("test"));
    ust_str_insert(&strs, str_init("for"));
    ust_str_insert(&strs, str_init("unordered"));
    ust_str_insert(&strs, str_init("set"));
    ust_str_insert(&strs, str_init("for"));
    ust_str_insert(&strs, str_init("the"));
    ust_str_insert(&strs, str_init("C"));
    ust_str_insert(&strs, str_init("Standard"));
    ust_str_insert(&strs, str_init("Template"));
    ust_str_insert(&strs, str_init("Library"));
    ust_str_insert(&strs, str_init("(CTL)"));
    ust_str_insert(&strs, str_init("..."));
    foreach(ust_str, &strs, it) 
        puts(str_c_str(it.ref));
    for(size_t i = 0; i < strs.bucket_count; i++)
        printf("%2d : %2lu\n", i, ust_str_bucket_size(&strs, i));
    str what = str_init("(CTL)");
    str* found = &ust_str_find(&strs, what)->key;
    puts(str_c_str(found));
    ust_str_erase(&strs, what); // For fun.
    str_free(&what);
    ust_str_free(&strs);
}

gcc main.c -I ctl