Chapter 4: Containers and Algorithms#

Part III — Data structures. Prerequisite: Part II (1, 2, 3). After this chapter you can pick the right container for a job, sort and search with a guaranteed bound, hash for the right reason, and turn bytes into text and back.

This chapter covers array.h, list.h, ring.h, map.h, algorithm.h, hash.h, and encode.h. Every container here takes an allocator, which is why Chapter 2 comes first.

Table of contents#

1. Dynamic array
2. Intrusive list
3. Ring buffer
4. Hash map
5. Algorithms
6. Hashing, by use case
7. Bytes to text: hex and Base64
8. Examples and misuse cases

1. Dynamic array#

The problem: the array you write by hand, every time#

A growable array is the data structure every C program eventually writes, and writes slightly differently:

int *items = malloc(cap * sizeof(int));
/* ... later ... */
if (n == cap) {
    cap *= 2;
    items = realloc(items, cap * sizeof(int));   /* wrong on two counts */
    items[n++] = x;
}

Two bugs in one line, and both are classics. cap * sizeof(int) can wrap for a large cap, producing a small allocation for a huge count — see Chapter 1 §4. And assigning realloc's result straight back to items leaks the old block when it returns NULL, because the original pointer is gone and the memory it named is still allocated.

Beyond the bugs, the hand-written version has to be rewritten for every element type, or made generic with void * and lose type checking.

What this library does instead#

proven_array_t is a growable vector that keeps the element size and alignment it was created with, so it works for any type without a template and without void * at the call site — the PROVEN_ARRAY_* macros take the type and do the casting where the compiler can still check it.

• Growth uses checked arithmetic, so the overflow above is PROVEN_ERR_OVERFLOW, not a small allocation.
• Growth is failure-atomic: if it cannot grow, your existing elements are untouched and still valid. Nothing is leaked and nothing is lost.
• It stores its allocator internally, unlike the string types — which is why PROVEN_ARRAY_DESTROY takes only the array.

proven_array_t owns contiguous element storage, so it is also what you hand to proven_array_sort and the searches in §5.

Wrong — holding a pointer across a push:

int *first = PROVEN_ARRAY_GET_MUT(&arr, int, 0);
(void)PROVEN_ARRAY_PUSH(&arr, int, 42);   /* may reallocate */
*first = 7;                               /* wrong: `first` may point at freed memory */

This is the one hazard the type cannot remove. Growth moves the storage, so any pointer or view into the array is invalidated by any operation that can grow it. Index instead of pointing, or re-fetch the pointer after the push.

Structures#

typedef struct {
    proven_allocator_t alloc;
    proven_byte_t *data;
    proven_size_t len;
    proven_size_t cap;
    proven_size_t elem_size;
    proven_size_t align;
} proven_array_t;

typedef struct {
    proven_err_t err;
    proven_array_t value;
} proven_result_array_t;

Fields:

• alloc: allocator used for growth and destruction.
• data: byte storage for elements.
• len: current element count.
• cap: capacity in elements.
• elem_size: size of each element.
• align: alignment of each element.

Functions#

Macros#

Example:

proven_result_array_t r = PROVEN_ARRAY_INIT(alloc, int, 4);
if (!proven_is_ok(r.err)) {
    return;
}
proven_array_t nums = r.value;

(void)PROVEN_ARRAY_PUSH(&nums, int, 10);
(void)PROVEN_ARRAY_PUSH(&nums, int, 20);

/* GET points into the array's own storage, and returns NULL out of range. */
const int *first = PROVEN_ARRAY_GET(&nums, int, 0);
if (first) {
    proven_println("first={}", PROVEN_ARG(*first));
}

/* The array stores its allocator, so destroy needs nothing but the array. */
PROVEN_ARRAY_DESTROY(&nums);

2. Intrusive list#

The problem: the list you were taught allocates a node per element#

struct node { struct node *next; void *data; };

That is the textbook linked list, and it has two costs the textbook does not mention. Every insertion allocates — a thousand items means a thousand allocations that exist only to hold pointers, each one able to fail and each one needing a matching free. And data is a void *, so the list has no idea what it holds: every read back out is a cast the compiler cannot check.

What an intrusive list does instead#

It turns the relationship inside out: you own the memory, and the link lives inside it.

typedef struct {
    int                 id;
    proven_list_node_t  link;   /* the list's hook, inside your struct */
} task_t;

Now inserting is writing two pointers. It allocates nothing, so it cannot fail — notice that proven_list_push_back returns void, which is unusual in this library and is the point. Removing is the same. The objects can live on the stack, in an array, in an arena, anywhere; the list only rearranges pointers that are already inside them.

Getting from a link back to your object is PROVEN_LIST_ENTRY(node, task_t, link), which subtracts the member's offset from the node's address. It is arithmetic the compiler checks the types of, not a cast you hope is right.

What you give up: an object can be in only as many lists as it has link members, and you decide that when you declare the struct. If an item needs to be in a queue and an index at the same time, it needs two links.

proven_list_t is an intrusive doubly-linked circular list — the head is a sentinel node, so insertion and removal never special-case the ends. It allocates no nodes.

Wrong — removing while walking with the plain iterator:

PROVEN_LIST_FOR_EACH(it, &queue) {
    if (should_drop(it)) proven_list_remove(it);   /* wrong: it->next is read after unlink */
}

proven_list_remove writes through the node's own pointers, so the loop then reads next from a node that has just been detached. PROVEN_LIST_FOR_EACH_SAFE takes a second variable and reads the next pointer before the body runs, which is exactly why it exists.

Worked example: a queue whose links live in the caller's structs#

Compiled and run by the test suite. It builds a queue of stack-allocated tasks, walks it, removes one from inside a safe walk, and inserts in the middle — with no allocator anywhere in the program.

/*
 * An INTRUSIVE list puts the links inside your struct instead of allocating a
 * node to hold your data.
 *
 * The list you were taught looks like this:
 *
 *     struct node { struct node *next; void *data; };
 *
 * Every insertion allocates a node, so a list of a thousand items costs a
 * thousand allocations that exist only to hold pointers, each one a chance to
 * fail and a thing to free. Worse, `data` is a void* - the list has no idea what
 * it holds, so every read is a cast the compiler cannot check.
 *
 * Intrusive lists invert it: YOU own the memory, and the link lives in it.
 * Inserting allocates nothing and cannot fail. Removing allocates nothing and
 * cannot fail. And because the link is a member of a known type, getting back
 * from a link to the object is arithmetic the compiler does for you, not a cast.
 *
 * The trade is that an object can only be in as many lists as it has link
 * members, and that is a decision you make when you declare the struct.
 */

/* The link is a member. This task can be in exactly one list at a time. */
typedef struct {
    int                 id;
    proven_list_node_t  link;
} task_t;

int main(void) {
    /* No allocator anywhere in this program: the tasks are on the stack, and the
     * list only ever rearranges pointers that live inside them. */
    task_t a = { .id = 1 };
    task_t b = { .id = 2 };
    task_t c = { .id = 3 };

    proven_list_t queue;
    proven_list_init(&queue);
    EXAMPLE_REQUIRE(proven_list_is_empty(&queue), "a freshly initialised list is empty");

    /* --- pushing cannot fail, because nothing is allocated ------------- */
    proven_list_push_back(&queue, &a.link);
    proven_list_push_back(&queue, &b.link);
    proven_list_push_back(&queue, &c.link);
    EXAMPLE_REQUIRE(!proven_list_is_empty(&queue), "three tasks are queued");

    /* --- walking: PROVEN_LIST_ENTRY gets the object back from the link -- */
    proven_list_node_t *it = NULL;
    int seen[3] = {0}, n = 0;
    PROVEN_LIST_FOR_EACH(it, &queue) {
        task_t *t = PROVEN_LIST_ENTRY(it, task_t, link);
        if (n < 3) seen[n++] = t->id;
    }
    EXAMPLE_REQUIRE(n == 3 && seen[0] == 1 && seen[1] == 2 && seen[2] == 3,
                    "the walk visits every task, in insertion order");

    /* --- removing while walking needs the SAFE form -------------------- */
    /* proven_list_remove writes through the node's own next/prev pointers, so a
     * plain FOR_EACH would read `it->next` from a node that has just been
     * unlinked. The _SAFE form reads the next pointer BEFORE the body runs. */
    proven_list_node_t *safe = NULL;
    PROVEN_LIST_FOR_EACH_SAFE(it, safe, &queue) {
        task_t *t = PROVEN_LIST_ENTRY(it, task_t, link);
        if (t->id == 2) proven_list_remove(it);
    }

    n = 0;
    PROVEN_LIST_FOR_EACH(it, &queue) {
        task_t *t = PROVEN_LIST_ENTRY(it, task_t, link);
        if (n < 3) seen[n++] = t->id;
    }
    EXAMPLE_REQUIRE(n == 2 && seen[0] == 1 && seen[1] == 3, "task 2 was unlinked");

    /* --- inserting in the middle is a pointer swap --------------------- */
    task_t d = { .id = 4 };
    proven_list_insert_after(&a.link, &d.link);

    n = 0;
    PROVEN_LIST_FOR_EACH(it, &queue) {
        task_t *t = PROVEN_LIST_ENTRY(it, task_t, link);
        if (n < 3) seen[n++] = t->id;
    }
    EXAMPLE_REQUIRE(n == 3 && seen[0] == 1 && seen[1] == 4 && seen[2] == 3,
                    "task 4 sits directly after task 1");

    /* There is nothing to destroy. The list never owned anything: `a`, `c` and
     * `d` are still perfectly good local variables, and their lifetime is the
     * function's, exactly as it would be without the list. */
    return EXAMPLE_OK();
}

Structures#

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;
} proven_list_t;

Functions and macros#

Example:

typedef struct Item {
    int value;
    proven_list_node_t link;   /* the list lives inside the object; it allocates nothing */
} Item;

proven_list_t list;
proven_list_init(&list);

Item a = { .value = 1 };
Item b = { .value = 2 };
proven_list_push_back(&list, &a.link);
proven_list_push_back(&list, &b.link);

int total = 0;
proven_list_node_t *it = NULL;
PROVEN_LIST_FOR_EACH(it, &list) {
    /* The iterator walks nodes; ENTRY converts a node back to its owner. */
    Item *item = PROVEN_LIST_ENTRY(it, Item, link);
    total += item->value;
}
proven_println("total={}", PROVEN_ARG(total));   /* 3 */

3. Ring buffer#

The problem: a queue that must not grow#

A queue between a fast producer and a slow consumer has to answer one question: what happens when the consumer falls behind? A growable queue answers "allocate more", which turns a temporary slowdown into unbounded memory growth and, eventually, into something worse than dropped work.

The hand-written alternative is an array plus a head index plus a tail index plus modulo arithmetic — and it has one famous bug. When head == tail, is the buffer empty or full? Both states look identical unless you keep a separate count or deliberately waste one slot, and every generation of programmers rediscovers this.

What this library does instead#

proven_ring_t is a fixed-capacity FIFO that keeps the count, so empty and full are distinct, and that refuses rather than grows:

• proven_ring_push on a full ring returns PROVEN_ERR_OUT_OF_BOUNDS. It does not overwrite the oldest entry and it does not reallocate. The caller decides — wait, drop the new item, or report backpressure — because only the caller knows which is right.
• proven_ring_pop on an empty ring fails rather than handing back a stale slot.

The capacity is chosen once, at creation, and that number is the policy: it says how far ahead the producer may get. Reach for a ring for an event queue, a log of recent items, an audio or sensor buffer — anywhere a bound is part of the design rather than a limitation.

Unlike most types in this library, proven_ring_t stores its allocator internally, which is why PROVEN_RING_DESTROY takes only the ring.

Wrong — treating a full ring as an error to retry immediately:

while (PROVEN_RING_PUSH(&ring, event_t, e) != PROVEN_OK) { }   /* wrong: spins forever */

Nothing in that loop consumes anything, so the ring stays full. A refusal from a bounded queue is information about the consumer, and the loop that ignores it is a hang.

Worked example: pushing until full, and what refusal looks like#

Compiled and run by the test suite.

/*
 * A ring buffer is a fixed-size queue that never moves its contents and never
 * grows. You give it a capacity once; push adds at the tail, pop removes from
 * the head, and when it is full, push REFUSES.
 *
 * The C you would otherwise write is an array plus two indices plus the modulo
 * arithmetic to wrap them, and the bug is always the same: "is it full or is it
 * empty?" - both states have head == tail unless you keep a count or waste a
 * slot. This ring keeps the count, so the question does not arise.
 *
 * Use one when a producer and a consumer run at different speeds and you want a
 * hard bound on how far ahead the producer may get: an event queue, a log ring,
 * an audio buffer. The refusal on a full ring is the feature - it is
 * backpressure. A growable queue would answer a burst by eating memory until
 * something worse happens.
 */

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

    /* Capacity of 4 events. It will never be 5. */
    proven_result_ring_t r = PROVEN_RING_INIT(alloc, int, 4);
    EXAMPLE_REQUIRE(proven_is_ok(r.err), "creating a 4-slot ring should succeed");
    proven_ring_t ring = r.value;

    /* --- push until full ---------------------------------------------- */
    for (int i = 1; i <= 4; ++i) {
        proven_err_t err = PROVEN_RING_PUSH(&ring, int, i);
        EXAMPLE_REQUIRE(proven_is_ok(err), "the first four pushes fit");
    }

    /* The fifth push is refused. It does not overwrite the oldest entry, and it
     * does not grow: a full ring is a full ring, and the caller decides what to
     * do about it - wait, drop the new event, or report backpressure. */
    proven_err_t full = PROVEN_RING_PUSH(&ring, int, 5);
    EXAMPLE_REQUIRE(full == PROVEN_ERR_OUT_OF_BOUNDS,
                    "pushing into a full ring must be refused, not silently absorbed");

    /* --- pop in the order they were pushed ----------------------------- */
    int out = 0;
    proven_err_t err = PROVEN_RING_POP(&ring, int, &out);
    EXAMPLE_REQUIRE(proven_is_ok(err) && out == 1, "pop returns the oldest entry first");

    /* Now there is room again, and the ring wraps around its storage without
     * moving anything. */
    err = PROVEN_RING_PUSH(&ring, int, 5);
    EXAMPLE_REQUIRE(proven_is_ok(err), "after a pop there is room for one more");

    int expected[] = { 2, 3, 4, 5 };
    for (int i = 0; i < 4; ++i) {
        err = PROVEN_RING_POP(&ring, int, &out);
        EXAMPLE_REQUIRE(proven_is_ok(err) && out == expected[i],
                        "entries come out in the order they went in");
    }

    /* --- empty behaves like full: it refuses, it does not invent data --- */
    err = PROVEN_RING_POP(&ring, int, &out);
    EXAMPLE_REQUIRE(!proven_is_ok(err), "popping an empty ring must fail rather than return junk");

    PROVEN_RING_DESTROY(&ring);
    return EXAMPLE_OK();
}

Structures#

typedef struct {
    proven_allocator_t alloc;
    proven_mem_mut_t internal;
    proven_size_t head;
    proven_size_t tail;
    proven_size_t len;
    proven_size_t cap;
    proven_size_t elem_size;
    proven_size_t align;
} proven_ring_t;

typedef struct {
    proven_err_t err;
    proven_ring_t value;
} proven_result_ring_t;

Functions and macros#

Example:

proven_result_ring_t r = PROVEN_RING_INIT(alloc, int, 8);
if (!proven_is_ok(r.err)) {
    return;
}
proven_ring_t q = r.value;

proven_err_t e = PROVEN_RING_PUSH(&q, int, 7);
if (!proven_is_ok(e)) {
    /* The ring is fixed-capacity: a full ring is PROVEN_ERR_OUT_OF_BOUNDS,
     * never a silent grow. */
    PROVEN_RING_DESTROY(&q);
    return;
}

int out = 0;
e = PROVEN_RING_POP(&q, int, &out);   /* FIFO: out == 7. Empty ring is OUT_OF_BOUNDS. */
(void)e;

PROVEN_RING_DESTROY(&q);

4. Hash map#

proven_map_t is an open-addressing hash map with tombstones. It supports integer keys and borrowed or owned U8 string keys. It stores its allocator internally.

Structures#

typedef enum {
    PROVEN_KEY_TYPE_INT,          /* keys are proven_size_t integers */
    PROVEN_KEY_TYPE_U8_BORROWED,  /* keys are u8 views; caller keeps the bytes alive */
    PROVEN_KEY_TYPE_U8_OWNED      /* keys are u8 views; the map copies and frees the bytes */
} proven_key_type_t;

typedef union {
    proven_size_t id;             /* used when key_type == PROVEN_KEY_TYPE_INT */
    proven_u8str_view_t str;      /* used for the two U8 key modes */
} proven_map_key_t;

typedef struct {
    proven_allocator_t alloc;     /* allocator for the bucket array and owned keys */
    proven_mem_mut_t internal;    /* the single contiguous bucket array (ptr + size) */
    proven_size_t len;            /* live entries */
    proven_size_t used;           /* live entries + tombstones (drives the load factor) */
    proven_size_t cap;            /* number of buckets, always a power of two */
    proven_size_t elem_size;      /* size of one stored value */
    proven_size_t align;          /* alignment requested for the value */
    proven_size_t bucket_stride;  /* bytes per bucket: align_up(header + elem_size) */
    proven_size_t payload_offset; /* bytes from a bucket start to its value payload */
    proven_key_type_t key_type;   /* key mode chosen at create time */
} proven_map_t;

typedef struct {
    proven_err_t err;
    proven_map_t value;
} proven_result_map_t;

How it works internally#

The map is a single flat array of cap buckets — there are no per-entry allocations for values (and none for keys in INT/BORROWED mode), so lookups stay cache-friendly. Each bucket is laid out as:

[ header: state + key ][ padding to the value's alignment ][ value payload ]
^ bucket start                                              ^ payload_offset
|<------------------------- bucket_stride ------------------------------------>|

The header's state is one of EMPTY (never used), OCCUPIED (holds a live key+value), or TOMBSTONE (a removed entry). payload_offset and bucket_stride are computed once at create time from elem_size/align, so addressing bucket i's value is just internal.ptr + i*bucket_stride + payload_offset.

• Hashing, and why the default is the safe one. Integer keys go through a SplitMix/Murmur-style bit-mix finaliser (so sequential ids spread across buckets). String keys are hashed with keyed SipHash-2-4 under a per-process secret drawn once from the OS CSPRNG — because a map that hashes untrusted keys with a predictable function is a denial of service waiting to happen: an attacker who controls the keys computes collisions offline, floods them all into one bucket, and turns every lookup into a linear scan. Keying the hash with a secret they cannot see is what closes that, and it is the same choice Python, Rust, and the Linux kernel made for their own tables. If your keys all come from your own program, proven_map_create_trusted opts into fast unkeyed FNV-1a instead; proven_map_hash shows you which function a given map actually uses. (On a freestanding target, which has no CSPRNG and no attacker model, string keys fall back to FNV.)
• Probing. Linear open addressing: the start bucket is hash & (cap - 1) (cheap because cap is a power of two), then the search walks forward one bucket at a time, wrapping around, until it finds the key (OCCUPIED with an equal key) or an EMPTY bucket (which proves the key is absent). Linear probing keeps the walked buckets contiguous in memory.
• Removal and tombstones. proven_map_remove cannot just blank a bucket — that would cut a probe chain and hide later keys. It marks the bucket TOMBSTONE instead. Tombstones are skipped by lookups but still consume a slot, which is why used (live + tombstones) — not len — drives growth.
• Load factor and resize. When used >= cap * 3/4, the map allocates a new bucket array of the next power of two and rehashes every OCCUPIED entry into it, dropping all tombstones in the process. Capacity only grows; it never shrinks. Reserve ahead with proven_map_reserve (especially with arena allocators, to avoid leaving dead arrays behind).

Key modes — choosing one#

• PROVEN_KEY_TYPE_INT: keys are proven_size_t. No key storage.
• PROVEN_KEY_TYPE_U8_BORROWED: the bucket stores the view (pointer + length). The map never copies the bytes, so the caller must keep the exact bytes alive and unmoved for the whole time the entry exists. Cheapest for keys that already live somewhere stable (string literals, interned strings).
• PROVEN_KEY_TYPE_U8_OWNED: on insert (proven_map_set_u8_owned / PROVEN_MAP_SET_U8_OWNED) the map duplicates the key bytes into its own storage and frees them on remove/destroy, so the source buffer may be released or reused immediately after the call.

The set_with_scratch / alias case#

If the element you pass to proven_map_set points into the map's own bucket array (for example, copying a value from one key to another via a pointer returned by proven_map_get), a rehash triggered by that same insert would move or free the bytes you are reading. proven_map_set_with_scratch (and the *_WITH_SCRATCH_* macros) capture the source bytes into a temporary buffer from the scratch allocator first, so the insert is alias-safe. Persistent storage still uses map->alloc; the scratch allocator is only for that transient copy.

Functions#

Macros#

Owned key path:

PROVEN_KEY_TYPE_U8_OWNED stores a duplicate of the key bytes inside the map. Use it when the source buffer may move or be freed after insertion. The owned bytes are released on remove and destroy, and they move with the entry during rehash.

PROVEN_HARDENED and debug validation can reject some borrowed-key pointers that fall inside the map's own internal storage. That check is defensive only; it does not make borrowed keys self-owning.

Example:

typedef struct UserInfo {
    int level;
    double budget;
} UserInfo;

proven_result_map_t r = PROVEN_MAP_INIT_INT(alloc, UserInfo, 8);
if (!proven_is_ok(r.err)) {
    return;
}
proven_map_t users = r.value;

UserInfo u = { .level = 3, .budget = 99.0 };
(void)PROVEN_MAP_SET_INT(&users, 404, UserInfo, u);

/* GET returns a pointer into the bucket array, or NULL when absent. Any insert
 * that rehashes invalidates it: look it up, use it, drop it. */
const UserInfo *found = PROVEN_MAP_GET_INT(&users, UserInfo, 404);
if (found) {
    proven_println("level={}", PROVEN_ARG(found->level));
}

PROVEN_MAP_DESTROY(&users);

5. Algorithms#

Array algorithms operate on proven_array_t and a comparison callback.

Comparison function#

typedef int (*proven_compare_fn_t)(const void *a, const void *b);

Return negative if a < b, zero if equal, positive if a > b.

Functions#

proven_array_sort is an introsort: a Bentley-McIlroy three-way partition, an insertion-sort cutoff for small ranges, and a heapsort fallback once the recursion exceeds 2*log2(n) levels.

Two properties are worth stating, because they are the ones that bite:

• O(n log n) is a guarantee, not a typical case. The heapsort fallback is what makes it one. A sort whose worst case can be reached by an adversarial ordering is a denial of service in any program that sorts data it did not author.

• Duplicate keys are the fast case, not the slow one. Elements equal to the pivot are collected into a run that is final and never recursed into, so all-equal input costs a single pass. This matters because low-cardinality keys

  • a status column, an enum, a bucket id - are what callers actually sort by, and they are exactly what a naive two-way partition degrades on.

The sort is not stable: equal elements may be reordered.

The comparator is an ordinary file-scope function, so the shape is:

static int cmp_int(const void *a, const void *b) {
    int x = *(const int *)a;
    int y = *(const int *)b;
    return (x > y) - (x < y);   /* not (x - y): that overflows */
}

proven_array_sort(&nums, cmp_int);
int key = 20;
int *hit = proven_array_binary_search(&nums, &key, cmp_int);

The worked example at the end of this chapter (manual/examples/ex_04_array.c) is the compiled-and-run version of exactly this.

6. Hashing, by use case#

There is no single "hash". Which function is correct depends entirely on what you are doing with the result, and reaching for the wrong one gives you either a program that is needlessly slow or one that is quietly insecure. proven/hash.h offers exactly one primitive per job so the choice is made once you name the job:

The one line to remember: CRC-32 and FNV detect accident, not attack. Do not use them to decide whether two things are "the same" when someone might benefit from fooling you — that is what proven_sha256 is for. And a keyed hash is only safe if the key is a real secret chosen once from real randomness; a fixed key is no key at all.

Every function is byte-exact and endianness-independent: the same input gives the same output on any target, because a fingerprint that changed with the machine would be a fingerprint of the machine, not the content. All four are royalty-free algorithms (FNV, CRC-32: public domain; SipHash: CC0; SHA-256: FIPS 180-4, unpatented), implemented from their specifications and checked against each one's official known-answer vectors.

Reference#

The one structure you hold:

typedef struct {
    /* Opaque. A running SHA-256: the 8-word chain value, a 64-byte block being
       filled, and the message length. Declare one, init it, update it, finalise it. */
} proven_sha256_t;

#define PROVEN_SHA256_SIZE 32   /* the digest; size your output buffer with this */

proven_sha256_t allocates nothing — it is caller-owned state, so there is nothing to destroy.

Cautions, and what goes wrong#

A keyed hash with a fixed key is not a keyed hash. The security of proven_hash_keyed rests entirely on the key being a secret drawn once from real randomness. This is why proven_map_create does it for you and why you should almost never call proven_hash_keyed yourself for a table.

Wrong:

proven_byte_t key[16] = { 0 };            /* wrong: a "secret" everyone knows */
proven_u64 h = proven_hash_keyed(user_input, key);

proven_byte_t key[16];
memcpy(key, &timestamp, sizeof timestamp); /* wrong: guessable, and mostly zero */

Correct — draw it once, at startup, from the OS:

proven_byte_t key[16];
if (proven_random_bytes(key, sizeof key)) {
    proven_u64 h = proven_hash_keyed(
        proven_mem_view_from_u8(PROVEN_LIT("session-token")), key);
    (void)h;
}

Do not use CRC-32 or FNV to decide two things are "the same" when someone might gain by fooling you. Both are trivially forgeable: producing a second input with the same CRC-32 is schoolbook arithmetic.

Wrong — a content-addressed store an attacker can poison:

if (proven_crc32(incoming) == stored_crc) {
    accept_as_identical(incoming);   /* wrong: a forged collision costs seconds */
}

Correct — a fingerprint that must not be foolable is proven_sha256, compared over all 32 bytes.

A digest buffer that is not PROVEN_SHA256_SIZE is a buffer overflow. proven_sha256 writes exactly 32 bytes and does not know how big your array is.

proven_byte_t digest[16];        /* wrong: SHA-256 is 32 bytes */
proven_sha256(data, digest);     /* writes 32 into a 16-byte buffer */

Compiled and run by the test suite:

/*
 * Hashing, by use case. The module gives you exactly one function per job, so the only
 * decision is which job you have - and getting THAT wrong is the whole danger.
 */

int main(void) {
    proven_mem_view_t data = proven_mem_view_from_u8(PROVEN_LIT("the quick brown fox"));

    /* Job 1: hash a key into your own table, trusted input. Fast, non-cryptographic. */
    proven_u64 table_hash = proven_hash_bytes(data);
    EXAMPLE_REQUIRE(table_hash != 0, "FNV-1a produces a spread-out 64-bit value");

    /* Job 2: hash a key from UNTRUSTED input. Same purpose, but an attacker who picks the
     * input still cannot make everything collide, because they do not have the key. Pick
     * the key once at startup from real randomness; a fixed key defeats the point. */
    proven_byte_t key[16] = { 0 };   /* in real code: fill from a random source, once */
    proven_u64 safe_hash = proven_hash_keyed(data, key);
    EXAMPLE_REQUIRE(safe_hash != table_hash, "a keyed hash is a different function");

    /* Job 3: did these bytes get corrupted? A checksum, not a hash. Interoperates with
     * gzip/zlib/PNG, which all carry this exact CRC-32. */
    proven_u32 checksum = proven_crc32(data);
    /* The canonical CRC-32 sanity value, so you can see it is the real one: */
    EXAMPLE_REQUIRE(proven_crc32(proven_mem_view_from_u8(PROVEN_LIT("123456789"))) == 0xcbf43926u,
                    "CRC-32 of \"123456789\" is the shared check value");
    (void)checksum;

    /* Job 4: fingerprint content - dedup, content-addressing, "are these the same file",
     * answered safely even against someone trying to forge a match. This is the one you
     * reach for when the answer must not be foolable. */
    proven_byte_t digest[PROVEN_SHA256_SIZE];
    proven_sha256(data, digest);

    char hex[65];
    proven_sha256_to_hex(digest, hex);
    /* The same spelling sha256sum and git print, so it interoperates: */
    EXAMPLE_REQUIRE(hex[64] == '\0' && proven_cstr_len(hex) == 64,
                    "a SHA-256 fingerprint is 64 lowercase hex characters");

    /* SHA-256 streams, for content you cannot hold in memory at once - the digest depends
     * only on the bytes, never on how they were chunked. */
    proven_sha256_t ctx;
    proven_sha256_init(&ctx);
    proven_sha256_update(&ctx, proven_mem_view_from_u8(PROVEN_LIT("the quick ")));
    proven_sha256_update(&ctx, proven_mem_view_from_u8(PROVEN_LIT("brown fox")));
    proven_byte_t streamed[PROVEN_SHA256_SIZE];
    proven_sha256_final(&ctx, streamed);

    bool same = true;
    for (proven_size_t i = 0; i < PROVEN_SHA256_SIZE; ++i) {
        if (streamed[i] != digest[i]) same = false;
    }
    EXAMPLE_REQUIRE(same, "two updates of the halves equal one hash of the whole");

    return EXAMPLE_OK();
}

7. Bytes to text: hex and Base64#

Once you can hash a thing (above) and draw a random token (random.h), you need to write those bytes somewhere that only holds text — a URL, an HTTP header, a log line, a JSON string. That is encode.h. No cryptography, no compression; the two encodings everything already agrees on, done without hidden allocation and without the two ways they are usually got wrong.

Two refusals are the point:

• A decoder validates its whole input before writing a byte. Text from outside the program is not guaranteed to be valid; a stray character, a bad length, bad padding, or embedded whitespace is PROVEN_ERR_INVALID_ENCODING with nothing committed — not a read past the end, and not a silently short result one byte into which the caller finds the corruption. proven_base64_decode accepts both alphabets and padded-or-not, because a decoder that only takes what it emits rejects half the Base64 in the world.
• The output size is a call, not a guess — proven_hex_encoded_size, proven_base64_encoded_size, and their decode counterparts. A buffer one byte too small is PROVEN_ERR_OUT_OF_BOUNDS with nothing written, never a truncated prefix.

It is pure computation — no allocation, no OS — and available freestanding.

Reference#

Every call takes the input, a caller-owned output buffer and its capacity, and an optional written_out. None of them allocate.

written_out may be NULL. It is set to 0 on entry and on every error path, so it is never stale.

Cautions, and what goes wrong#

Size the output with the size function, not by eye. The encoders refuse a short buffer rather than truncating — which means the failure you get from a hand-computed size is an error you have to handle, not a silent corruption. That is the good outcome; the point is you will still have to handle it.

Wrong — the classic off-by-one, and it now fails instead of overflowing:

proven_byte_t out[16];                       /* wrong: 12 bytes of hex needs 24 chars */
proven_hex_encode(twelve_bytes, out, sizeof out, &w);   /* OUT_OF_BOUNDS, nothing written */

Correct:

proven_mem_view_t data = proven_mem_view_from_u8(PROVEN_LIT("twelve bytes"));
proven_byte_t out[64];
proven_size_t w = 0;
if (proven_hex_encoded_size(data.size) <= sizeof out &&
    proven_is_ok(proven_hex_encode(data, out, sizeof out, &w))) {
    /* `w` characters of lowercase hex in `out` - not NUL-terminated */
}

Base64URL emits no padding, and the decoder accepts that. proven_base64_decoded_size rounds up so it is a correct upper bound for unpadded text too. Do not "improve" on it with 3 * (n / 4) — that floors away the 1-2 bytes an unpadded tail carries, and you will fail to decode this library's own URL-safe output. (It did exactly that, once, and an audit caught it.)

proven_size_t cap = 3 * (text_len / 4);   /* wrong: 0 for "QQ", which decodes to 1 byte */

Never hand-roll the decoder. The whole reason these exist is that a decode reads text from outside your program, and the two-line loop everyone writes trusts it.

Wrong — reads past the end on odd input, and accepts junk as data:

for (size_t i = 0; i < len; i += 2)               /* wrong: no length check */
    out[i/2] = (hexval(text[i]) << 4) | hexval(text[i+1]);   /* wrong: no validation */

proven_hex_decode validates the whole input before writing a single byte, so a stray character near the end cannot leave you holding a half-decoded prefix you believe is complete.

Whitespace is not skipped, on purpose. A pasted, line-wrapped Base64 blob is INVALID_ENCODING, not a silently different result. If you want to accept wrapped input, strip the whitespace yourself — deliberately, where you can see it.

Size the destination with the size functions, never by hand. Each encoding has a pair — proven_hex_encoded_size() / proven_hex_decoded_size() and proven_base64_encoded_size() / proven_base64_decoded_size() — and they differ in what they promise:

The example below ends with that: it allocates a destination sized by proven_base64_encoded_size(), encodes into it, sizes the reverse buffer with proven_base64_decoded_size(), decodes, and round-trips the same bytes through proven_hex_decode() — including the uppercase input real tools produce, and the odd-length input that cannot be a whole number of bytes.

Compiled and run by the test suite:

/*
 * Bytes to text, by use case. The rule is the same one hashing follows: one function per job,
 * and the danger is picking the wrong job. Hex for something a human reads; Base64URL for
 * something that goes in a URL; standard Base64 for something that goes on the wire.
 */

int main(void) {
    proven_mem_view_t data = proven_mem_view_from_u8(PROVEN_LIT("the quick brown fox"));

    /* Job 1: a digest a human will read or paste - hex, the spelling sha256sum and git use. */
    proven_byte_t hex[64];   /* proven_hex_encoded_size(19) = 38 */
    proven_size_t hn = 0;
    EXAMPLE_REQUIRE(proven_is_ok(proven_hex_encode(data, hex, sizeof hex, &hn)),
                    "hex encode into a buffer sized by proven_hex_encoded_size");
    EXAMPLE_REQUIRE(hn == proven_hex_encoded_size(data.size), "two hex chars per byte");

    /* Job 2: a token that goes in a URL - Base64URL, so nothing needs percent-escaping and
     * there is no '=' padding for a parser to trip over. */
    proven_byte_t token_bytes[16] = { 0 };   /* in real code: proven_random_bytes(token_bytes, 16) */
    proven_byte_t url[32];
    proven_size_t un = 0;
    EXAMPLE_REQUIRE(proven_is_ok(proven_base64url_encode(
                        (proven_mem_view_t){ token_bytes, sizeof token_bytes }, url, sizeof url, &un)),
                    "base64url encode a token");
    /* No '=' in a URL-safe token. */
    bool has_pad = false;
    for (proven_size_t i = 0; i < un; ++i) if (url[i] == '=') has_pad = true;
    EXAMPLE_REQUIRE(!has_pad, "the URL form emits no padding");

    /* Job 3: bytes on the wire - standard Base64, the +/= alphabet HTTP and MIME expect. */
    proven_byte_t b64[64];
    proven_size_t bn = 0;
    EXAMPLE_REQUIRE(proven_is_ok(proven_base64_encode(data, b64, sizeof b64, &bn)),
                    "standard base64 encode");

    /* And it round-trips: decode gives back exactly the bytes. A decoder that accepts both
     * alphabets and padded-or-not is deliberate - real input comes in every shape. */
    proven_byte_t back[32];
    proven_size_t dn = 0;
    EXAMPLE_REQUIRE(proven_is_ok(proven_base64_decode(
                        (proven_mem_view_t){ b64, bn }, back, sizeof back, &dn)),
                    "decode the base64 back");
    EXAMPLE_REQUIRE(dn == data.size && proven_memcmp(back, data.ptr, dn) == 0,
                    "what comes back is exactly what went in");

    /* The point of a validating decoder: junk is refused, not guessed. A caller who fed this
     * to a two-line loop would read past the end or get a silently short result. */
    proven_err_t bad = proven_base64_decode(
        proven_mem_view_from_u8(PROVEN_LIT("not valid base64!!")), back, sizeof back, &dn);
    EXAMPLE_REQUIRE(bad == PROVEN_ERR_INVALID_ENCODING,
                    "a stray character is INVALID_ENCODING, with nothing committed");

    /* And a buffer one byte too small is refused, never truncated. */
    proven_byte_t tiny[4];
    EXAMPLE_REQUIRE(proven_hex_encode(data, tiny, sizeof tiny, &hn) == PROVEN_ERR_OUT_OF_BOUNDS,
                    "a too-small output buffer is OUT_OF_BOUNDS, not a truncated prefix");

    /* --- sizing the destination buffer, instead of guessing ---------------- */

    /* Every encode and decode above wrote into a fixed array that was obviously
     * big enough. Real code allocates the destination, and then the size has to
     * be computed rather than remembered. That is what the four size functions
     * are for - one per direction, per encoding. */
    proven_allocator_t alloc = proven_heap_allocator();

    proven_size_t need = proven_base64_encoded_size(data.size);
    EXAMPLE_REQUIRE(need > 0, "an encoded size must be computed, not guessed");

    proven_result_mem_mut_t out = alloc.alloc_fn(alloc.ctx, need, 1);
    EXAMPLE_REQUIRE(proven_is_ok(out.err), "allocating exactly the encoded size must succeed");

    proven_size_t wrote = 0;
    EXAMPLE_REQUIRE(proven_is_ok(proven_base64_encode(data, out.value.ptr, out.value.size, &wrote)),
                    "encoding into a buffer sized by the size function must fit exactly");
    EXAMPLE_REQUIRE(wrote == need, "and use all of it: this size is exact for standard base64");

    /* The decode direction is an UPPER BOUND, not an exact count: base64 text
     * may carry padding, so the decoder reports how many bytes it really wrote.
     * Size the buffer with the bound; use the reported count afterwards. */
    proven_size_t bound = proven_base64_decoded_size(wrote);
    EXAMPLE_REQUIRE(bound >= data.size, "the decoded bound must cover the real output");

    proven_result_mem_mut_t plain = alloc.alloc_fn(alloc.ctx, bound, 1);
    EXAMPLE_REQUIRE(proven_is_ok(plain.err), "allocating the decode bound must succeed");

    proven_size_t got = 0;
    EXAMPLE_REQUIRE(proven_is_ok(proven_base64_decode(
                        (proven_mem_view_t){ out.value.ptr, wrote }, plain.value.ptr, plain.value.size, &got)),
                    "decoding back must succeed");
    EXAMPLE_REQUIRE(got == data.size && proven_memcmp(plain.value.ptr, data.ptr, got) == 0,
                    "and reproduce the original bytes exactly");

    /* Hex has the same pair. Its decoded bound is exact when the input length is
     * even, which valid hex always is - an odd length is malformed input, and
     * the decoder says so rather than dropping the last digit. */
    proven_size_t hex_len = 0;
    EXAMPLE_REQUIRE(proven_is_ok(proven_hex_encode(data, hex, sizeof hex, &hex_len)),
                    "re-encode to hex, since the refused call above left its count unusable");

    proven_size_t hex_bound = proven_hex_decoded_size(hex_len);
    EXAMPLE_REQUIRE(hex_bound == data.size, "two hex characters decode to one byte");

    proven_byte_t from_hex[32];
    proven_size_t hex_got = 0;
    EXAMPLE_REQUIRE(proven_is_ok(proven_hex_decode(
                        (proven_mem_view_t){ hex, hex_len }, from_hex, sizeof from_hex, &hex_got)),
                    "hex decodes back to the original bytes");
    EXAMPLE_REQUIRE(hex_got == data.size && proven_memcmp(from_hex, data.ptr, hex_got) == 0,
                    "and the round trip is exact");

    /* Hex is case-insensitive on the way in, which matters because different
     * tools print different cases of the same digest. */
    EXAMPLE_REQUIRE(proven_is_ok(proven_hex_decode(
                        proven_mem_view_from_u8(PROVEN_LIT("DEADBEEF")), from_hex, sizeof from_hex, &hex_got)),
                    "uppercase hex decodes too");
    EXAMPLE_REQUIRE(hex_got == 4, "and yields one byte per two characters");

    /* An odd number of characters cannot be a whole number of bytes. */
    EXAMPLE_REQUIRE(proven_hex_decode(proven_mem_view_from_u8(PROVEN_LIT("abc")),
                                      from_hex, sizeof from_hex, &hex_got) == PROVEN_ERR_INVALID_ENCODING,
                    "an odd-length hex string is malformed, not silently truncated");

    alloc.free_fn(alloc.ctx, plain.value.ptr);
    alloc.free_fn(alloc.ctx, out.value.ptr);

    (void)url; (void)un;
    return EXAMPLE_OK();
}

8. Examples and misuse cases#

Pointers into arrays can become stale#

Wrong:

int *p = PROVEN_ARRAY_GET_MUT(&nums, int, 0);
PROVEN_ARRAY_PUSH(&nums, int, 30);
*p = 99; /* wrong: push may have reallocated the array */

Correct:

proven_result_array_t r = PROVEN_ARRAY_INIT(alloc, int, 2);
if (!proven_is_ok(r.err)) {
    return;
}
proven_array_t nums = r.value;
(void)PROVEN_ARRAY_PUSH(&nums, int, 10);

/* Push first, then take the pointer. A pointer fetched before a push may point
 * at a block the array has already reallocated away. */
(void)PROVEN_ARRAY_PUSH(&nums, int, 30);
int *p = PROVEN_ARRAY_GET_MUT(&nums, int, 0);
if (p) {
    *p = 99;
}

PROVEN_ARRAY_DESTROY(&nums);

One intrusive node belongs to one list at a time#

Wrong:

proven_list_push_back(&list_a, &item.link);
proven_list_push_back(&list_b, &item.link); /* wrong */

Use one embedded node per membership.

Remove while iterating with the safe macro#

Correct:

typedef struct Item {
    int value;
    proven_list_node_t link;
} Item;

proven_list_t list;
proven_list_init(&list);
Item a = { .value = 1 };
Item b = { .value = 2 };
proven_list_push_back(&list, &a.link);
proven_list_push_back(&list, &b.link);

/* The SAFE form reads `it->next` into `next` before the body runs, so removing
 * `it` (which nulls its links) cannot strand the loop. */
proven_list_node_t *it = NULL;
proven_list_node_t *next = NULL;
PROVEN_LIST_FOR_EACH_SAFE(it, next, &list) {
    Item *item = PROVEN_LIST_ENTRY(it, Item, link);
    if (item->value % 2 == 0) {
        proven_list_remove(it);
    }
}

Ring push does not grow#

Wrong:

PROVEN_RING_PUSH(&q, int, value); /* wrong if you ignore full-ring errors */

Correct:

proven_result_ring_t r = PROVEN_RING_INIT(alloc, int, 2);
if (!proven_is_ok(r.err)) {
    return;
}
proven_ring_t q = r.value;

int value = 7;
for (int i = 0; i < 3; ++i) {
    proven_err_t e = PROVEN_RING_PUSH(&q, int, value);
    if (e == PROVEN_ERR_OUT_OF_BOUNDS) {
        /* The ring is full. Drop the item, or drain one first - but decide. */
        int drop = 0;
        (void)PROVEN_RING_POP(&q, int, &drop);
        e = PROVEN_RING_PUSH(&q, int, value);
    }
    (void)e;
}

PROVEN_RING_DESTROY(&q);

Borrowed map keys must outlive entries#

Wrong:

proven_u8str_t key = make_key(alloc);
PROVEN_MAP_SET_U8_BORROWED(&m, proven_u8str_as_view(&key), int, 1);
proven_u8str_destroy(alloc, &key);
/* wrong: map still points at freed key bytes */

Correct options:

• Use string literals or other stable storage for borrowed keys.
• Store owned key objects elsewhere and destroy them after removing map entries.
• Use PROVEN_KEY_TYPE_U8_OWNED and proven_map_set_u8_owned() when the map should own key storage.

Use scratch when inserting a value borrowed from the same map#

If element points into map storage and insertion can rehash, use proven_map_set_with_scratch() or the scratch macros.

proven_result_map_t r = PROVEN_MAP_INIT_INT(alloc, int, 4);
if (!proven_is_ok(r.err)) {
    return;
}
proven_map_t m = r.value;
(void)PROVEN_MAP_SET_INT(&m, 1, int, 42);

/* `src` points into the map's own bucket array. Passing it straight to
 * proven_map_set would be an alias: a rehash triggered by that same insert can
 * free the bytes it is still reading from. The scratch form captures the source
 * bytes into a temporary from `scratch` first, so the insert is alias-safe. */
const int *src = PROVEN_MAP_GET_INT(&m, int, 1);
if (src) {
    (void)proven_map_set_with_scratch(&m, (proven_map_key_t){ .id = 2 }, src, scratch);
}

PROVEN_MAP_DESTROY(&m);

Binary search requires sorted input#

Wrong:

int *hit = proven_array_binary_search(&nums, &key, cmp_int);
/* wrong if nums was not sorted by cmp_int */

Worked example: array, sort, binary search#

Compiled and run by the test suite. Note the sort's behaviour on duplicate keys: they are the fast case, not the quadratic one.

/*
 * proven_array_t is a growable vector of one element type. It stores the
 * allocator you created it with, so push can grow and destroy can free without
 * you passing the allocator back in - which also means the array must be
 * destroyed with nothing but itself.
 *
 * The PROVEN_ARRAY_* macros are the type-safe face of the void* core: they
 * derive sizeof/alignof from the type and hand the element to the array by
 * pointer, so pushing an int into an array of records will not compile.
 */

/* A task queue keyed by priority. Real data is low-cardinality: three
 * priorities, many tasks. That matters for the sort - see below. */
typedef struct {
    int priority;
    int id;
} task_t;

/* The comparator is the array's ordering. The same one MUST be used for the
 * sort and for the binary search - a search under a different order is a bug
 * the compiler cannot see.
 *
 * The (x > y) - (x < y) form is deliberate: subtracting the two ints would
 * overflow for large values and hand back a nonsense sign. */
static int cmp_priority(const void *a, const void *b) {
    int x = ((const task_t *)a)->priority;
    int y = ((const task_t *)b)->priority;
    return (x > y) - (x < y);
}

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

    /* --- push / get / pop --------------------------------------------------- */
    /* init_cap is a hint, not a limit: push grows past it. Sizing it right just
     * avoids the reallocations. */
    proven_result_array_t r = PROVEN_ARRAY_INIT(alloc, task_t, 4);
    EXAMPLE_REQUIRE(proven_is_ok(r.err), "creating an array of task_t must succeed");
    if (!proven_is_ok(r.err)) {
        return 1;
    }
    proven_array_t tasks = r.value;

    /* Deliberately duplicate-heavy, because that is what real keys look like:
     * a status column, an enum, a bucket id. */
    static const task_t seed[] = {
        { .priority = 2, .id = 10 }, { .priority = 0, .id = 11 },
        { .priority = 2, .id = 12 }, { .priority = 1, .id = 13 },
        { .priority = 2, .id = 14 }, { .priority = 0, .id = 15 },
        { .priority = 1, .id = 16 }, { .priority = 2, .id = 17 },
    };

    for (proven_size_t i = 0; i < sizeof seed / sizeof seed[0]; ++i) {
        proven_err_t err = PROVEN_ARRAY_PUSH(&tasks, task_t, seed[i]);
        EXAMPLE_REQUIRE(proven_is_ok(err), "pushing into a growable array must succeed");
        if (!proven_is_ok(err)) {
            PROVEN_ARRAY_DESTROY(&tasks);
            return 1;
        }
    }
    EXAMPLE_REQUIRE(tasks.len == 8, "eight pushes give eight elements");

    /* get returns a pointer INTO the array's storage - it is not a copy, and the
     * next push may reallocate and leave it dangling. Fetch it after the pushes,
     * use it, do not store it. */
    const task_t *front = PROVEN_ARRAY_GET(&tasks, task_t, 0);
    EXAMPLE_REQUIRE(front && front->id == 10, "element 0 is the first one pushed");

    /* Out of range is a null pointer, not a crash and not UB. */
    EXAMPLE_REQUIRE(PROVEN_ARRAY_GET(&tasks, task_t, 99) == NULL, "an out-of-range index yields NULL");

    /* pop copies the last element out (pass NULL to just discard it). */
    task_t last = {0};
    proven_err_t err = PROVEN_ARRAY_POP(&tasks, task_t, &last);
    EXAMPLE_REQUIRE(proven_is_ok(err), "popping a non-empty array must succeed");
    EXAMPLE_REQUIRE(last.id == 17 && tasks.len == 7, "pop returns the last element and shrinks the array");

    /* Put it back: the rest of the example wants all eight. */
    err = PROVEN_ARRAY_PUSH(&tasks, task_t, last);
    EXAMPLE_REQUIRE(proven_is_ok(err), "pushing the popped element back must succeed");

    /* --- sort --------------------------------------------------------------- */
    /* An introsort: O(n log n) is a guarantee, not an average - the heapsort
     * fallback rules out the quadratic case an adversary could otherwise steer
     * you into. And equal keys are the FAST path here: everything equal to the
     * pivot is partitioned into a run that is never recursed into, so the
     * duplicate priorities above cost less than distinct ones would, not more.
     *
     * It is not stable: task 10 and task 12 may come out in either order. */
    proven_array_sort(&tasks, cmp_priority);

    for (proven_size_t i = 1; i < tasks.len; ++i) {
        const task_t *prev = PROVEN_ARRAY_GET(&tasks, task_t, i - 1);
        const task_t *cur  = PROVEN_ARRAY_GET(&tasks, task_t, i);
        EXAMPLE_REQUIRE(prev && cur && prev->priority <= cur->priority,
                        "after sorting, priorities must be non-decreasing");
    }

    /* --- binary search ------------------------------------------------------ */
    /* Only legal because the array is sorted by this exact comparator. The key
     * is a whole element, but only the fields the comparator reads matter. */
    task_t key = { .priority = 1, .id = 0 };
    const task_t *hit = (const task_t *)proven_array_binary_search(&tasks, &key, cmp_priority);
    EXAMPLE_REQUIRE(hit != NULL, "priority 1 is present, so the search must find it");
    EXAMPLE_REQUIRE(hit && hit->priority == 1, "the hit must be an element with the searched key");
    /* With duplicate keys it finds SOME element with that key, not the first one.
     * If you need the first, scan backwards from the hit. */

    task_t absent = { .priority = 9, .id = 0 };
    EXAMPLE_REQUIRE(proven_array_binary_search(&tasks, &absent, cmp_priority) == NULL,
                    "a key that is not there must return NULL");

    printf("tasks: %zu sorted, found priority %d (id %d)\n",
           (size_t)tasks.len, hit ? hit->priority : -1, hit ? hit->id : -1);

    /* The array owns its element storage; destroy returns it through the
     * allocator the array was created with. Elements are plain data here - if
     * they owned anything, you would have to destroy each one first. */
    PROVEN_ARRAY_DESTROY(&tasks);
    return EXAMPLE_OK();
}

Worked example: a map with integer keys and with owned string keys#

Compiled and run by the test suite. The owned-key half proves the point that is easy to get wrong: the map copies the key, so the buffer you built it in is yours to reuse immediately.

/*
 * proven_map_t is a flat open-addressing hash map. The value type is fixed at
 * create time and stored inline in the bucket array - there is no per-entry
 * allocation for values, and get hands back a pointer straight into that array.
 *
 * The interesting decision is the KEY:
 *
 *   PROVEN_KEY_TYPE_INT          - the key is a proven_size_t. Nothing to own.
 *   PROVEN_KEY_TYPE_U8_BORROWED  - the bucket stores your pointer and length.
 *                                  The map never copies the bytes, so YOU must
 *                                  keep them alive and unmoved for as long as
 *                                  the entry exists. Right for string literals.
 *   PROVEN_KEY_TYPE_U8_OWNED     - the map copies the key bytes into its own
 *                                  storage and frees them again. Right for keys
 *                                  built at runtime, which is most of them.
 *
 * The second half of this example is the reason OWNED exists.
 */

typedef struct {
    int  level;
    long score;
} player_t;

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

    /* --- integer keys ------------------------------------------------------- */
    proven_result_map_t r = PROVEN_MAP_INIT_INT(alloc, player_t, 8);
    EXAMPLE_REQUIRE(proven_is_ok(r.err), "creating an int-keyed map must succeed");
    if (!proven_is_ok(r.err)) {
        return 1;
    }
    proven_map_t by_id = r.value;

    proven_err_t err = PROVEN_MAP_SET_INT(&by_id, 404, player_t, ((player_t){ .level = 3, .score = 990 }));
    EXAMPLE_REQUIRE(proven_is_ok(err), "inserting into the map must succeed");
    err = PROVEN_MAP_SET_INT(&by_id, 7, player_t, ((player_t){ .level = 1, .score = 10 }));
    EXAMPLE_REQUIRE(proven_is_ok(err), "inserting a second key must succeed");

    /* set on an existing key replaces the value; it does not add an entry. */
    err = PROVEN_MAP_SET_INT(&by_id, 7, player_t, ((player_t){ .level = 2, .score = 40 }));
    EXAMPLE_REQUIRE(proven_is_ok(err), "re-setting an existing key must succeed");
    EXAMPLE_REQUIRE(by_id.len == 2, "re-setting a key replaces its value rather than adding an entry");

    /* get returns a pointer into the bucket array, or NULL when absent. It is
     * invalidated by any insert that rehashes - look it up, use it, drop it. */
    const player_t *p = PROVEN_MAP_GET_INT(&by_id, player_t, 7);
    EXAMPLE_REQUIRE(p && p->level == 2 && p->score == 40, "get must see the replaced value");
    EXAMPLE_REQUIRE(PROVEN_MAP_GET_INT(&by_id, player_t, 999) == NULL, "a missing key yields NULL");

    err = PROVEN_MAP_REMOVE_INT(&by_id, 7);
    EXAMPLE_REQUIRE(proven_is_ok(err), "removing a present key must succeed");
    EXAMPLE_REQUIRE(PROVEN_MAP_GET_INT(&by_id, player_t, 7) == NULL, "a removed key is gone");
    EXAMPLE_REQUIRE(by_id.len == 1, "removal decrements the live entry count");

    PROVEN_MAP_DESTROY(&by_id);

    /* --- owned string keys --------------------------------------------------- */
    /* Same map, keyed by a name that we build at runtime - the case where a
     * borrowed key would be a dangling pointer waiting to happen. */
    proven_result_map_t rm = PROVEN_MAP_INIT_U8_OWNED(alloc, player_t, 8);
    EXAMPLE_REQUIRE(proven_is_ok(rm.err), "creating an owned-string-keyed map must succeed");
    if (!proven_is_ok(rm.err)) {
        return 1;
    }
    proven_map_t by_name = rm.value;

    /* A scratch buffer we intend to reuse for every key. With a BORROWED map
     * that plan is fatal: every entry would point at these same bytes. */
    proven_byte_t scratch[32];
    proven_u8str_t name = proven_u8str_borrow(scratch, sizeof scratch);

    err = proven_u8str_append(&name, PROVEN_LIT("ada"));
    EXAMPLE_REQUIRE(proven_is_ok(err), "building the first key must succeed");

    /* set_u8_owned COPIES the key bytes into map storage. After it returns, the
     * map's key no longer has anything to do with `scratch`. */
    err = PROVEN_MAP_SET_U8_OWNED(&by_name, proven_u8str_as_view(&name), player_t,
                                  ((player_t){ .level = 9, .score = 5000 }));
    EXAMPLE_REQUIRE(proven_is_ok(err), "inserting with an owned key must succeed");

    /* So the buffer is immediately free to be reused for the next key... */
    err = proven_u8str_reset(&name);
    EXAMPLE_REQUIRE(proven_is_ok(err), "the key buffer is ours again the moment set returns");
    err = proven_u8str_append(&name, PROVEN_LIT("grace"));
    EXAMPLE_REQUIRE(proven_is_ok(err), "overwriting the buffer with the next key must succeed");

    err = PROVEN_MAP_SET_U8_OWNED(&by_name, proven_u8str_as_view(&name), player_t,
                                  ((player_t){ .level = 4, .score = 700 }));
    EXAMPLE_REQUIRE(proven_is_ok(err), "inserting the second owned key must succeed");

    /* ...and the first entry is untouched by that overwrite. This is the whole
     * point: the map holds its own copy of "ada", not a view of a buffer that
     * now says "grace". A BORROWED map would report two entries both keyed
     * "grace" - or worse, one keyed by freed memory. */
    const player_t *ada = PROVEN_MAP_GET_U8_OWNED(&by_name, player_t, PROVEN_LIT("ada"));
    EXAMPLE_REQUIRE(ada && ada->score == 5000, "the copied key survives the caller reusing its buffer");

    const player_t *grace = PROVEN_MAP_GET_U8_OWNED(&by_name, player_t, PROVEN_LIT("grace"));
    EXAMPLE_REQUIRE(grace && grace->score == 700, "the second key is a separate entry");
    EXAMPLE_REQUIRE(by_name.len == 2, "two distinct keys means two entries");

    /* Remove frees the key copy the map made - you never free it yourself. */
    err = PROVEN_MAP_REMOVE_U8_OWNED(&by_name, PROVEN_LIT("ada"));
    EXAMPLE_REQUIRE(proven_is_ok(err), "removing an owned key must succeed");
    EXAMPLE_REQUIRE(PROVEN_MAP_GET_U8_OWNED(&by_name, player_t, PROVEN_LIT("ada")) == NULL,
                    "the removed entry is gone");

    printf("map: %zu name(s) left, grace at level %d\n",
           (size_t)by_name.len, grace ? grace->level : -1);

    /* destroy frees the bucket array AND every key copy still in it ("grace"
     * here). `scratch` is ours and outlives the map; the borrowed `name` handle
     * has nothing to free. */
    PROVEN_MAP_DESTROY(&by_name);
    proven_u8str_destroy(alloc, &name);
    return EXAMPLE_OK();
}

Worked example: sizing containers, searching unsorted data, and streaming a checksum#

The worked examples above take one container at a time. This one is the program those pieces end up inside — a small event intake — and it answers the questions that only come up once several containers are in play:

• Stop a container reallocating while it fills. proven_array_reserve() and proven_map_reserve() set the capacity once. On the heap that saves copying; behind an arena it saves the dead storage every reallocation leaves behind until the next reset. For a map it also matters for correctness of your pointers: a rehash invalidates every pointer a previous get_mut returned.
• Check a handle you did not create. proven_array_is_valid(), proven_ring_is_valid() and proven_map_is_valid() ask whether the handle's own fields are consistent — the check that catches a zero-initialised or never-created container at the boundary of your code, rather than at the first push.
• Search data that is not sorted. The event log is kept in arrival order, because that order is the thing being recorded, so binary search may not be used on it — on unsorted input it does not return "not found", it returns a wrong answer. proven_array_linear_search() is the correct call, and it returns the first match in order.
• Update a value already in a map, with one lookup. proven_map_get_mut() returns a pointer into the map's own storage, so a counter is incremented where it lives instead of being read, changed and written back.
• Decide which hash the keys deserve. proven_map_create() hashes string keys with keyed SipHash, so an attacker who chooses the keys cannot collide them all into one bucket. proven_map_create_trusted() uses fast FNV-1a and is right only when your own code chooses every key. proven_map_hash() returns the value the map actually places a key by, so the difference between the two is observable rather than a claim.
• Checksum data that arrives in pieces. proven_crc32_update() folds each chunk into a running value; the result equals proven_crc32() over the whole, whatever the chunk boundaries were.

/*
 * The container chapters show each structure on its own. A real program uses
 * several at once, and the questions that come up then are not about any single
 * container:
 *
 *   - How do I stop a container reallocating while it fills?  reserve.
 *   - How do I check a container somebody handed me is usable?  is_valid.
 *   - How do I search when the data is NOT sorted?  linear search - and knowing
 *     why binary search would give a wrong answer here.
 *   - How do I update a value already in a map without looking it up twice?
 *     get_mut.
 *   - Do I need the attack-resistant hash, or the fast one?  it depends on who
 *     chooses the keys, and map_hash lets you see the difference.
 *   - How do I checksum data that arrives in pieces?  crc32_update.
 *
 * The program is a small event intake: events arrive, are counted per client,
 * the most recent few are kept for a diagnostic dump, and the batch is
 * checksummed as it streams past.
 */

typedef struct {
    proven_u32 client;
    proven_u32 code;      /* an event code; 0 means "connection closed" */
} event_t;

/* Search by client id: this is the comparison for finding an event, not for
 * sorting them. The array below is in ARRIVAL order and stays that way. */
static int by_client(const void *a, const void *b) {
    const event_t *x = (const event_t *)a;
    const event_t *y = (const event_t *)b;
    return (x->client > y->client) - (x->client < y->client);
}

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

    /* --- 1. reserve: decide the capacity once ----------------------------- */

    proven_result_array_t ar = PROVEN_ARRAY_INIT(alloc, event_t, 4);
    EXAMPLE_REQUIRE(proven_is_ok(ar.err), "creating the event log must succeed");
    if (!proven_is_ok(ar.err)) {
        return 1;
    }
    proven_array_t events = ar.value;

    /* We know the batch size before we start, so ask for the room once. Without
     * this the array doubles as it fills, copying its contents each time; behind
     * an arena allocator each of those copies also leaves the old block behind
     * until the arena is reset. */
    proven_err_t err = proven_array_reserve(&events, 16);
    EXAMPLE_REQUIRE(proven_is_ok(err), "reserving room for the whole batch must succeed");
    EXAMPLE_REQUIRE(events.cap >= 16, "the capacity is now at least what was asked for");

    /* is_valid asks whether the handle itself is structurally sound - a pointer,
     * a length and a capacity that agree. Assert it where a container arrives
     * from other code, or after a zero-initialised handle might have escaped;
     * it is not something to repeat after every push. */
    EXAMPLE_REQUIRE(proven_array_is_valid(&events), "a created array must be structurally valid");

    proven_array_t never_created = {0};
    EXAMPLE_REQUIRE(!proven_array_is_valid(&never_created),
                    "a zero-initialised handle is not a usable array");

    static const event_t batch[] = {
        { .client = 7, .code = 200 }, { .client = 3, .code = 200 },
        { .client = 7, .code = 404 }, { .client = 9, .code = 200 },
        { .client = 3, .code = 500 }, { .client = 7, .code = 0   },
    };
    proven_size_t batch_len = sizeof batch / sizeof batch[0];

    proven_size_t cap_before = events.cap;
    for (proven_size_t i = 0; i < batch_len; ++i) {
        err = PROVEN_ARRAY_PUSH(&events, event_t, batch[i]);
        EXAMPLE_REQUIRE(proven_is_ok(err), "pushing an event must succeed");
    }
    EXAMPLE_REQUIRE(events.cap == cap_before, "the reserve was enough: nothing reallocated while filling");

    /* --- 2. searching data that is not sorted ----------------------------- */

    /* The log is in arrival order, which is the order we want to keep: it is the
     * thing being recorded. Binary search would be faster and WRONG here, since
     * it may only be used on a sorted range - on unsorted data it does not
     * return "not found", it returns nonsense. Linear search is the correct
     * tool, and O(n) over a batch this size is nothing. */
    event_t key = { .client = 9, .code = 0 };
    const event_t *found = (const event_t *)proven_array_linear_search(&events, &key, by_client);
    EXAMPLE_REQUIRE(found != NULL, "client 9 appears in the batch");
    EXAMPLE_REQUIRE(found->code == 200, "and linear search returns the FIRST match in order");

    event_t absent = { .client = 42, .code = 0 };
    EXAMPLE_REQUIRE(proven_array_linear_search(&events, &absent, by_client) == NULL,
                    "a client that never appeared is reported as not found");

    /* --- 3. a ring for the most recent events ----------------------------- */

    proven_result_ring_t rr = PROVEN_RING_INIT(alloc, event_t, 4);
    EXAMPLE_REQUIRE(proven_is_ok(rr.err), "creating the recent-events ring must succeed");
    proven_ring_t recent = rr.value;
    EXAMPLE_REQUIRE(proven_ring_is_valid(&recent), "a created ring must be structurally valid");

    proven_ring_t unset = {0};
    EXAMPLE_REQUIRE(!proven_ring_is_valid(&unset), "a zero-initialised ring handle is not usable");

    /* This ring refuses when full rather than overwriting, so "keep the most
     * recent four" means dropping the oldest ourselves before pushing. */
    for (proven_size_t i = 0; i < batch_len; ++i) {
        if (recent.len == recent.cap) {
            event_t dropped;
            err = PROVEN_RING_POP(&recent, event_t, &dropped);
            EXAMPLE_REQUIRE(proven_is_ok(err), "a full ring must yield its oldest element");
        }
        err = PROVEN_RING_PUSH(&recent, event_t, batch[i]);
        EXAMPLE_REQUIRE(proven_is_ok(err), "pushing after making room must succeed");
    }
    EXAMPLE_REQUIRE(recent.len == 4, "the ring holds the four most recent events");

    /* --- 4. counting per client, with one lookup per update --------------- */

    /* create_with_capacity is proven_map_create under a name that says why the
     * capacity argument is there: sizing it now avoids rehashing later, and a
     * rehash both copies every bucket and invalidates every pointer previously
     * returned by get_mut. */
    proven_result_map_t mr = proven_map_create_with_capacity(alloc, 8, PROVEN_KEY_TYPE_INT,
                                                            sizeof(proven_u32), alignof(proven_u32));
    EXAMPLE_REQUIRE(proven_is_ok(mr.err), "creating the counter map must succeed");
    proven_map_t counts = mr.value;
    EXAMPLE_REQUIRE(proven_map_is_valid(&counts), "a created map must be structurally valid");

    err = proven_map_reserve(&counts, 32);
    EXAMPLE_REQUIRE(proven_is_ok(err), "reserving map capacity must succeed");

    for (proven_size_t i = 0; i < batch_len; ++i) {
        proven_map_key_t k = { .id = batch[i].client };

        /* get_mut returns a pointer INTO the map's storage, so the counter is
         * incremented where it lives: one lookup, no copy back. The pointer is
         * good only until the next insert - which is another reason the capacity
         * was reserved above. */
        proven_u32 *seen = (proven_u32 *)proven_map_get_mut(&counts, k);
        if (seen) {
            *seen += 1;
        } else {
            proven_u32 one = 1;
            err = proven_map_set(&counts, k, &one);
            EXAMPLE_REQUIRE(proven_is_ok(err), "inserting a new client must succeed");
        }
    }

    const proven_u32 *seven = PROVEN_MAP_GET_INT(&counts, proven_u32, 7);
    EXAMPLE_REQUIRE(seven != NULL && *seven == 3, "client 7 sent three events");

    /* A closing event (code 0) means the client is gone: drop its counter. */
    for (proven_size_t i = 0; i < batch_len; ++i) {
        if (batch[i].code == 0) {
            err = proven_map_remove(&counts, (proven_map_key_t){ .id = batch[i].client });
            EXAMPLE_REQUIRE(proven_is_ok(err), "removing a present key must succeed");
        }
    }
    EXAMPLE_REQUIRE(PROVEN_MAP_GET_INT(&counts, proven_u32, 7) == NULL, "the closed client is gone");

    /* --- 5. which hash, and how to see the difference --------------------- */

    /* Two string-key maps over the same keys. The default one hashes with keyed
     * SipHash, so an attacker who chooses the keys cannot force them all into
     * one bucket. The trusted one uses fast FNV-1a and is the right choice ONLY
     * when your own code chooses every key. */
    proven_result_map_t untrusted = PROVEN_MAP_INIT_U8_BORROWED(alloc, proven_u32, 8);
    EXAMPLE_REQUIRE(proven_is_ok(untrusted.err), "creating the default string-key map must succeed");
    proven_map_t from_network = untrusted.value;

    proven_result_map_t tr = proven_map_create_trusted(alloc, 8, PROVEN_KEY_TYPE_U8_BORROWED,
                                                       sizeof(proven_u32), alignof(proven_u32));
    EXAMPLE_REQUIRE(proven_is_ok(tr.err), "creating the trusted-key map must succeed");
    proven_map_t internal = tr.value;

    EXAMPLE_REQUIRE(from_network.trusted_keys == false, "the default map defends against chosen keys");
    EXAMPLE_REQUIRE(internal.trusted_keys == true, "the trusted map opts out of that defence");

    /* map_hash exposes the value the map actually places a key by, so the
     * choice is observable rather than something you take on faith. */
    proven_map_key_t name = { .str = PROVEN_LIT("user-agent") };
    proven_u64 keyed = proven_map_hash(&from_network, name);
    proven_u64 fast  = proven_map_hash(&internal, name);
    EXAMPLE_REQUIRE(keyed != fast, "the same key hashes differently under the two functions");
    EXAMPLE_REQUIRE(proven_map_hash(&internal, name) == fast, "and each function is deterministic");

    /* Keys that live in memory the map does not own are BORROWED: the bytes must
     * outlive the map. These are string literals, so they do. When the key comes
     * from a buffer you are about to reuse, use an owned-key map instead
     * (PROVEN_MAP_INIT_U8_OWNED / proven_map_set_u8_owned), which copies. */
    proven_u32 hits = 1;
    err = proven_map_set(&from_network, name, &hits);
    EXAMPLE_REQUIRE(proven_is_ok(err), "inserting a borrowed string key must succeed");
    EXAMPLE_REQUIRE(PROVEN_MAP_GET_U8_BORROWED(&from_network, proven_u32, PROVEN_LIT("user-agent")) != NULL,
                    "and it can be looked up by an equal view, not the same pointer");

    /* --- 6. checksumming a stream in chunks ------------------------------- */

    /* The batch is checksummed as it goes past, which is what a program reading
     * a file or a socket has to do: it never holds the whole thing. Start the
     * running value at 0, feed each chunk in, and the final value is the same
     * one a single call over the concatenation would produce. */
    proven_u32 running = 0;
    for (proven_size_t i = 0; i < batch_len; ++i) {
        proven_mem_view_t chunk = { .ptr = (const proven_byte_t *)&batch[i], .size = sizeof batch[i] };
        running = proven_crc32_update(running, chunk);
    }
    proven_mem_view_t whole = { .ptr = (const proven_byte_t *)batch, .size = sizeof batch };
    EXAMPLE_REQUIRE(running == proven_crc32(whole),
                    "chunked and whole-buffer CRC-32 must agree, whatever the chunking");

    printf("events=%zu recent=%zu crc32=%08x\n",
           (size_t)events.len, (size_t)recent.len, (unsigned)running);

    proven_map_destroy(&internal);
    proven_map_destroy(&from_network);
    proven_map_destroy(&counts);
    PROVEN_RING_DESTROY(&recent);
    PROVEN_ARRAY_DESTROY(&events);
    return EXAMPLE_OK();
}

Wrong — binary search on the arrival-ordered log:

const event_t *e = proven_array_binary_search(&events, &key, by_client);   /* wrong */

proven_array_binary_search() may only be used on a range sorted by the same comparison. On unsorted input it does not fail; it halves its way to whatever element happens to be there and reports it, or reports nothing while the element is present two slots away.

Wrong — holding a get_mut pointer across an insert:

proven_u32 *seen = proven_map_get_mut(&counts, k);
proven_err_t e = proven_map_set(&counts, other_key, &one);   /* may rehash */
*seen += 1;                                                  /* wrong: may dangle */

Hold the key, not the pointer, across anything that can insert.

Wrong — the fast hash on keys from outside the program:

proven_result_map_t m = proven_map_create_trusted(alloc, 64, PROVEN_KEY_TYPE_U8_BORROWED,
                                                  sizeof(session_t), alignof(session_t));
/* keys are HTTP header names taken from the request */   /* wrong */

That is exactly the case the keyed hash defends against. Use proven_map_create() whenever the keys are chosen by anyone other than you.