92 Containers and algorithms

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

92.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 90), while an array takes one at creation and keeps it inside — making push pass an allocator every time it grows 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 89′s rule; the array remembers the allocator it was given at creation).

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 */

92.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 46.

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 in order 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 94), 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 the other way 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 46 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 edition turns 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.

92.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 example’s err=2 is that confirmation).

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.

92.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 89′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 87′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.

#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 53'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 contains all of this chapter’s tools — it counts with a map, gathers into an array, sorts and prints. Chapter 90′s views were used to cut the words, so string copying happens only once, when the map owns the key.

92.6 Sorting with a worst-case guarantee

The two problems seen in chapter 85 — 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 85 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 85′s counterexample (the comparator that sees only the first letter).

92.7 Bytes into letters — hashes and encodings

We note the remaining tools in the same box too.

• Hashes by purpose — for the map’s internals (fast mixing), for integrity checking (CRC-32), for cryptographic use (SHA-256), 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 90).

That is as far as the world of pure computation — 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.