107 Containers and algorithms

107.1 The life cycle of the four containers#

First we see the four on one screen. How making, putting in, traversing and giving back differ between them is all in this example.

/* The life of four containers — made, filled, walked and given back.
   array, list, ring and map compared on one screen. */
#include <proven.h>

/* an intrusive list: the node lives inside the data */
typedef struct {
    int                id;
    proven_list_node_t link;      /* <- this one slot is the hook it hangs on the list by */
} task_t;

int main(void)
{
    proven_allocator_t alloc = proven_heap_allocator();

    /* ── (1) a growing array ─────────────────────────────────────── */
    proven_result_array_t ar = PROVEN_ARRAY_INIT(alloc, int, 2);
    if (!proven_is_ok(ar.err)) return 1;
    proven_array_t arr = ar.value;

    for (int i = 1; i <= 5; i++)
        (void)PROVEN_ARRAY_PUSH(&arr, int, i * i);

    proven_println("array  len={} cap={} elem_size={}",
                   PROVEN_ARG(arr.len), PROVEN_ARG(arr.cap), PROVEN_ARG(arr.elem_size));

    /* walked by index — no pointer is carried around */
    proven_print("       content:");
    for (proven_size_t i = 0; i < arr.len; i++)
        proven_print(" {}", PROVEN_ARG(*PROVEN_ARRAY_GET(&arr, int, i)));
    proven_println("");

    int last = 0;
    (void)PROVEN_ARRAY_POP(&arr, int, &last);
    proven_println("       pop -> {} (len {})", PROVEN_ARG(last), PROVEN_ARG(arr.len));
    PROVEN_ARRAY_DESTROY(&arr);

    /* ── (2) an intrusive list — not one allocation ──────────────── */
    task_t     items[3] = { { .id = 10 }, { .id = 20 }, { .id = 30 } };
    proven_list_t list;
    proven_list_init(&list);
    for (int i = 0; i < 3; i++)
        proven_list_push_back(&list, &items[i].link);

    proven_list_node_t *node, *tmp;
    proven_print("list   from the front:");
    PROVEN_LIST_FOR_EACH(node, &list) {
        task_t *t = PROVEN_LIST_ENTRY(node, task_t, link);
        proven_print(" {}", PROVEN_ARG(t->id));
    }
    proven_println("  (the node is inside the data, so no allocation is needed)");

    /* to unhook while walking, the SAFE version is used */
    PROVEN_LIST_FOR_EACH_SAFE(node, tmp, &list) {
        task_t *t = PROVEN_LIST_ENTRY(node, task_t, link);
        if (t->id == 20) proven_list_remove(node);
    }
    proven_print("       after removing 20:");
    PROVEN_LIST_FOR_EACH(node, &list) {
        proven_print(" {}", PROVEN_ARG(PROVEN_LIST_ENTRY(node, task_t, link)->id));
    }
    proven_println("");

    /* ── (3) a ring buffer — fixed size, the past is dropped ─────── */
    proven_result_ring_t rr = PROVEN_RING_INIT(alloc, int, 4);
    if (proven_is_ok(rr.err)) {
        proven_ring_t ring = rr.value;
        for (int i = 1; i <= 4; i++) (void)proven_ring_push(&ring, &i);

        int five = 5;
        proven_err_t full = proven_ring_push(&ring, &five);
        proven_println("ring   push when full -> err={} (it reports rather than overwrites)",
                       PROVEN_ARG((int)full));

        int v = 0;
        (void)proven_ring_pop(&ring, &v);
        proven_println("       pop -> {} (the one put in first)", PROVEN_ARG(v));
        proven_ring_destroy(&ring);
    }

    /* ── (4) a hash map — the key is owned or borrowed, as chosen ── */
    /* the map copies and owns the key (U8_OWNED) — a borrowing version exists too */
    proven_result_map_t mr = PROVEN_MAP_INIT_U8_OWNED(alloc, int, 8);
    if (proven_is_ok(mr.err)) {
        proven_map_t map = mr.value;
        int a = 1, b = 2;
        (void)proven_map_set_u8_owned(&map, PROVEN_LIT("alpha"), &a);
        (void)proven_map_set_u8_owned(&map, PROVEN_LIT("beta"), &b);

        const int *found = proven_map_get(&map,
                        (proven_map_key_t){ .str = PROVEN_LIT("beta") });
        proven_println("map    get(\"beta\") -> {}",
                       PROVEN_ARG(found ? *found : -1));
        proven_println("       get(\"absent\") -> {} (null when there is none)",
                       PROVEN_ARG((bool)(proven_map_get(&map,
                            (proven_map_key_t){ .str = PROVEN_LIT("absent") }) == nullptr)));
        proven_map_destroy(&map);
    }
    return 0;
}

array  len=5 cap=8 elem_size=4
       content: 1 4 9 16 25
       pop -> 25 (len 4)
list   from the front: 10 20 30  (the node is inside the data, so no allocation is needed)
       after removing 20: 10 30
ring   push when full -> err=2 (it reports rather than overwrites)
       pop -> 1 (the one put in first)
map    get("beta") -> 2
       get("absent") -> true (null when there is none)

That only the list has no allocation stands out — because the node lives inside the data. So a list is the only container that cannot fail for lack of memory, and it is especially loved in embedded work (chapter 109).

107.2 The growing array#

proven_array_t is a byte buffer that knows the element size and alignment. Open it up and why the type is filled in by macros becomes clear.

typedef struct {
    proven_allocator_t alloc;       /* it remembers the allocator given at creation */
    proven_byte_t     *data;        /* the byte buffer */
    proven_size_t      len;         /* the number of elements held now */
    proven_size_t      cap;         /* the number of elements it can hold */
    proven_size_t      elem_size;   /* the size of one element */
    proven_size_t      align;       /* the element's alignment requirement */
} proven_array_t;

That the array remembers the allocator differs from strings. A string takes an allocator per operation (chapter 105), while an array takes one at creation and keeps it inside — requiring an allocator on every push that may grow the array would make the code noisy. So the allocator is not given again at destruction either (PROVEN_ARRAY_DESTROY(&arr)).

C having no generics, the type is filled in by macros.

#include <proven.h>
#include <stdio.h>

int main(void)
{
    proven_allocator_t alloc = proven_heap_allocator();

    proven_result_array_t made = PROVEN_ARRAY_INIT(alloc, int, 4);
    if (!proven_is_ok(made.err)) {
        printf("array creation failed\n");
        return 1;
    }
    proven_array_t arr = made.value;

    for (int i = 1; i <= 6; i += 1) {          /* past a capacity of 4 it grows by itself */
        if (!proven_is_ok(PROVEN_ARRAY_PUSH(&arr, int, i * i))) {
            printf("push failed\n");
            PROVEN_ARRAY_DESTROY(&arr);
            return 1;
        }
    }

    printf("count: %zu\n", arr.len);
    for (size_t i = 0; i < arr.len; i += 1) {
        printf("%d ", *PROVEN_ARRAY_GET(&arr, int, i));
    }
    printf("\n");

    PROVEN_ARRAY_DESTROY(&arr);
    return 0;
}

count: 6
1 4 9 16 25 36 

PROVEN_ARRAY_INIT(alloc, int, 4) means “an array to hold ints, initial capacity 4”, and PROVEN_ARRAY_PUSH writes the type again to check at compile time that it matches. At the fifth element, which exceeded the capacity of 4, the array grew by itself — and that growth happens through the allocator (exactly chapter 104′s rule; the array remembers the allocator it was given at creation).

Besides appending at the end, there are functions that edit the middle. proven_array_insert puts an element in at one position, and proven_array_remove_at takes one out and pulls the rest forward. proven_array_swap_remove fills the hole with the last element — the order is disturbed, but only one element moves. proven_array_extend appends several at once, and proven_array_truncate and proven_array_clear shorten the array. When one of them fails, the array is unchanged (failure atomicity, chapter 102).

int *first = PROVEN_ARRAY_GET_MUT(&arr, int, 0);
(void)PROVEN_ARRAY_PUSH(&arr, int, 42);   /* the buffer may move here */
*first = 7;                               /* writes at the old address — use after free */

107.3 The intrusive list — linking without allocation#

proven_list_t is an intrusive linked list — the node does not hold the data; rather a link field is planted inside the data struct. It amounts to putting one proven_list_node_t link; slot inside a struct made in chapter 47.

typedef struct proven_list_node_t {
    struct proven_list_node_t *next;
    struct proven_list_node_t *prev;
} proven_list_node_t;

typedef struct {
    proven_list_node_t head;      /* a sentinel pointing at itself */
} proven_list_t;

That head is a sentinel is this implementation’s knack. In an empty list head.next and head.prev point at head itself, and so not one “is it null” check appears in the insertion and deletion code — a pattern the Linux kernel long used.

What is good about it? There is nothing to allocate separately to put something in the list — because the node is the data. A list can be used even in an environment with no heap (chapter 109), and hanging the same object on two lists at once is a matter of keeping two link fields. The price is that the data struct must know about the list.

Getting back from a node to the data that holds it is the problem, and one macro solves it.

task_t *t = PROVEN_LIST_ENTRY(node, task_t, link);

It is the macro that works the struct’s starting address back from the address of the link member — the offsetof seen in chapter 47 used here in the flesh. This one line returning from node to data is nearly the whole of the intrusive list.

There are two traversal macros.

The star matters. Remove a node during traversal and its next becomes meaningless, so the loop loses its way. The _SAFE variant loops with the next node already in hand, so removing the present node is safe. It is why the example used it when detaching item

It is worth knowing too that both macros require the iteration variables to be declared in advance (proven_list_node_t *node, *tmp;). The macro does not put a declaration in the for’s initialiser — a kernel practice carried on from the C89 days.

107.4 The ring buffer — a stream of fixed size#

proven_ring_t is a fixed-size circular buffer. It is used where a producer and a consumer come and go, for the most recent N of a log, and for streams such as audio and sensor samples where what has passed may be thrown away. The size being fixed, what to do when it is full is part of the contract — and here too the default is to report rather than quietly overwrite (the err=2 in tour.c’s output confirms it).

There are only push and pop, and both copy the element. Putting in gives an address, and taking out gives the address of the place to receive it.

int v = 42;
proven_err_t e = proven_ring_push(&ring, &v);     /* copies the value in */
int out;
e = proven_ring_pop(&ring, &out);                 /* copies the value out */

Thanks to this design no pointer into an element inside the ring leaks outward — holding a pointer in a circular buffer and having that place overwritten is a classic accident, and it was blocked by the interface.

107.5 The hash map, and data structures under attack#

proven_map_t is an open-addressing hash map. Keys are integers or byte sequences, and string keys have two modes — a borrowed key (the caller keeps the bytes alive) and an owned key (the map copies and holds it). Chapter 104′s owning-borrowing distinction appears here as it is too.

The kind of key is settled at creation.

The key is passed as one union — .id for an integer, .str for a string.

proven_map_key_t k = { .str = PROVEN_LIT("beta") };
const int *v = proven_map_get(&map, k);      /* null if absent */

Lookup answers with null. The reason it returns a pointer rather than a bundle is that “absent” is not a failure but a normal answer (distinct from chapter 102′s error branches). And that pointer points inside the map, so it becomes invalid the next time the map grows — the same rule as with arrays.

There are three functions for putting in. proven_map_set (general), proven_map_set_u8_owned (copying a string key in), and proven_map_set_with_scratch (giving the temporary memory separately). The last is used when the temporary buffers of internal work such as rehashing are to be obtained from another allocator — a device for keeping dead memory from piling up when running a map on an arena.

What is inside can also be walked in full. proven_map_len gives the count, and a walk starts with proven_map_iter_init and calls proven_map_iter_next until PROVEN_ERR_EOF comes.

proven_map_iter_t it = proven_map_iter_init(&map);
proven_map_key_t key;
void *value;
while (proven_is_ok(proven_map_iter_next(&it, &key, &value))) {
    /* use key.str and *(int *)value */
}

The walk is in bucket order. That is not insertion order, and in a default map it differs from one run to the next — when order is needed, gather into an array and sort, as the example does. Removing an entry or changing a value during a walk is allowed. Adding a new key is not. Entries move when the map grows, and the next iter_next then returns PROVEN_ERR_INVALID_STATE — it stops instead of skipping or repeating entries.

#include <proven.h>
#include <stdio.h>

/* Words counted, sorted and printed — a map, an array and a sort at once */
typedef struct { proven_u8str_view_t word; int count; } entry_t;

/* a comparator must be a total order: ties are broken consistently too (avoiding chapter 100's counterexample) */
static int by_count_desc(const void *a, const void *b)
{
    const entry_t *x = a, *y = b;
    if (x->count != y->count) return (x->count < y->count) - (x->count > y->count);

    proven_size_t n = x->word.size < y->word.size ? x->word.size : y->word.size;
    int c = proven_memcmp(x->word.ptr, y->word.ptr, n);
    if (c != 0) return c;
    return (x->word.size > y->word.size) - (x->word.size < y->word.size);
}

int main(void)
{
    proven_allocator_t alloc = proven_heap_allocator();
    const char *text = "the quick fox the lazy dog the fox";

    /* a map with string keys: by default a keyed hash that stands up to HashDoS */
    proven_result_map_t made_map =
        proven_map_create(alloc, 16, PROVEN_KEY_TYPE_U8_OWNED, sizeof(int), alignof(int));
    if (!proven_is_ok(made_map.err)) return 1;
    proven_map_t counts = made_map.value;

    proven_u8str_view_t all = proven_u8str_view_from_cstr(text);
    proven_u8str_view_t space = proven_u8str_view_from_cstr(" ");
    proven_size_t start = 0;

    for (;;) {
        proven_size_t hit = proven_u8str_view_find(all, start, space);
        proven_size_t end = (hit == PROVEN_INDEX_NOT_FOUND) ? all.size : hit;
        proven_u8str_view_t w = proven_u8str_view_slice(all, start, end - start);

        const int *seen = proven_map_get(&counts, (proven_map_key_t){ .str = w });
        int next = seen ? *seen + 1 : 1;
        if (!proven_is_ok(proven_map_set(&counts, (proven_map_key_t){ .str = w }, &next)))
            break;

        if (hit == PROVEN_INDEX_NOT_FOUND) break;
        start = hit + 1;
    }
    printf("distinct words: %zu\n", counts.len);

    /* the counts gathered into an array and sorted */
    proven_result_array_t made_arr = PROVEN_ARRAY_INIT(alloc, entry_t, 8);
    if (!proven_is_ok(made_arr.err)) return 1;
    proven_array_t list = made_arr.value;

    const char *words[] = {"the", "quick", "fox", "lazy", "dog"};
    for (size_t i = 0; i < sizeof words / sizeof words[0]; i++) {
        proven_u8str_view_t w = proven_u8str_view_from_cstr(words[i]);
        const int *c = proven_map_get(&counts, (proven_map_key_t){ .str = w });
        entry_t e = { .word = w, .count = c ? *c : 0 };
        if (!proven_is_ok(PROVEN_ARRAY_PUSH(&list, entry_t, e))) break;
    }

    proven_array_sort(&list, by_count_desc);   /* O(n log n) guaranteed even in the worst case */
    for (size_t i = 0; i < list.len; i++) {
        const entry_t *e = PROVEN_ARRAY_GET(&list, entry_t, i);
        printf("  %.*s = %d\n", (int)e->word.size, (const char *)e->word.ptr, e->count);
    }

    PROVEN_ARRAY_DESTROY(&list);
    proven_map_destroy(&counts);
    return 0;
}

distinct words: 5
  the = 3
  fox = 2
  dog = 1
  lazy = 1
  quick = 1

This one example brings several of this chapter’s tools together — it counts with a map, gathers into an array, sorts and prints. Chapter 105′s views were used to cut the words, so string copying happens only once, when the map owns the key.

107.6 Sorting with a worst-case guarantee#

The two problems seen in chapter 100 — the unchecked comparator, and the algorithm that collapses in the worst case — are treated together here.

proven_array_sort is introsort. It begins as a fast quicksort and, if the recursion becomes too deep, switches to heapsort. So the average is as fast as quicksort and $𝑂\left(𝑛log𝑛\right)$ is guaranteed even in the worst case — the complexity attack seen in chapter 100 does not work. To carry the header’s wording over as it is: “$𝑂\left(𝑛log𝑛\right)$ is not an average but a guarantee.”

On the comparator side the language cannot help, so the contract is stated in the documentation and in examples. The example’s by_count_desc is the model — descending by count, and ties broken by the word. It contrasts exactly with chapter 100′s counterexample (the comparator that sees only the first letter).

107.7 Bytes into text — hashes and encodings#

We also note the other tools that come with the containers: hashes, and the hex and Base64 encodings.

• Hashes by purpose — for the map’s internals (fast mixing), for integrity checking (CRC-32), for cryptographic use (SHA-256 — from v0.113.0 in the separate proven_crypto’s sha2.h, and not in this book’s snapshot), and the keyed hash seen above (SipHash). The library distinguishes them because the same word “hash” means entirely different demands — using SHA-256 where only speed is needed is waste, and using FNV-1a where adversarial input comes is dangerous.
• hex and Base64 — two standards for moving bytes into text. The principle here is the same. Wrong input (hex of odd length, wrong padding) is not guessed at and mended but refused with PROVEN_ERR_INVALID_ENCODING (that norm from chapter 105).

This is where the world of pure computation ends — it all runs even with no operating system. In the next chapter we go outside. Files, streams, time, random numbers — the places that touch the OS.