set

#include <set.h>

The CTL set, analogous to the STL std::set, is a container specializing in unique key value pairs with O(log2N) lookup, insertion, and deletion times. The set template is implemented as a red-black tree, and pointers to elements within a set remain valid as new elements are inserted and erased into and from a set. The set template also includes conventional mathematical functions, such as intersection and difference functions.

Example 1: Storing and Summing a Sorted Set of Random Integers

A set stores its elements in order by relation of a key_compare function. The key_compare function must return -1 upon comparison if less, 1 if greater, and 0 if equal. Similar to that of the vec example, a set is naturally always sorted, and therefor has no sort function.

#include <stdio.h>

#define P
#define T int
#include <set.h>

int key_compare(int* a, int* b)
{
    return (*b == *a) ? 0 : (*b < *a) ? -1 : 1;
}

int main(void)
{
    set_int a = set_int_init(key_compare);
    for(int i = 0; i < 32; i++)
        set_int_insert(&a, rand() % 1024);
    int sum = 0;
    int index = 0;
    foreach(set_int, &a, it)
    {
        printf("%2d: %4d\n", index, *it.ref);
        sum += *it.ref;
        index += 1;
    )   
    printf("%d\n", sum);
    set_int_free(&a);
}

gcc -I ctl main.c

Example 2: Creating a Database of Images

Databases, often built upon key value pairs, may utilize a unique identifier such as a UUID, or simply even a name, to quickly retrieve or modify data (for instance, images or videos):

#include <stdio.h>
#include <stdint.h>

#include <str.h>

#define P
#define T uint8_t
#include <vec.h>

typedef struct
{
    str name;
    vec_uint8_t data;
}
image;

void
image_free(image* im)
{
    str_free(&im->name);
    vec_uint8_t_free(&im->data);
}

image
image_copy(image* im)
{
    return (image) {
        str_copy(&im->name),
        vec_uint8_t_copy(&im->data),
    };
}

#define T image
#include <set.h>

int
key_compare(image* a, image* b)
{
    return str_key_compare(&a->name, &b->name);
}

int main(void)
{
    set_image a = set_image_init(key_compare);
    for(int i = 0; i < 32; i++)
    {
        size_t bytes = 8;
        char name[bytes];
        for(size_t i = 0; i < bytes - 1; i++)
            name[i] = 'a' + rand() % ('z' - 'a');
        name[bytes - 1] = '\0';
        image im = {
            str_init(name),
            vec_uint8_t_init(),
        };
        vec_uint8_t_resize(&im.data, 512, 0);
        set_image_insert(&a, im);
    }
    set_image b = set_image_copy(&a);
    set_image_free(&a);
    set_image_free(&b);
}

gcc -I ctl main.c

A copy of a, named b, is copied, and then both a and b freed to exemplify no double-free errors are raised at runtime. Finding items within a set (the copy, set b, for instance) requires only specifying the comparison value:

image im;
im.name = str_init("abc");
image* found = &set_image_find(&b, im)->key;
str_free(&im.name);

The image im must be manually freed as it is not consumed by the container. As an aside, sets of pointer types (eg. char*) are possible, given the pointer type is a typedef:

#include <stdio.h>
#include <string.h>

typedef char* charp;
#define P
#define T charp
#include <set.h>

int
key_compare(charp* a, charp* b)
{
    return strcmp(*a, *b);
}

int main(void)
{
    set_charp a = set_charp_init(key_compare);
    set_charp_insert(&a, "the");
    set_charp_insert(&a, "quick");
    set_charp_insert(&a, "brown");
    set_charp_insert(&a, "fox");
    set_charp_insert(&a, "jumps");
    set_charp_insert(&a, "over");
    set_charp_insert(&a, "the");
    set_charp_insert(&a, "lazy");
    set_charp_insert(&a, "dog");
    foreach(set_charp, &a, it)
        puts(*it.ref);
    set_charp_free(&a);
}

gcc -I ctl main.c

Once again, #define P states no additional cleanup is required per element when the charp set is freed.