10. Data Structures and Algorithms in C

C ships with arrays and nothing else — no vector, no map, no list — so every non-trivial C program either builds its containers or borrows someone's. That constraint is a gift for learning: you cannot use a hash table in C without understanding load factors and collision resolution, and you cannot write a linked list without confronting exactly who owns each allocation. This chapter builds the standard structures from raw memory, then covers the three techniques C offers for making them reusable across types.

<a id="101-linear-structures"></a>

10.1 Linear Structures

Linear structures store elements in a sequence and differ mainly in what is cheap: indexing, inserting at the ends, or inserting in the middle. This section builds each one from malloc and pointers, with attention to the growth strategies and ownership rules that decide whether the result is fast and leak-free or neither.

Dynamic Arrays

Theory

A C array has a size fixed when you write it. That is fine when you know the count in advance and useless when you do not — reading an unknown number of lines, collecting search results, accumulating events. The dynamic array (the same idea as C++'s vector, Python's list, or Java's ArrayList) solves this by separating two quantities that a fixed array conflates:

• length — how many elements are actually stored
• capacity — how many the current allocation could hold

Appending is then trivial while length < capacity: write at data[length] and increment. When they meet, allocate a bigger block, copy everything across, free the old one, and continue. realloc does all three steps for you and may skip the copy entirely if the heap can extend the block in place.

The critical design decision is how much bigger. It is tempting to grow by one element each time, or by a fixed 10. Both are quadratic disasters. Growing by a constant k means appending n elements performs roughly n²/(2k) element copies — for a million appends that is billions of copies, and the profile shows all the time inside memcpy.

The fix is geometric growth: multiply the capacity by a constant factor, typically 2 or 1.5. Now the copies form a geometric series that sums to less than 2n total, so the amortized cost of an append is O(1) — most appends are a single write, and the occasional expensive resize is paid for by all the cheap appends before it.

   GROWTH BY +1 (quadratic)          GROWTH BY x2 (amortized O(1))

   append 1 -> copy 0                append 1 -> copy 0    cap 1
   append 2 -> copy 1                append 2 -> copy 1    cap 2
   append 3 -> copy 2                append 3 -> copy 2    cap 4
   append 4 -> copy 3                append 4 -> copy 0
   ...                               append 5 -> copy 4    cap 8
   append n -> copy n-1              append 6,7,8 -> copy 0
   ------------------------          ---------------------------
   total ~ n^2/2 copies              total < 2n copies

Factor 2 is the common default. A factor of 1.5 wastes less memory and, on some allocators, lets a freed block be reused by a later growth; the difference rarely matters outside allocation-heavy code.

Three implementation details separate a correct dynamic array from a broken one:

Never assign realloc's result directly to the pointer you passed in. If realloc fails it returns NULL while leaving the original block allocated — so v->data = realloc(v->data, n) on failure both loses your data and leaks it. Always use a temporary.

Pointers into the array are invalidated by growth. After a resize the elements may live at a completely different address. Any pointer or saved &v->data[i] from before the append is dangling. This is why dynamic-array APIs return indices rather than pointers, and why "get a pointer, then append, then use the pointer" is a classic use-after-free.

Removal from the middle is O(n) because everything after the hole must shift down. When order does not matter, swap_remove — move the last element into the hole and shrink — makes it O(1).

The trade-off against a linked list is the whole point: dynamic arrays give you O(1) indexing and contiguous memory that the CPU cache loves, at the cost of O(n) middle insertion and periodic reallocation.

Examples

#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <stdint.h>   /* SIZE_MAX */

typedef struct {
    int    *data;
    size_t  len;      /* elements in use          */
    size_t  cap;      /* elements the block holds */
} IntVec;

static void vec_init(IntVec *v) { v->data = NULL; v->len = v->cap = 0; }

static void vec_free(IntVec *v)
{
    free(v->data);
    v->data = NULL;                  /* leave the struct in a safe state */
    v->len = v->cap = 0;
}

/* Ensure room for at least 'want' elements. Returns 0 on success. */
static int vec_reserve(IntVec *v, size_t want)
{
    if (want <= v->cap) return 0;

    size_t cap = v->cap ? v->cap : 4;        /* small non-zero start */
    while (cap < want) {
        if (cap > SIZE_MAX / 2) return -1;   /* guard the doubling itself */
        cap *= 2;                            /* GEOMETRIC growth */
    }

    /* Overflow check before computing the byte size. */
    if (cap > SIZE_MAX / sizeof *v->data) return -1;

    /* Assign to a TEMPORARY: realloc returns NULL on failure and leaves
       the old block valid. Writing straight to v->data would leak it. */
    int *tmp = realloc(v->data, cap * sizeof *v->data);
    if (!tmp) return -1;

    v->data = tmp;
    v->cap  = cap;
    return 0;
}

static int vec_push(IntVec *v, int value)
{
    if (v->len == v->cap && vec_reserve(v, v->len + 1) != 0)
        return -1;
    v->data[v->len++] = value;
    return 0;
}

static int vec_pop(IntVec *v, int *out)
{
    if (v->len == 0) return -1;
    *out = v->data[--v->len];
    return 0;
}

/* O(n): everything after the hole shifts down. Order is preserved. */
static int vec_remove(IntVec *v, size_t i)
{
    if (i >= v->len) return -1;
    memmove(&v->data[i], &v->data[i + 1],
            (v->len - i - 1) * sizeof *v->data);   /* memmove: regions overlap */
    v->len--;
    return 0;
}

/* O(1): the last element fills the hole. Order is NOT preserved. */
static int vec_swap_remove(IntVec *v, size_t i)
{
    if (i >= v->len) return -1;
    v->data[i] = v->data[--v->len];
    return 0;
}

int main(void)
{
    IntVec v;
    vec_init(&v);

    for (int i = 0; i < 10; i++)
        if (vec_push(&v, i * i) != 0) { vec_free(&v); return 1; }

    printf("len=%zu cap=%zu\n", v.len, v.cap);       /* len=10 cap=16 */

    vec_remove(&v, 0);                                /* drop the first */
    vec_swap_remove(&v, 0);                           /* last fills the hole */

    for (size_t i = 0; i < v.len; i++) printf("%d ", v.data[i]);
    putchar('\n');

    int top;
    if (vec_pop(&v, &top) == 0) printf("popped %d\n", top);

    vec_free(&v);
    return 0;
}

The invalidation trap, which every dynamic-array user meets once:

#include <stdio.h>
#include <stdlib.h>

int main(void)
{
    int   *data = malloc(2 * sizeof *data);
    if (!data) return 1;
    size_t cap = 2, len = 0;

    data[len++] = 10;
    int *p = &data[0];          /* a pointer INTO the array */
    printf("before: *p = %d\n", *p);   /* valid -- for now */

    /* Growing may move the whole block to a new address. */
    int *tmp = realloc(data, (cap = 8) * sizeof *data);
    if (!tmp) { free(data); return 1; }
    data = tmp;

    /* *p is now a USE-AFTER-FREE if the block moved. Store the INDEX
       (0) instead of the pointer, and re-derive &data[0] after growing. */
    printf("safe: %d\n", data[0]);

    free(data);
    return 0;
}

Operation	Dynamic array	Linked list
Index i	O(1)	O(n)
Append at end	O(1) amortized	O(1) with a tail pointer
Insert/remove at front	O(n)	O(1)
Insert/remove in middle (position known)	O(n)	O(1) given the node
Memory per element	the element	element + pointer(s)
Cache behavior	contiguous, excellent	scattered, poor
Pointer stability across insertion	none	full

Key Takeaways

• A dynamic array separates length from capacity; appending is a write until they meet, then a reallocation.
• Grow geometrically (typically doubling) — growing by a constant makes n appends cost O(n²) in copies instead of amortized O(1).
• Always assign realloc's result to a temporary: on failure it returns NULL and the original block is still allocated and still yours to free.
• Any pointer into the array is invalidated by a growth; store indices instead, and re-derive pointers after every append.
• Removal is O(n) if order matters and O(1) with swap_remove if it does not.

🧪 Practice

1. Instrument vec_reserve to count reallocations and total elements copied, then push 100,000 items with doubling and with +1 growth. Compare the counts.
2. Add vec_insert(IntVec *v, size_t i, int value) that shifts elements up, and vec_shrink_to_fit that releases unused capacity.
3. Write a version that stores char * strings and takes ownership of them, ensuring vec_free releases every string as well as the array.
4. Interview-style: "Why do dynamic arrays double their capacity instead of growing by a fixed amount?" Hint: sum the total number of element copies over n appends under each strategy.

Singly and Doubly Linked Lists

Theory

A linked list stores each element in its own allocation — a node — that carries the value plus a pointer to the next node. The list itself is just a pointer to the first node; the last node's next is NULL, which marks the end.

The trade against an array is exact and worth stating plainly. An array gives you a position instantly (data[i] is one multiply and one add) but has to move elements to make room. A list can insert or remove anywhere in O(1) provided you already hold a pointer to the right node, but reaching node i means following i pointers. There is no way to jump.

That last caveat is where most people over-estimate linked lists. "O(1) insertion" is true, but finding where to insert is usually O(n), so the total is O(n) anyway. Lists genuinely win when you already hold the node: an LRU cache moving an entry to the front, a scheduler removing the task it is currently examining, a memory allocator splicing a block out of a free list.

They also have a cost that Big-O hides: every node is a separate allocation in a separate place in memory. Traversing a list is a chain of dependent loads, each a potential cache miss, and the CPU cannot prefetch because it does not know the next address until the current load completes. Iterating a million-element array is often 10–50x faster than iterating a million-element list holding the same data. Modern practice is to reach for a dynamic array first and a list only when its specific properties are needed.

Singly linked lists have one pointer per node and can only be walked forwards. Removing a node requires a pointer to its predecessor, because that is what must be updated — which is why the naive list_remove(node) cannot be written for a singly linked list.

Doubly linked lists add a prev pointer. That buys backward traversal and true O(1) removal given only the node, at the cost of an extra pointer per node and two updates instead of one on every operation.

Two techniques eliminate most linked-list bugs:

The pointer-to-pointer idiom. Insertion and deletion have a special case at the head, because there the thing to update is the list's own head pointer rather than some node's next. Instead of writing that special case, walk a Node ** — a pointer to the pointer that points at the current node. It starts as &head and becomes &current->next, so the head is no longer special and the code has one branch instead of three.

The sentinel (dummy head) node. Allocate one permanent node that is never a real element. Now the list is never empty from the code's perspective, and every insertion and removal has a predecessor. A circular doubly linked list with a sentinel — the form used by the Linux kernel — makes every operation completely branch-free.

Examples

#include <stdio.h>
#include <stdlib.h>

/* ---------------- singly linked list ---------------- */
typedef struct Node {
    int          value;
    struct Node *next;      /* NULL marks the end */
} Node;

static Node *node_new(int value, Node *next)
{
    Node *n = malloc(sizeof *n);
    if (!n) return NULL;
    n->value = value;
    n->next  = next;
    return n;
}

/* Push at the front: O(1), the natural operation for a singly linked list. */
static int list_push_front(Node **head, int value)
{
    Node *n = node_new(value, *head);
    if (!n) return -1;
    *head = n;
    return 0;
}

/* Remove the first node holding 'value'.
   The pointer-to-pointer walk removes the head special case entirely:
   'link' always points AT the pointer that must be updated. */
static int list_remove(Node **head, int value)
{
    for (Node **link = head; *link; link = &(*link)->next) {
        if ((*link)->value == value) {
            Node *dead = *link;
            *link = dead->next;      /* works whether *link is head or a ->next */
            free(dead);
            return 0;
        }
    }
    return -1;
}

/* Reverse in place: the classic three-pointer walk. */
static Node *list_reverse(Node *head)
{
    Node *prev = NULL;
    while (head) {
        Node *next = head->next;    /* save it before we overwrite the link */
        head->next = prev;          /* flip the arrow backwards */
        prev = head;                /* advance both cursors */
        head = next;
    }
    return prev;                    /* the old tail is the new head */
}

static void list_free(Node *head)
{
    while (head) {
        Node *next = head->next;    /* read BEFORE freeing -- not after */
        free(head);
        head = next;
    }
}

static void list_print(const Node *head)
{
    for (const Node *n = head; n; n = n->next) printf("%d -> ", n->value);
    puts("NULL");
}

int main(void)
{
    Node *head = NULL;
    for (int i = 1; i <= 5; i++) list_push_front(&head, i);

    list_print(head);                /* 5 -> 4 -> 3 -> 2 -> 1 -> NULL */
    list_remove(&head, 5);           /* removing the HEAD, no special case */
    list_remove(&head, 1);           /* removing the TAIL */
    list_print(head);                /* 4 -> 3 -> 2 -> NULL */

    head = list_reverse(head);
    list_print(head);                /* 2 -> 3 -> 4 -> NULL */

    list_free(head);
    return 0;
}

A circular doubly linked list with a sentinel — every operation is branch-free:

#include <stdio.h>
#include <stdlib.h>

typedef struct DNode {
    int           value;
    struct DNode *prev, *next;
} DNode;

/* The sentinel is a real node that holds no value. An empty list is the
   sentinel pointing at itself, so 'next' and 'prev' are NEVER NULL. */
static void dlist_init(DNode *sentinel)
{
    sentinel->next = sentinel->prev = sentinel;
}

/* Splice 'n' in before 'at'. With a sentinel, at == sentinel means
   "append at the end" -- and it needs no special case. */
static void dlist_insert_before(DNode *at, DNode *n)
{
    n->prev        = at->prev;
    n->next        = at;
    at->prev->next = n;          /* four pointer writes, no branches */
    at->prev       = n;
}

/* Unlink 'n'. O(1) given only the node -- impossible in a singly linked list. */
static void dlist_remove(DNode *n)
{
    n->prev->next = n->next;
    n->next->prev = n->prev;
    n->prev = n->next = n;       /* self-link: safe to remove twice */
}

int main(void)
{
    DNode sentinel;
    dlist_init(&sentinel);

    DNode *saved = NULL;
    for (int i = 1; i <= 5; i++) {
        DNode *n = malloc(sizeof *n);
        if (!n) break;
        n->value = i;
        dlist_insert_before(&sentinel, n);       /* append */
        if (i == 3) saved = n;
    }

    /* Forward, then backward -- the sentinel bounds both directions. */
    for (DNode *p = sentinel.next; p != &sentinel; p = p->next) printf("%d ", p->value);
    putchar('\n');
    for (DNode *p = sentinel.prev; p != &sentinel; p = p->prev) printf("%d ", p->value);
    putchar('\n');

    dlist_remove(saved);                          /* O(1), node only */
    free(saved);

    /* Free the rest: capture 'next' before freeing the current node. */
    for (DNode *p = sentinel.next, *next; p != &sentinel; p = next) {
        next = p->next;
        free(p);
    }
    return 0;
}

   THE POINTER-TO-POINTER WALK

   head
    |
    v
   +-----+    +-----+    +-----+
   |  5  |--->|  4  |--->|  3  |---> NULL
   +-----+    +-----+    +-----+

   link = &head          *link is the head pointer
   link = &node5->next   *link is node5's next field
   link = &node4->next   ...

   Deleting is ALWAYS  *link = (*link)->next  -- one line, no special
   case for the head, because 'link' names the pointer that must change.

   Without it you need:  if (target == head) head = head->next;
                         else pred->next = target->next;
   ...plus tracking 'pred' through the whole loop.

	Singly linked	Doubly linked
Pointers per node	1	2
Traverse backwards	no	yes
Remove given only the node	no (need the predecessor)	yes, O(1)
Memory overhead	lower	one extra pointer per node
Writes per insertion	2	4
Typical use	stacks, free lists, hash buckets	LRU caches, schedulers, kernel lists

Key Takeaways

• A linked list trades O(1) indexing for O(1) splicing, but only when you already hold the node — finding it is still O(n).
• Every node is a separate allocation, so traversal is a chain of dependent, unpredictable loads; arrays are far more cache-friendly for the same data.
• The Node ** pointer-to-pointer walk removes the head special case from insertion and deletion, collapsing three branches into one line.
• A sentinel node in a circular doubly linked list makes next and prev never NULL, so every operation is branch-free.
• When freeing or removing, read the next pointer before freeing the node — reading it afterwards is a use-after-free.

🧪 Practice

1. Implement list_append, list_length, and list_find for the singly linked list, then rewrite list_append using the Node ** idiom and compare the two.
2. Detect a cycle in a singly linked list with Floyd's tortoise-and-hare algorithm, using O(1) extra space.
3. Write list_middle that returns the middle node in a single pass, without first computing the length.
4. Interview-style: "You are given a pointer to a node in a singly linked list, but not the head. Can you delete it?" Hint: you cannot change the predecessor, but you can change what the given node contains.

Stacks

Theory

A stack is a container with exactly one rule: the last thing you put in is the first thing you get out. Push adds to the top, pop removes from the top, and there is no way to reach anything underneath. This is LIFO — last in, first out.

The restriction sounds limiting and is exactly the point. A stack is the right structure whenever you need to remember where you came from so you can return to it in reverse order:

• Function calls. The call stack is literally this structure; each call pushes a frame, each return pops one. Recursion is a stack you get for free.
• Undo. Each action pushes its inverse; undo pops and applies it.
• Matching delimiters. Push each opening bracket; on a closing bracket, pop and check it matches.
• Backtracking. Depth-first search pushes the frontier and pops to retreat.
• Expression evaluation. Postfix evaluation pushes operands and pops pairs for each operator.

Any structure with cheap insert-and-remove at one end implements a stack. In C there are two natural choices:

Array-based uses a dynamic array and pushes/pops at the end (never the front — that would be O(n) shifting). It is the default choice: no per-element allocation, contiguous memory, and the top element is almost always in cache.

List-based pushes at the front of a singly linked list. Every operation is genuinely O(1) with no amortization, and it never needs to copy, but it costs a malloc per element and scatters the data.

The classic bug is failing to check for underflow: popping an empty stack reads data[-1], which is out of bounds. Because C does not check, this usually returns garbage rather than crashing, and the wrong value propagates. Give pop a status return and a separate out-parameter, exactly as with the dynamic array.

A note on the hardware stack: it is finite (typically 1–8 MB) and it is where recursion lives. Deep recursion overflows it, and stack overflow in C is not an exception — it is a segmentation fault or, worse, silent corruption. Converting a recursive algorithm to an explicit heap-allocated stack is the standard fix, and it is why the iterative forms of tree and graph traversals matter.

Examples

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

/* ---------------- array-backed stack: the default choice ------------- */
typedef struct {
    char   *data;
    size_t  len, cap;
} CharStack;

static void  cs_init(CharStack *s) { s->data = NULL; s->len = s->cap = 0; }
static void  cs_free(CharStack *s) { free(s->data); cs_init(s); }
static bool  cs_empty(const CharStack *s) { return s->len == 0; }

static int cs_push(CharStack *s, char c)
{
    if (s->len == s->cap) {
        size_t cap = s->cap ? s->cap * 2 : 8;
        char  *tmp = realloc(s->data, cap);      /* temporary, never s->data */
        if (!tmp) return -1;
        s->data = tmp;
        s->cap  = cap;
    }
    s->data[s->len++] = c;
    return 0;
}

/* Status return plus out-parameter: underflow is reported, not guessed. */
static int cs_pop(CharStack *s, char *out)
{
    if (s->len == 0) return -1;                  /* the check that matters */
    *out = s->data[--s->len];
    return 0;
}

static int cs_peek(const CharStack *s, char *out)
{
    if (s->len == 0) return -1;
    *out = s->data[s->len - 1];                  /* look without removing */
    return 0;
}

/* The canonical stack problem: are all brackets balanced and correctly nested? */
static bool balanced(const char *s)
{
    CharStack st;
    cs_init(&st);
    bool ok = true;

    for (; *s && ok; s++) {
        switch (*s) {
        case '(': case '[': case '{':
            if (cs_push(&st, *s) != 0) { ok = false; }
            break;
        case ')': case ']': case '}': {
            char open;
            if (cs_pop(&st, &open) != 0) { ok = false; break; }  /* too many closers */
            /* The matching opener must be the MOST RECENT one -- that is
               exactly what LIFO guarantees. */
            if ((*s == ')' && open != '(') ||
                (*s == ']' && open != '[') ||
                (*s == '}' && open != '{')) ok = false;
            break;
        }
        default: break;
        }
    }

    if (!cs_empty(&st)) ok = false;              /* unclosed openers remain */
    cs_free(&st);
    return ok;
}

int main(void)
{
    const char *tests[] = { "({[]})", "(]", "((", "a(b)[c]{d}", ")(" };
    for (size_t i = 0; i < sizeof tests / sizeof *tests; i++)
        printf("%-12s %s\n", tests[i], balanced(tests[i]) ? "balanced" : "NOT balanced");
    return 0;
}

Postfix evaluation, and a list-backed stack for comparison:

#include <stdio.h>
#include <stdlib.h>

/* ---------------- list-backed stack: O(1) worst case, malloc per push -- */
typedef struct SNode { int value; struct SNode *next; } SNode;

static int  s_push(SNode **top, int v)
{
    SNode *n = malloc(sizeof *n);
    if (!n) return -1;
    n->value = v; n->next = *top; *top = n;      /* push at the FRONT */
    return 0;
}

static int s_pop(SNode **top, int *out)
{
    if (!*top) return -1;
    SNode *n = *top;
    *out = n->value; *top = n->next;
    free(n);
    return 0;
}

/* Evaluate a postfix expression: operands push, operators pop two. */
static int eval_postfix(const char *expr, int *result)
{
    SNode *st = NULL;
    int status = -1;

    for (const char *p = expr; *p; p++) {
        if (*p == ' ') continue;

        if (*p >= '0' && *p <= '9') {
            if (s_push(&st, *p - '0') != 0) goto done;
            continue;
        }

        int b, a;
        /* Pop order matters: the SECOND operand comes off first. */
        if (s_pop(&st, &b) != 0 || s_pop(&st, &a) != 0) goto done;

        int r;
        switch (*p) {
        case '+': r = a + b; break;
        case '-': r = a - b; break;
        case '*': r = a * b; break;
        case '/': if (b == 0) goto done; r = a / b; break;
        default:  goto done;
        }
        if (s_push(&st, r) != 0) goto done;
    }

    /* A well-formed expression leaves exactly one value. */
    if (s_pop(&st, result) == 0 && st == NULL) status = 0;

done:
    { int junk; while (s_pop(&st, &junk) == 0) ; }   /* drain and free */
    return status;
}

int main(void)
{
    const char *e = "3 4 + 2 *";      /* (3+4)*2 */
    int r;
    printf("%s = %s", e, eval_postfix(e, &r) == 0 ? "" : "error\n");
    if (r) printf("%d\n", r);         /* 14 */
    return 0;
}

   EVALUATING  "3 4 + 2 *"

   token   action              stack (top on the right)
   -----   ------------------  ------------------------
     3     push 3              3
     4     push 4              3 4
     +     pop 4, pop 3        (empty)
           push 3+4            7
     2     push 2              7 2
     *     pop 2, pop 7        (empty)
           push 7*2            14
   -----   ------------------  ------------------------
   end     exactly one value left -> the result is 14

   Note the pop order: the FIRST pop is the RIGHT operand.
   Getting it backwards makes '-' and '/' silently wrong.

	Array-backed	List-backed
Push / pop	O(1) amortized	O(1) worst case
Allocation	one block, grown occasionally	one malloc per element
Memory per element	the element	element + pointer + heap overhead
Cache behavior	excellent	poor
Pointer stability	none (resize moves data)	full
Default choice	yes	when worst-case O(1) is required

Key Takeaways

• A stack is LIFO with exactly three operations — push, pop, peek — and the restriction is what makes it useful for remembering where you came from.
• Implement it over a dynamic array pushing at the end; pushing at the front of an array is O(n) and defeats the purpose.
• Always report underflow through a status return with an out-parameter; popping an empty stack silently reads out of bounds.
• Delimiter matching, undo, postfix evaluation, and DFS are all the same structure — each needs the most recent unfinished item first.
• Recursion uses the fixed-size hardware stack; converting to an explicit heap stack is the standard cure for stack overflow on deep inputs.

🧪 Practice

1. Extend balanced to report the index of the first mismatched bracket rather than just a boolean.
2. Implement a stack with a min() operation that returns the smallest element currently held, in O(1) time. Hint: one stack may not be enough.
3. Convert a recursive factorial or Fibonacci function into an iterative one using an explicit stack, and compare the maximum input each version survives.
4. Interview-style: "How would you implement a queue using only two stacks?" Hint: reversing a stack into another stack reverses the order, and reversing twice restores it.

Queues and Circular Buffers

Theory

A queue is a stack's mirror image: first in, first out. Items are added at the tail and removed from the head, so they come out in the order they arrived. That is the right model whenever fairness or arrival order matters — print jobs, network packets, work items handed between threads, and the frontier in breadth-first search.

The naive array implementation is a trap. Storing the head at index 0 and shifting everything down on each dequeue makes dequeue O(n), so draining n items costs O(n²). Keeping a moving head index avoids the shifting but leaks space: after n enqueues and n dequeues the head has crawled to the end of the array and the reclaimed space at the front is unusable.

The circular buffer (or ring buffer) fixes both. Keep head and tail indices and let them wrap around to 0 when they pass the end. The array becomes a ring with no beginning; the used region is the span from head to tail, which may wrap through the end of the array. Enqueue and dequeue are both O(1), and no space is ever stranded.

   capacity 8, head=6, tail=2  -- the data WRAPS through the end

   index:   0    1    2    3    4    5    6    7
          +----+----+----+----+----+----+----+----+
          | 30 | 40 |    |    |    |    | 10 | 20 |
          +----+----+----+----+----+----+----+----+
            ^         ^                   ^
            |         tail (next write)    head (next read)
            |
            the ring continues here:  6 -> 7 -> 0 -> 1 -> 2

   logical order: 10, 20, 30, 40

Wrapping is one operation: index = (index + 1) % capacity. When the capacity is a power of two you can use index = (index + 1) & (capacity - 1), which is a single AND instead of a division — the reason nearly every production ring buffer has a power-of-two capacity.

There is one genuine design puzzle. With only head and tail, the empty condition (head == tail) and the full condition (head == tail) are indistinguishable — the ring has capacity distinct states to express but capacity + 1 possible fill levels. Three standard resolutions:

Approach	How	Cost
Keep a count field	store the number of items explicitly	one extra field, updated on every operation
Waste one slot	full means (tail + 1) % cap == head	one slot of capacity
Use free-running counters	never wrap the indices; mask only when indexing	needs unsigned wrap-around reasoning

Keeping a count is the clearest and is what most code should do. The free-running-counter form matters in lock-free single-producer/single-consumer queues, where having only one writer per variable is what makes the structure safe without locks.

A deque (double-ended queue) generalizes this by also allowing insertion at the head and removal from the tail — the same ring, with head decrementing as well as tail incrementing.

Examples

#include <stdio.h>
#include <stdlib.h>
#include <stdbool.h>

/* A fixed-capacity ring buffer. Capacity is a power of two so the
   wrap is a bitwise AND rather than a modulo. */
typedef struct {
    int    *data;
    size_t  cap;        /* power of two          */
    size_t  mask;       /* cap - 1               */
    size_t  head;       /* index of the next read  */
    size_t  tail;       /* index of the next write */
    size_t  count;      /* items held -- resolves the full/empty ambiguity */
} Ring;

static int ring_init(Ring *r, size_t cap_pow2)
{
    if (cap_pow2 == 0 || (cap_pow2 & (cap_pow2 - 1)) != 0)
        return -1;                              /* must be a power of two */
    r->data = malloc(cap_pow2 * sizeof *r->data);
    if (!r->data) return -1;
    r->cap = cap_pow2;
    r->mask = cap_pow2 - 1;
    r->head = r->tail = r->count = 0;
    return 0;
}

static void ring_free(Ring *r) { free(r->data); r->data = NULL; }

static bool ring_empty(const Ring *r) { return r->count == 0; }
static bool ring_full (const Ring *r) { return r->count == r->cap; }

static int ring_push(Ring *r, int value)
{
    if (ring_full(r)) return -1;
    r->data[r->tail] = value;
    r->tail = (r->tail + 1) & r->mask;          /* wrap: cheaper than % */
    r->count++;
    return 0;
}

static int ring_pop(Ring *r, int *out)
{
    if (ring_empty(r)) return -1;
    *out = r->data[r->head];
    r->head = (r->head + 1) & r->mask;
    r->count--;
    return 0;
}

/* Overwrite mode: used for fixed-size history and telemetry buffers,
   where the newest data matters more than the oldest. */
static void ring_push_overwrite(Ring *r, int value)
{
    if (ring_full(r)) {
        r->head = (r->head + 1) & r->mask;      /* drop the oldest */
        r->count--;
    }
    ring_push(r, value);
}

static void ring_print(const Ring *r)
{
    printf("[");
    /* Iterate LOGICALLY from head, applying the mask -- never 0..count. */
    for (size_t i = 0; i < r->count; i++)
        printf("%d%s", r->data[(r->head + i) & r->mask], i + 1 < r->count ? " " : "");
    printf("] head=%zu tail=%zu count=%zu\n", r->head, r->tail, r->count);
}

int main(void)
{
    Ring r;
    if (ring_init(&r, 8) != 0) return 1;

    for (int i = 1; i <= 6; i++) ring_push(&r, i * 10);
    ring_print(&r);                       /* [10 20 30 40 50 60] */

    int v;
    ring_pop(&r, &v); ring_pop(&r, &v);   /* drain two from the head */
    ring_print(&r);                       /* [30 40 50 60] head=2 */

    /* Push past the end of the array so the data wraps around. */
    for (int i = 7; i <= 10; i++) ring_push(&r, i * 10);
    ring_print(&r);                       /* wrapped, but the order is right */

    printf("full: %s\n", ring_full(&r) ? "yes" : "no");
    ring_push_overwrite(&r, 999);         /* evicts the oldest */
    ring_print(&r);

    ring_free(&r);
    return 0;
}

A growable queue built on a linked list, for when the bound is unknown:

#include <stdio.h>
#include <stdlib.h>

/* Head and tail pointers make both ends O(1). A singly linked list is
   enough: we only ever remove from the head. */
typedef struct QNode { int value; struct QNode *next; } QNode;
typedef struct { QNode *head, *tail; size_t count; } Queue;

static void q_init(Queue *q) { q->head = q->tail = NULL; q->count = 0; }

static int q_push(Queue *q, int value)
{
    QNode *n = malloc(sizeof *n);
    if (!n) return -1;
    n->value = value; n->next = NULL;

    if (q->tail) q->tail->next = n;      /* link the old tail forwards */
    else         q->head = n;            /* the list was empty */
    q->tail = n;                         /* the new node is always the tail */
    q->count++;
    return 0;
}

static int q_pop(Queue *q, int *out)
{
    if (!q->head) return -1;
    QNode *n = q->head;
    *out = n->value;
    q->head = n->next;
    if (!q->head) q->tail = NULL;        /* CRITICAL: clear a stale tail */
    free(n);
    q->count--;
    return 0;
}

int main(void)
{
    Queue q; q_init(&q);
    for (int i = 1; i <= 3; i++) q_push(&q, i);

    int v;
    while (q_pop(&q, &v) == 0) printf("%d ", v);   /* 1 2 3 -- FIFO */
    putchar('\n');
    return 0;
}

	Circular buffer	Linked-list queue
Capacity	fixed (or grown by reallocation)	unbounded
Allocation	one block up front	one per element
Enqueue / dequeue	O(1)	O(1)
Cache behavior	excellent	poor
Back-pressure	natural — "full" is a real state	none until memory runs out
Typical use	audio, telemetry, producer/consumer	task queues of unknown size

Key Takeaways

• A queue is FIFO: enqueue at the tail, dequeue from the head, preserving arrival order.
• Never implement a queue by shifting an array down on dequeue — that makes draining n items O(n²); use a circular buffer instead.
• Wrapping with (i + 1) & (cap - 1) requires a power-of-two capacity and replaces a division with a single AND.
• head == tail cannot distinguish full from empty on its own — keep a count, waste one slot, or use free-running counters.
• In a linked-list queue, always clear tail when the last element is removed, or the stale pointer corrupts the next enqueue.

🧪 Practice

1. Add ring_peek and ring_clear, then write a test that pushes and pops 10,000 times through an 8-slot ring and verifies FIFO order throughout.
2. Implement a growable ring buffer that doubles its capacity when full — note that you cannot simply realloc, because the wrapped data must be unwound.
3. Build a deque on a ring buffer with push_front, push_back, pop_front, and pop_back, being careful with the head decrement at index 0.
4. Interview-style: "Why can't a ring buffer distinguish full from empty using only head and tail?" Hint: count the distinct index pairs versus the number of fill levels you must represent.

String Builders

Theory

Building a string by repeated concatenation is the most common accidental O(n²) in C. Consider appending n pieces with strcat:

for (int i = 0; i < n; i++)
    strcat(buffer, pieces[i]);      /* looks linear, is quadratic */

strcat must first find the end of buffer by walking it from the start. On iteration i the buffer already holds roughly i pieces, so that walk is O(i), and the total is O(n²). This is sometimes called Shlemiel the painter's algorithm — each day he walks further back to the paint can. For 10,000 appends the difference against a linear approach is thousands of times.

A string builder fixes it with the same insight as the dynamic array: track the current length so you never rescan, and grow geometrically so reallocation is amortized away. Appending becomes "copy the new bytes at the remembered offset, advance the offset" — O(k) in the length of the piece, not the length of the result.

The structure is a dynamic array of char with two refinements:

• Always keep a NUL terminator so the buffer is a valid C string at every moment. Store len as the count of real characters, excluding the terminator, and reserve len + 1 bytes.
• Support formatted appends. snprintf returns the length it would have written, which gives a clean two-step: ask for the size, reserve it, then write for real. That handles arbitrary formats without guessing.

Two API decisions matter for the caller:

Who owns the result? Either the builder hands ownership to the caller on "finish" (the caller frees it, the builder is reset), or the builder keeps ownership and returns a const char * valid until the next append. Both are fine; silence about which is not, and mixed conventions cause double frees.

Pointers into the buffer are invalidated by every append, for the same reason as the dynamic array. A const char * obtained before an append may dangle after it.

A related technique worth knowing is snprintf size probing: calling snprintf(NULL, 0, fmt, ...) returns the exact length the formatted output needs, so you can allocate precisely once. This is how to format a single unknown-length string without a builder at all.

Examples

#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <stdarg.h>
#include <stdint.h>    /* SIZE_MAX */

typedef struct {
    char   *data;      /* always NUL-terminated when data != NULL */
    size_t  len;       /* characters, EXCLUDING the terminator    */
    size_t  cap;       /* bytes allocated, INCLUDING room for it  */
} StrBuf;

static void sb_init(StrBuf *b) { b->data = NULL; b->len = 0; b->cap = 0; }
static void sb_free(StrBuf *b) { free(b->data); sb_init(b); }

/* Ensure room for 'extra' more characters plus the terminator. */
static int sb_reserve(StrBuf *b, size_t extra)
{
    if (extra > SIZE_MAX - b->len - 1) return -1;      /* size overflow */
    size_t need = b->len + extra + 1;
    if (need <= b->cap) return 0;

    size_t cap = b->cap ? b->cap : 16;
    while (cap < need) {
        if (cap > SIZE_MAX / 2) return -1;
        cap *= 2;                                       /* geometric growth */
    }

    char *tmp = realloc(b->data, cap);                  /* temporary! */
    if (!tmp) return -1;
    b->data = tmp;
    b->cap  = cap;
    if (b->len == 0) b->data[0] = '\0';                 /* valid from the start */
    return 0;
}

/* Append n bytes. O(n) in the PIECE, not in the result: no rescanning. */
static int sb_append_len(StrBuf *b, const char *s, size_t n)
{
    if (sb_reserve(b, n) != 0) return -1;
    memcpy(b->data + b->len, s, n);      /* write at the REMEMBERED offset */
    b->len += n;
    b->data[b->len] = '\0';              /* keep it a valid C string */
    return 0;
}

static int sb_append(StrBuf *b, const char *s) { return sb_append_len(b, s, strlen(s)); }
static int sb_append_char(StrBuf *b, char c)   { return sb_append_len(b, &c, 1); }

/* Formatted append: measure with snprintf, reserve, then write for real. */
static int sb_appendf(StrBuf *b, const char *fmt, ...)
{
    va_list ap, ap2;
    va_start(ap, fmt);
    va_copy(ap2, ap);                    /* a va_list can only be walked ONCE */

    int need = vsnprintf(NULL, 0, fmt, ap);   /* how many bytes would it write? */
    va_end(ap);

    int rc = -1;
    if (need >= 0 && sb_reserve(b, (size_t)need) == 0) {
        vsnprintf(b->data + b->len, (size_t)need + 1, fmt, ap2);
        b->len += (size_t)need;
        rc = 0;
    }
    va_end(ap2);
    return rc;
}

/* Hand ownership to the caller and reset the builder. */
static char *sb_release(StrBuf *b)
{
    char *out = b->data ? b->data : calloc(1, 1);   /* never return NULL for "" */
    sb_init(b);                                      /* caller now owns it */
    return out;
}

int main(void)
{
    StrBuf b;
    sb_init(&b);

    sb_append(&b, "SELECT * FROM users");
    sb_append(&b, " WHERE ");

    const char *cols[]  = { "age", "score", "rank" };
    const int   values[] = { 18, 90, 3 };

    for (size_t i = 0; i < 3; i++) {
        if (i) sb_append(&b, " AND ");
        sb_appendf(&b, "%s > %d", cols[i], values[i]);   /* formatted append */
    }
    sb_append_char(&b, ';');

    printf("%s\n", b.data);
    printf("len=%zu cap=%zu\n", b.len, b.cap);

    char *owned = sb_release(&b);        /* the builder is now empty */
    printf("released: %s\n", owned);
    free(owned);                         /* the CALLER frees it */

    sb_free(&b);                         /* safe: already reset */
    return 0;
}

Measuring the quadratic blow-up:

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

#define N 20000

/* O(n^2): strcat rescans from the start of the buffer on EVERY call. */
static double quadratic(void)
{
    char *buf = malloc(N * 8 + 1);
    if (!buf) return -1;
    buf[0] = '\0';

    clock_t t0 = clock();
    for (int i = 0; i < N; i++)
        strcat(buf, "abcdefg");          /* walks i*7 bytes just to find the end */
    double secs = (double)(clock() - t0) / CLOCKS_PER_SEC;

    free(buf);
    return secs;
}

/* O(n): the offset is remembered, so nothing is rescanned. */
static double linear(void)
{
    char  *buf = malloc(N * 8 + 1);
    if (!buf) return -1;
    size_t len = 0;

    clock_t t0 = clock();
    for (int i = 0; i < N; i++) {
        memcpy(buf + len, "abcdefg", 7);  /* write straight at the offset */
        len += 7;
    }
    buf[len] = '\0';
    double secs = (double)(clock() - t0) / CLOCKS_PER_SEC;

    free(buf);
    return secs;
}

int main(void)
{
    printf("strcat loop:   %.4f s\n", quadratic());
    printf("tracked len:   %.4f s\n", linear());
    return 0;
}

   WHY REPEATED strcat IS QUADRATIC

   append 1:  |x|                      scan 0 bytes to find the end
   append 2:  |x|x|                    scan 1
   append 3:  |x|x|x|                  scan 2
   append 4:  |x|x|x|x|                scan 3
      ...
   append n:  |x|x| ... |x|            scan n-1
                                       ------------------------
                                       total ~ n^2/2 bytes scanned

   A string builder stores 'len', so every append scans 0 bytes:
                                       total = n bytes copied

Key Takeaways

• Repeated strcat is O(n²) because each call rescans the whole buffer to find the terminator; tracking the length makes appending O(1) per byte.
• A string builder is a dynamic array of char with geometric growth, a remembered length, and a NUL terminator maintained at all times.
• Use snprintf(NULL, 0, fmt, ...) to measure a formatted append exactly, then reserve and write — and va_copy when you must walk a va_list twice.
• Decide and document whether the builder or the caller owns the finished string; mixed conventions produce double frees.
• Every append may reallocate, so any char * into the buffer taken before an append is invalid after it.

🧪 Practice

1. Add sb_append_repeat(StrBuf *b, char c, size_t n) and sb_truncate(StrBuf *b, size_t len), keeping the terminator correct in both.
2. Write a CSV row builder that quotes any field containing a comma or a quote, doubling embedded quotes, and test it on awkward inputs.
3. Benchmark building a 1 MB string with strcat, with the builder, and with a single snprintf size probe plus one allocation. Explain the ranking.
4. Interview-style: "A log-formatting function that concatenates 5,000 fragments takes 40 seconds. What is wrong?" Hint: ask what strcat must do before it can copy a single byte.

<a id="102-associative-and-hierarchical-structures"></a>

10.2 Associative and Hierarchical Structures

Linear structures answer "what is at position i". These answer harder questions: "is this key present", "what is the smallest remaining item", "which words start with this prefix". Each buys its speed with a different organizing principle — hashing, ordering, or shape — and each has a failure mode that shows up only at scale.

Hash Tables and Collision Handling

Theory

Suppose you want to look up a value by a string key. A linear scan through n pairs is O(n). A sorted array with binary search is O(log n) but needs shifting on insertion. A hash table gets you O(1) average by a different trick entirely: compute the storage location from the key itself.

A hash function maps a key to an integer. Reduce that integer modulo the table size and you have a bucket index. Storing and looking up are then both "hash, index, check" — no searching at all. That is the whole idea, and everything else is dealing with its one unavoidable problem.

Collisions are guaranteed. There are vastly more possible keys than buckets, so different keys will land in the same bucket. The birthday paradox makes this happen far earlier than intuition suggests: with 365 buckets and just 23 keys, a collision is more likely than not. A hash table is therefore not "a hash function" — it is a hash function plus a collision strategy.

The two strategies:

Separate chaining. Each bucket holds a linked list (or small array) of entries. On collision, append to the list. Lookup hashes to the bucket and walks its short chain. Simple, tolerant of high load, and deletion is trivial — but it costs a pointer per entry and an allocation per insertion, and the chains scatter across memory.

Open addressing. Every entry lives in the table array itself. On collision, probe for another slot by a fixed rule: linear probing checks i+1, i+2, ...; quadratic probing checks i+1, i+4, i+9, ...; double hashing uses a second hash for the step. No per-entry allocation and excellent cache behavior, since probing walks contiguous memory. The catch is deletion: you cannot simply blank a slot, because that would break the probe chain for any entry that probed past it. You must write a tombstone marking "occupied once, now empty, keep probing".

The load factor — entries divided by buckets — governs performance for both. As it rises, chains lengthen and probe sequences grow; open addressing degrades sharply as it approaches 1.0, because the table runs out of empty slots to stop a probe. The fix is rehashing: when the load factor crosses a threshold (0.75 is a common choice for chaining, 0.5–0.7 for open addressing), allocate a table roughly twice as large and reinsert every entry — bucket indices depend on the table size, so entries cannot simply be copied.

The hash function itself matters more than beginners expect. A weak one — summing the bytes, say — maps anagrams together and clusters short strings badly, turning O(1) into O(n). Use a proven one: FNV-1a is four lines and good enough for most purposes; djb2 is similarly compact. Note that a table keyed by attacker-controlled strings can be attacked by deliberately colliding keys, which is why security-sensitive tables use a keyed hash such as SipHash with a per-process random seed.

Examples

#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <stdint.h>
#include <stdbool.h>

/* FNV-1a: short, well-distributed, and fast. Do not invent your own. */
static uint64_t fnv1a(const char *s)
{
    uint64_t h = 1469598103934665603ULL;      /* offset basis */
    for (; *s; s++) {
        h ^= (unsigned char)*s;               /* XOR the byte in FIRST */
        h *= 1099511628211ULL;                /* then multiply by the prime */
    }
    return h;
}

/* ---------------- separate chaining ---------------- */
typedef struct Entry {
    char         *key;        /* owned by the table */
    int           value;
    uint64_t      hash;       /* cached: avoids rehashing on every compare */
    struct Entry *next;
} Entry;

typedef struct {
    Entry **buckets;
    size_t  nbuckets;         /* power of two */
    size_t  count;
} Map;

#define MAX_LOAD_NUM 3        /* rehash when count > 3/4 * nbuckets */
#define MAX_LOAD_DEN 4

static int map_init(Map *m, size_t nbuckets)
{
    m->buckets = calloc(nbuckets, sizeof *m->buckets);   /* calloc: all NULL */
    if (!m->buckets) return -1;
    m->nbuckets = nbuckets;
    m->count = 0;
    return 0;
}

static void map_free(Map *m)
{
    for (size_t i = 0; i < m->nbuckets; i++)
        for (Entry *e = m->buckets[i], *next; e; e = next) {
            next = e->next;                   /* read BEFORE freeing */
            free(e->key);                     /* the table owns the key copy */
            free(e);
        }
    free(m->buckets);
    m->buckets = NULL; m->nbuckets = m->count = 0;
}

/* Grow and reinsert. Entries cannot just be copied: the bucket index
   depends on nbuckets, so every entry must be re-placed. */
static int map_rehash(Map *m)
{
    size_t  new_n = m->nbuckets * 2;
    Entry **new_b = calloc(new_n, sizeof *new_b);
    if (!new_b) return -1;

    for (size_t i = 0; i < m->nbuckets; i++)
        for (Entry *e = m->buckets[i], *next; e; e = next) {
            next = e->next;
            size_t j = e->hash & (new_n - 1);   /* reuse the CACHED hash */
            e->next = new_b[j];                 /* splice into the new bucket */
            new_b[j] = e;
        }

    free(m->buckets);
    m->buckets  = new_b;
    m->nbuckets = new_n;
    return 0;
}

static int map_put(Map *m, const char *key, int value)
{
    uint64_t h = fnv1a(key);
    size_t   i = h & (m->nbuckets - 1);         /* power of two -> mask */

    for (Entry *e = m->buckets[i]; e; e = e->next)
        if (e->hash == h && strcmp(e->key, key) == 0) {
            e->value = value;                   /* update, do not duplicate */
            return 0;
        }

    if ((m->count + 1) * MAX_LOAD_DEN > m->nbuckets * MAX_LOAD_NUM) {
        if (map_rehash(m) != 0) return -1;
        i = h & (m->nbuckets - 1);              /* the index MOVED */
    }

    Entry *e = malloc(sizeof *e);
    if (!e) return -1;
    /* strdup is POSIX (and C23); with a strict -std=c11 compiler, define
       _POSIX_C_SOURCE 200809L or write the two-line malloc+memcpy yourself. */
    e->key = strdup(key);                       /* copy: the caller's may die */
    if (!e->key) { free(e); return -1; }
    e->value = value;
    e->hash  = h;
    e->next  = m->buckets[i];                   /* push at the front: O(1) */
    m->buckets[i] = e;
    m->count++;
    return 0;
}

static bool map_get(const Map *m, const char *key, int *out)
{
    uint64_t h = fnv1a(key);
    for (Entry *e = m->buckets[h & (m->nbuckets - 1)]; e; e = e->next)
        /* Compare the cheap hash first; strcmp only on a hash match. */
        if (e->hash == h && strcmp(e->key, key) == 0) { *out = e->value; return true; }
    return false;
}

static bool map_remove(Map *m, const char *key)
{
    uint64_t h = fnv1a(key);
    /* Pointer-to-pointer walk: no special case for the first entry. */
    for (Entry **link = &m->buckets[h & (m->nbuckets - 1)]; *link; link = &(*link)->next)
        if ((*link)->hash == h && strcmp((*link)->key, key) == 0) {
            Entry *dead = *link;
            *link = dead->next;
            free(dead->key); free(dead);
            m->count--;
            return true;
        }
    return false;
}

int main(void)
{
    Map m;
    if (map_init(&m, 8) != 0) return 1;

    const char *words[] = { "alpha","beta","gamma","delta","epsilon","zeta","eta" };
    for (int i = 0; i < 7; i++) map_put(&m, words[i], i * 10);

    int v;
    printf("gamma  -> %s%d\n", map_get(&m, "gamma",  &v) ? "" : "(missing) ", v);
    printf("missing-> %s\n",   map_get(&m, "nosuch", &v) ? "found" : "not found");

    map_put(&m, "beta", 999);                   /* update in place */
    map_get(&m, "beta", &v); printf("beta   -> %d\n", v);

    map_remove(&m, "alpha");
    printf("count=%zu buckets=%zu load=%.2f\n",
           m.count, m.nbuckets, (double)m.count / (double)m.nbuckets);

    map_free(&m);
    return 0;
}

Open addressing with linear probing and tombstones:

#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <stdint.h>
#include <stdbool.h>

typedef enum { SLOT_EMPTY = 0, SLOT_FULL, SLOT_TOMB } SlotState;

typedef struct { char *key; int value; SlotState state; } Slot;
typedef struct { Slot *slots; size_t cap; size_t count, used; } OpenMap;
/* count = live entries;  used = live + tombstones (what probing must consider) */

static uint64_t hash_str(const char *s)
{
    uint64_t h = 1469598103934665603ULL;
    for (; *s; s++) { h ^= (unsigned char)*s; h *= 1099511628211ULL; }
    return h;
}

static int om_init(OpenMap *m, size_t cap)
{
    m->slots = calloc(cap, sizeof *m->slots);    /* SLOT_EMPTY == 0 */
    if (!m->slots) return -1;
    m->cap = cap; m->count = m->used = 0;
    return 0;
}

static void om_free(OpenMap *m)
{
    for (size_t i = 0; i < m->cap; i++)
        if (m->slots[i].state == SLOT_FULL) free(m->slots[i].key);
    free(m->slots);
    m->slots = NULL; m->cap = m->count = m->used = 0;
}

/* Find the slot for 'key': the existing entry, or the first place to put it.
   Probing STOPS at EMPTY but CONTINUES past a TOMBSTONE -- that is exactly
   why deletion cannot simply blank a slot. */
static size_t om_probe(const OpenMap *m, const char *key, bool *found)
{
    size_t i     = hash_str(key) & (m->cap - 1);
    size_t first_tomb = m->cap;                  /* cap == "none seen" */

    for (;;) {
        Slot *s = &m->slots[i];

        if (s->state == SLOT_EMPTY) {            /* the key is not present */
            *found = false;
            return first_tomb != m->cap ? first_tomb : i;   /* reuse a tombstone */
        }
        if (s->state == SLOT_TOMB) {
            if (first_tomb == m->cap) first_tomb = i;
        } else if (strcmp(s->key, key) == 0) {
            *found = true;
            return i;
        }
        i = (i + 1) & (m->cap - 1);              /* LINEAR probe, wrapping */
    }
}

static int om_grow(OpenMap *m)
{
    OpenMap bigger;
    if (om_init(&bigger, m->cap * 2) != 0) return -1;

    for (size_t i = 0; i < m->cap; i++)
        if (m->slots[i].state == SLOT_FULL) {    /* tombstones are dropped */
            bool found;
            size_t j = om_probe(&bigger, m->slots[i].key, &found);
            bigger.slots[j] = m->slots[i];
            bigger.count++; bigger.used++;
        }

    free(m->slots);                              /* keys were MOVED, not copied */
    *m = bigger;
    return 0;
}

static int om_put(OpenMap *m, const char *key, int value)
{
    /* Grow on 'used', not 'count': tombstones also lengthen probe chains. */
    if ((m->used + 1) * 2 > m->cap && om_grow(m) != 0) return -1;

    bool found;
    size_t i = om_probe(m, key, &found);

    if (found) { m->slots[i].value = value; return 0; }

    char *copy = strdup(key);
    if (!copy) return -1;
    if (m->slots[i].state == SLOT_EMPTY) m->used++;   /* a tombstone was reused */
    m->slots[i] = (Slot){ copy, value, SLOT_FULL };
    m->count++;
    return 0;
}

static bool om_get(const OpenMap *m, const char *key, int *out)
{
    bool found;
    size_t i = om_probe(m, key, &found);
    if (found) *out = m->slots[i].value;
    return found;
}

static bool om_remove(OpenMap *m, const char *key)
{
    bool found;
    size_t i = om_probe(m, key, &found);
    if (!found) return false;

    free(m->slots[i].key);
    m->slots[i].key   = NULL;
    m->slots[i].state = SLOT_TOMB;      /* NOT EMPTY: probes must pass through */
    m->count--;                         /* 'used' stays: the slot still blocks */
    return true;
}

int main(void)
{
    OpenMap m;
    if (om_init(&m, 16) != 0) return 1;

    om_put(&m, "one", 1); om_put(&m, "two", 2); om_put(&m, "three", 3);

    int v;
    om_remove(&m, "two");                      /* leaves a tombstone */
    printf("three -> %s\n", om_get(&m, "three", &v) ? "found" : "LOST");
    printf("two   -> %s\n", om_get(&m, "two",   &v) ? "found" : "not found");
    printf("count=%zu used=%zu cap=%zu\n", m.count, m.used, m.cap);

    om_free(&m);
    return 0;
}

   WHY DELETION NEEDS A TOMBSTONE (linear probing)

   "cat" and "dog" both hash to bucket 3.
   insert cat -> slot 3.   insert dog -> 3 taken, probe to slot 4.

        3        4        5
      +------+------+------+
      | cat  | dog  |empty |
      +------+------+------+

   Now delete "cat" by blanking slot 3:

        3        4        5
      +------+------+------+
      |EMPTY | dog  |empty |
      +------+------+------+

   get("dog") hashes to 3, sees EMPTY, and concludes "not present".
   dog is still there -- it is now UNREACHABLE.

   With a tombstone:

        3        4        5
      +------+------+------+
      |TOMB  | dog  |empty |
      +------+------+------+

   get("dog") sees TOMB, keeps probing, finds dog at slot 4. Correct.
   Tombstones accumulate, so grow on (live + tombstones), not on live alone.

	Separate chaining	Open addressing
Entry storage	linked nodes outside the table	inside the table array
Allocation per insert	one	none
Cache behavior	poor (pointer chasing)	excellent (contiguous probing)
Tolerates load factor > 1	yes, degrades gracefully	no, breaks at 1.0
Deletion	trivial unlink	needs tombstones
Typical max load factor	0.75	0.5 - 0.7
Sensitive to a weak hash	chains lengthen	clustering, severe degradation

Key Takeaways

• A hash table computes the storage location from the key, giving O(1) average lookup; collisions are mathematically unavoidable, so the collision strategy is half the design.
• Separate chaining stores colliding entries in per-bucket lists — simple and tolerant of high load; open addressing stores everything in the array — faster and cache-friendly, but it breaks down near a full table.
• The load factor drives performance: rehash into a table roughly twice as large when it crosses about 0.75 (chaining) or 0.5–0.7 (open addressing), reinserting every entry because bucket indices depend on the size.
• Open addressing must mark deleted slots with tombstones, or entries that probed past them become unreachable; grow based on live entries plus tombstones.
• Use a proven hash such as FNV-1a, cache the hash in each entry to skip most strcmp calls, and use a seeded hash when keys come from untrusted input.

🧪 Practice

1. Add map_iterate(Map *m, void (*fn)(const char *key, int value, void *ctx), void *ctx) to the chaining implementation and use it to print every pair.
2. Instrument the chaining table to report the longest chain and the number of empty buckets after inserting 100,000 keys. Then swap FNV-1a for "sum of bytes" and compare.
3. Implement quadratic probing in the open-addressing table and measure the average probe count at load factors 0.5, 0.7, and 0.9 against linear probing.
4. Interview-style: "Why must an open-addressed hash table use tombstones instead of clearing a slot on deletion?" Hint: trace a lookup for a key that was displaced past the deleted slot.

Binary Search Trees

Theory

A hash table gives O(1) lookup but destroys order — iterating one yields keys in an arbitrary sequence, and asking for "the smallest key greater than x" requires scanning everything. When you need ordered operations, you need a tree.

A binary search tree stores each key in a node with up to two children and maintains one invariant everywhere:

every key in the left subtree is less than the node's key, and every key in the right subtree is greater

That single property makes searching a sequence of decisions. Compare with the root: smaller means go left, larger means go right, equal means found. Each step discards an entire subtree — the same halving that makes binary search on a sorted array O(log n).

The invariant also makes ordered traversal free. An in-order walk — left subtree, node, right subtree — visits keys in sorted order, which is what a hash table cannot do at any price.

                    50
                   /  \
                 30    70
                /  \  /  \
              20   40 60  80

   search(40):  50 -> go left -> 30 -> go right -> 40. Found in 3 steps.
   in-order:    20 30 40 50 60 70 80   (sorted, for free)

The catch, and it is a serious one: the shape depends on the insertion order, and the shape determines the performance. Inserting 1, 2, 3, 4, 5 in ascending order produces a tree where every node has only a right child — a linked list wearing a tree costume, with O(n) search. Sorted input is not a rare edge case; it is what you get from a database export, a sorted file, or timestamps.

   RANDOM ORDER (balanced)        SORTED ORDER (degenerate)

           50                      1
          /  \                      \
        30    70                     2
       /  \  /  \                     \
     20   40 60  80                    3
                                        \
   height ~ log2(n)                      4     height = n
   search O(log n)                        \    search O(n)
                                           5

This is why production code uses self-balancing trees — AVL, red-black, or a B-tree for on-disk data — which perform rotations on insertion and deletion to keep the height at O(log n) regardless of input order. They are considerably more code, and understanding the plain BST first is the right order to learn them.

Deletion is the one genuinely fiddly operation, with three cases:

1. No children — unlink and free.
2. One child — replace the node with that child.
3. Two children — the node cannot simply be removed. Find its in-order successor (the smallest key in the right subtree, reached by going right once then left as far as possible), copy that key into the node, then delete the successor — which by construction has at most one child, reducing to case 1 or 2.

Recursion suits trees naturally, but note the depth: a recursive traversal of a degenerate tree with a million nodes will overflow the hardware stack. Iterative traversal with an explicit stack is the robust form.

Examples

#include <stdio.h>
#include <stdlib.h>
#include <stdbool.h>

typedef struct TNode {
    int           key;
    struct TNode *left, *right;
} TNode;

static TNode *node_new(int key)
{
    TNode *n = malloc(sizeof *n);
    if (n) { n->key = key; n->left = n->right = NULL; }
    return n;
}

/* Insert by walking the pointer that must change -- the same Node **
   idiom as the linked list, which removes the empty-tree special case. */
static int bst_insert(TNode **root, int key)
{
    TNode **link = root;
    while (*link) {
        if      (key < (*link)->key) link = &(*link)->left;
        else if (key > (*link)->key) link = &(*link)->right;
        else return 0;                       /* already present: no duplicates */
    }
    TNode *n = node_new(key);
    if (!n) return -1;
    *link = n;                               /* attach where the walk stopped */
    return 0;
}

/* Search: each comparison discards half the remaining tree. */
static bool bst_contains(const TNode *root, int key)
{
    while (root) {
        if      (key < root->key) root = root->left;
        else if (key > root->key) root = root->right;
        else return true;
    }
    return false;
}

static TNode *bst_min(TNode *n)
{
    while (n && n->left) n = n->left;        /* leftmost node = smallest key */
    return n;
}

/* Deletion, all three cases. Returns the new subtree root. */
static TNode *bst_delete(TNode *root, int key)
{
    if (!root) return NULL;

    if      (key < root->key) root->left  = bst_delete(root->left,  key);
    else if (key > root->key) root->right = bst_delete(root->right, key);
    else {
        /* Cases 1 and 2: zero or one child -- promote the child (or NULL). */
        if (!root->left)  { TNode *r = root->right; free(root); return r; }
        if (!root->right) { TNode *l = root->left;  free(root); return l; }

        /* Case 3: two children. Replace this key with its in-order
           successor, then delete the successor from the right subtree.
           The successor has NO left child, so that delete hits case 1 or 2. */
        TNode *succ = bst_min(root->right);
        root->key   = succ->key;
        root->right = bst_delete(root->right, succ->key);
    }
    return root;
}

/* In-order traversal yields sorted keys -- the property a hash table lacks. */
static void bst_inorder(const TNode *n, void (*visit)(int))
{
    if (!n) return;
    bst_inorder(n->left, visit);
    visit(n->key);
    bst_inorder(n->right, visit);
}

/* Post-order is the ONLY safe order for freeing: children before the parent. */
static void bst_free(TNode *n)
{
    if (!n) return;
    bst_free(n->left);
    bst_free(n->right);
    free(n);
}

static int bst_height(const TNode *n)
{
    if (!n) return 0;
    int l = bst_height(n->left), r = bst_height(n->right);
    return 1 + (l > r ? l : r);
}

static void print_key(int k) { printf("%d ", k); }

int main(void)
{
    TNode *balanced = NULL;
    int mixed[] = { 50, 30, 70, 20, 40, 60, 80 };
    for (size_t i = 0; i < 7; i++) bst_insert(&balanced, mixed[i]);

    printf("in-order: ");  bst_inorder(balanced, print_key);
    printf("\nheight: %d (7 nodes)\n", bst_height(balanced));   /* 3 */

    printf("contains 40: %s\n", bst_contains(balanced, 40) ? "yes" : "no");
    balanced = bst_delete(balanced, 30);      /* two children: uses case 3 */
    printf("after deleting 30: "); bst_inorder(balanced, print_key); putchar('\n');

    /* The same keys inserted in SORTED order degenerate into a list. */
    TNode *degenerate = NULL;
    for (int i = 1; i <= 7; i++) bst_insert(&degenerate, i * 10);
    printf("sorted-insert height: %d (7 nodes)\n", bst_height(degenerate));  /* 7 */

    bst_free(balanced);
    bst_free(degenerate);
    return 0;
}

Iterative in-order traversal, which does not risk a stack overflow:

#include <stdio.h>
#include <stdlib.h>

typedef struct TNode { int key; struct TNode *left, *right; } TNode;

/* An explicit stack replaces the call stack: safe on a degenerate tree
   with a million nodes, where recursion would segfault. */
static void inorder_iterative(TNode *root)
{
    TNode **stack = NULL;
    size_t  len = 0, cap = 0;
    TNode  *cur = root;

    while (cur || len) {
        while (cur) {                          /* descend, remembering the path */
            if (len == cap) {
                size_t ncap = cap ? cap * 2 : 32;
                TNode **tmp = realloc(stack, ncap * sizeof *tmp);
                if (!tmp) { free(stack); return; }
                stack = tmp; cap = ncap;
            }
            stack[len++] = cur;
            cur = cur->left;
        }
        cur = stack[--len];                    /* the leftmost unvisited node */
        printf("%d ", cur->key);               /* VISIT */
        cur = cur->right;                      /* then its right subtree */
    }
    putchar('\n');
    free(stack);
}

Operation	Balanced BST	Degenerate BST	Hash table	Sorted array
Search	O(log n)	O(n)	O(1) average	O(log n)
Insert	O(log n)	O(n)	O(1) average	O(n)
Delete	O(log n)	O(n)	O(1) average	O(n)
Min / max	O(log n)	O(n)	O(n)	O(1)
Sorted iteration	O(n)	O(n)	O(n log n) — must sort	O(n)
Range query	O(log n + k)	O(n)	O(n)	O(log n + k)

Key Takeaways

• A BST keeps every left-subtree key below the node and every right-subtree key above, turning search into a sequence of halving decisions.
• In-order traversal yields sorted keys and range queries are cheap — the ordered operations a hash table cannot provide.
• Performance depends entirely on the shape: sorted insertion produces a degenerate O(n) tree, and sorted input is common, not exotic.
• Deleting a node with two children requires promoting its in-order successor, which by construction has at most one child.
• Free with a post-order traversal, and use an explicit stack for traversal when the tree may be deep enough to overflow the call stack.

🧪 Practice

1. Add bst_count, bst_max, and a bst_is_valid that verifies the ordering invariant using a min/max range rather than only comparing with immediate children.
2. Write bst_range(root, lo, hi, visit) that visits only keys in [lo, hi], pruning subtrees that cannot contain any.
3. Insert 10,000 sequential integers, then 10,000 shuffled ones, and print the resulting heights. Explain the ratio you see.
4. Interview-style: "When would you choose a balanced BST over a hash table?" Hint: list the questions a hash table cannot answer without examining every entry.

Heaps and Priority Queues

Theory

A queue serves items in arrival order. Sometimes you need them served in importance order instead: the shortest job next, the nearest unvisited vertex in Dijkstra's algorithm, the highest-priority interrupt. That is a priority queue, and the standard implementation is a binary heap.

You could implement a priority queue with a sorted array — O(1) to find the best item but O(n) to insert. Or an unsorted array — O(1) to insert but O(n) to find. A heap gives O(log n) for both, which is the right balance when you do many of each.

The trick is that a priority queue does not need full sorting. It only needs the most important item to be findable. So the heap maintains a much weaker invariant than a BST:

every node's key is less than or equal to both of its children's keys (a min-heap)

That is it. No relationship between siblings, and no left/right ordering. The minimum is therefore always at the root, but the structure is far cheaper to maintain than a sorted order.

The second insight is that a heap is a complete binary tree — every level full except possibly the last, which fills left to right — and a complete tree can be stored in a plain array with no pointers at all. For the node at index i:

   parent(i)      = (i - 1) / 2
   left_child(i)  = 2*i + 1
   right_child(i) = 2*i + 2

   array:  [ 10, 20, 15, 40, 25, 30, 50 ]
   index:     0   1   2   3   4   5   6

                    10 (0)
                   /      \
              20 (1)      15 (2)
              /    \      /    \
         40 (3) 25 (4) 30 (5) 50 (6)

   No pointers, no allocation per node, perfect cache locality.

Both operations restore the invariant by moving one element along a single root-to-leaf path, which is why both are O(log n):

Insert (sift up). Append at the end of the array — the only position that keeps the tree complete — then repeatedly swap with the parent while it is larger. The new element bubbles up until its parent is smaller.

Extract-min (sift down). The root is the answer. Move the last element into the root (keeping completeness), shrink the array, then repeatedly swap with the smaller child while either child is smaller. Swapping with the smaller child is essential — swapping with the larger one violates the invariant on the other side.

Heapify builds a heap from an unordered array of n elements. The obvious approach — insert each one — is O(n log n). Sifting down from the last internal node backwards to the root is O(n), which is surprising but correct: most nodes are near the leaves and sift down only a step or two.

A heap does not give you sorted iteration, and it does not support finding an arbitrary element in better than O(n). Deleting or changing the priority of a known element requires an auxiliary index mapping elements to positions — which is what Dijkstra's decrease-key needs.

Examples

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

/* A min-heap over an implicit complete binary tree stored in an array. */
typedef struct { int *data; size_t len, cap; } Heap;

static void heap_init(Heap *h) { h->data = NULL; h->len = h->cap = 0; }
static void heap_free(Heap *h) { free(h->data); heap_init(h); }

static void swap(int *a, int *b) { int t = *a; *a = *b; *b = t; }

/* Move element i UP until its parent is no larger. O(log n). */
static void sift_up(Heap *h, size_t i)
{
    while (i > 0) {
        size_t parent = (i - 1) / 2;
        if (h->data[parent] <= h->data[i]) break;      /* invariant restored */
        swap(&h->data[parent], &h->data[i]);
        i = parent;
    }
}

/* Move element i DOWN until both children are no smaller. O(log n). */
static void sift_down(Heap *h, size_t i)
{
    for (;;) {
        size_t l = 2 * i + 1, r = 2 * i + 2, smallest = i;

        if (l < h->len && h->data[l] < h->data[smallest]) smallest = l;
        if (r < h->len && h->data[r] < h->data[smallest]) smallest = r;
        if (smallest == i) break;

        /* Swapping with the SMALLER child is essential: swapping with the
           larger one would leave it above its own smaller sibling. */
        swap(&h->data[i], &h->data[smallest]);
        i = smallest;
    }
}

static int heap_push(Heap *h, int value)
{
    if (h->len == h->cap) {
        size_t cap = h->cap ? h->cap * 2 : 8;
        int   *tmp = realloc(h->data, cap * sizeof *tmp);
        if (!tmp) return -1;
        h->data = tmp; h->cap = cap;
    }
    h->data[h->len] = value;          /* append keeps the tree COMPLETE */
    sift_up(h, h->len);
    h->len++;
    return 0;
}

static bool heap_peek(const Heap *h, int *out)
{
    if (h->len == 0) return false;
    *out = h->data[0];                /* the minimum is always the root */
    return true;
}

static bool heap_pop(Heap *h, int *out)
{
    if (h->len == 0) return false;
    *out = h->data[0];
    h->data[0] = h->data[--h->len];   /* the LAST element fills the root */
    sift_down(h, 0);                  /* then sinks to its proper place */
    return true;
}

/* Build a heap from an unordered array in O(n), not O(n log n):
   sift down from the last internal node backwards. */
static int heap_from_array(Heap *h, const int *src, size_t n)
{
    h->data = malloc(n * sizeof *h->data);
    if (!h->data) return -1;
    memcpy(h->data, src, n * sizeof *src);
    h->len = h->cap = n;

    if (n < 2) return 0;
    /* Leaves are already valid heaps, so start at the last node that has
       a child and walk backwards to the root. */
    for (size_t i = n / 2; i-- > 0; )
        sift_down(h, i);
    return 0;
}

int main(void)
{
    Heap h;
    heap_init(&h);

    int input[] = { 42, 7, 19, 3, 88, 15, 1, 56 };
    for (size_t i = 0; i < 8; i++) heap_push(&h, input[i]);

    int v;
    heap_peek(&h, &v);
    printf("min = %d\n", v);                      /* 1 */

    printf("drained in order: ");
    while (heap_pop(&h, &v)) printf("%d ", v);    /* 1 3 7 15 19 42 56 88 */
    putchar('\n');
    heap_free(&h);

    /* O(n) construction from an existing array. */
    Heap h2;
    if (heap_from_array(&h2, input, 8) == 0) {
        heap_peek(&h2, &v);
        printf("heapified min = %d\n", v);        /* 1 */
        heap_free(&h2);
    }
    return 0;
}

A priority queue of tasks, which is what heaps are actually used for:

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

typedef struct { int priority; unsigned seq; char name[24]; } Task;

/* Lower priority value = more urgent. 'seq' breaks ties by arrival order,
   making the queue STABLE -- a heap gives no such guarantee by itself. */
static bool more_urgent(const Task *a, const Task *b)
{
    if (a->priority != b->priority) return a->priority < b->priority;
    return a->seq < b->seq;
}

typedef struct { Task *data; size_t len, cap; unsigned next_seq; } PQ;

static void pq_sift_up(PQ *q, size_t i)
{
    while (i > 0) {
        size_t p = (i - 1) / 2;
        if (!more_urgent(&q->data[i], &q->data[p])) break;
        Task t = q->data[p]; q->data[p] = q->data[i]; q->data[i] = t;
        i = p;
    }
}

static void pq_sift_down(PQ *q, size_t i)
{
    for (;;) {
        size_t l = 2*i + 1, r = 2*i + 2, best = i;
        if (l < q->len && more_urgent(&q->data[l], &q->data[best])) best = l;
        if (r < q->len && more_urgent(&q->data[r], &q->data[best])) best = r;
        if (best == i) break;
        Task t = q->data[best]; q->data[best] = q->data[i]; q->data[i] = t;
        i = best;
    }
}

static int pq_push(PQ *q, int priority, const char *name)
{
    if (q->len == q->cap) {
        size_t cap = q->cap ? q->cap * 2 : 8;
        Task  *tmp = realloc(q->data, cap * sizeof *tmp);
        if (!tmp) return -1;
        q->data = tmp; q->cap = cap;
    }
    Task *t = &q->data[q->len];
    t->priority = priority;
    t->seq = q->next_seq++;
    snprintf(t->name, sizeof t->name, "%s", name);
    pq_sift_up(q, q->len++);
    return 0;
}

static bool pq_pop(PQ *q, Task *out)
{
    if (q->len == 0) return false;
    *out = q->data[0];
    q->data[0] = q->data[--q->len];
    pq_sift_down(q, 0);
    return true;
}

int main(void)
{
    PQ q = {0};
    pq_push(&q, 3, "write report");
    pq_push(&q, 1, "fix outage");
    pq_push(&q, 2, "review PR");
    pq_push(&q, 1, "page on-call");     /* same priority as "fix outage" */

    Task t;
    while (pq_pop(&q, &t))
        printf("p%d  %s\n", t.priority, t.name);
    /* p1 fix outage / p1 page on-call / p2 review PR / p3 write report */

    free(q.data);
    return 0;
}

Structure	Find min	Insert	Extract min	Sorted iteration
Unsorted array	O(n)	O(1)	O(n)	O(n log n)
Sorted array	O(1)	O(n)	O(1)	O(n)
Binary heap	O(1)	O(log n)	O(log n)	not supported directly
Balanced BST	O(log n)	O(log n)	O(log n)	O(n)

Key Takeaways

• A heap maintains only "every parent is no greater than its children", which is much weaker than sorting and therefore much cheaper to maintain.
• A complete binary tree stores perfectly in an array: parent is (i-1)/2, children are 2i+1 and 2i+2 — no pointers, no per-node allocation.
• Insert appends and sifts up; extract-min takes the root, moves the last element there, and sifts down — both O(log n), both touching one root-to-leaf path.
• Sifting down must swap with the smaller child, and building a heap by sifting down from the last internal node is O(n), not O(n log n).
• A heap gives no sorted iteration and no fast lookup of arbitrary elements; add a sequence field for stable tie-breaking and an index map if you need decrease-key.

🧪 Practice

1. Convert the min-heap into a max-heap by changing only the comparisons, and verify that draining it yields descending order.
2. Implement heapsort: heapify the array in place, then repeatedly swap the root with the last element and sift down over the shrinking prefix. Confirm it needs no extra memory.
3. Write heap_kth_smallest(const int *a, size_t n, size_t k) using a heap of bounded size, and explain why it beats sorting the whole array when k is small.
4. Interview-style: "Why is building a heap by sifting down O(n) when inserting n elements one at a time is O(n log n)?" Hint: count how many nodes sit at each depth and how far each can actually sink.

Tries

Theory

A hash table finds an exact key fast, but it cannot answer "which keys start with pre" without examining every entry — hashing deliberately destroys the relationship between similar keys. A trie (from retrieval, usually pronounced "try") is built precisely for that question.

The idea: instead of storing whole keys at nodes, store one character per edge and let the path from the root spell the key. A node is not "a word" — it is "a prefix", and a flag marks which prefixes are complete words.

   Words: "cat", "car", "cart", "dog"

              (root)
              /     \
            c        d
            |        |
            a        o
           / \       |
          t*  r*     g*
              |
              t*

   * = terminal (a complete word ends here)

   "car" and "cart" SHARE the path c-a-r, stored once.
   All words starting with "ca" live under one node -- so prefix
   search is: walk to that node, then collect everything below it.

Three properties follow directly from that shape:

Lookup time depends on the key length, not the number of keys. Searching for a 5-character word takes 5 steps whether the trie holds 10 words or 10 million. That is O(m) for key length m, independent of n — better than a BST's O(m log n) and comparable to hashing, except that hashing must read the whole key to compute the hash anyway.

Prefixes are free. Walk to the node for the prefix; every word beneath it matches. This makes tries the natural structure for autocomplete, spell-check dictionaries, IP routing tables (longest-prefix match), and word games.

Keys are stored implicitly and shared. Common prefixes are stored once, which can save memory on a dictionary of related words.

The dominant cost is the node representation. A node with a fixed array of 26 (or 256) child pointers gives O(1) child access but wastes enormous space — a 256-way node on a 64-bit machine is 2 KB, and most tries have far more nodes than words. Three alternatives trade lookup speed for size:

Node representation	Child lookup	Memory per node	Good for
Fixed array (26 or 256)	O(1)	large, mostly NULL	small alphabets, speed-critical
Sorted array of pairs	O(log k)	proportional to real children	sparse tries
Linked list of children	O(k)	smallest	very sparse tries
Hash map per node	O(1) average	moderate + overhead	large alphabets

A compressed trie (radix tree or Patricia trie) collapses each chain of single-child nodes into one node holding the whole substring. For a dictionary of English words this removes the large majority of nodes and is what production implementations use.

Deletion needs care: after clearing a word's terminal flag, you may remove the node only if it has no children and is not itself terminal — otherwise you would delete a prefix that other words still need.

Examples

#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <stdbool.h>
#include <ctype.h>

#define ALPHABET 26        /* lowercase a-z */

typedef struct TrieNode {
    struct TrieNode *children[ALPHABET];
    bool             terminal;      /* a complete word ends at this node */
    size_t           child_count;   /* maintained so deletion can prune */
} TrieNode;

static TrieNode *trie_node_new(void)
{
    return calloc(1, sizeof(TrieNode));    /* calloc: all children NULL */
}

/* Map a character to a child index, or -1 if it is outside the alphabet. */
static int slot_of(char c)
{
    unsigned char u = (unsigned char)c;    /* cast: ctype needs unsigned char */
    if (!isalpha(u)) return -1;
    return tolower(u) - 'a';
}

static int trie_insert(TrieNode *root, const char *word)
{
    TrieNode *cur = root;

    for (const char *p = word; *p; p++) {
        int i = slot_of(*p);
        if (i < 0) return -1;              /* reject unsupported characters */

        if (!cur->children[i]) {
            TrieNode *n = trie_node_new();
            if (!n) return -1;
            cur->children[i] = n;
            cur->child_count++;
        }
        cur = cur->children[i];            /* descend one character */
    }
    cur->terminal = true;                  /* the path so far IS a word */
    return 0;
}

/* Walk to the node for 'prefix', or NULL if the path does not exist. */
static const TrieNode *trie_walk(const TrieNode *root, const char *prefix)
{
    const TrieNode *cur = root;
    for (const char *p = prefix; *p && cur; p++) {
        int i = slot_of(*p);
        if (i < 0) return NULL;
        cur = cur->children[i];
    }
    return cur;
}

/* An exact word must both exist as a path AND be marked terminal. */
static bool trie_contains(const TrieNode *root, const char *word)
{
    const TrieNode *n = trie_walk(root, word);
    return n && n->terminal;
}

/* Any existing path is a valid prefix, terminal or not. */
static bool trie_has_prefix(const TrieNode *root, const char *prefix)
{
    return trie_walk(root, prefix) != NULL;
}

/* Collect every word beneath 'n', building the suffix in 'buf' as we go. */
static void collect(const TrieNode *n, char *buf, size_t depth, size_t cap,
                    void (*visit)(const char *))
{
    if (!n || depth + 1 >= cap) return;

    if (n->terminal) { buf[depth] = '\0'; visit(buf); }

    for (int i = 0; i < ALPHABET; i++)
        if (n->children[i]) {
            buf[depth] = (char)('a' + i);          /* append this edge's char */
            collect(n->children[i], buf, depth + 1, cap, visit);
            /* No explicit undo needed: depth is restored by the return. */
        }
}

static void trie_complete(const TrieNode *root, const char *prefix,
                          void (*visit)(const char *))
{
    const TrieNode *start = trie_walk(root, prefix);
    if (!start) return;

    char buf[128];
    size_t plen = strlen(prefix);
    if (plen >= sizeof buf) return;

    memcpy(buf, prefix, plen);                     /* seed with the prefix */
    collect(start, buf, plen, sizeof buf, visit);
}

/* Delete a word, pruning nodes that become useless. Returns true if the
   caller should free the node it passed in. */
static bool trie_delete(TrieNode *n, const char *word)
{
    if (!n) return false;

    if (*word == '\0') {
        n->terminal = false;                       /* no longer a word */
    } else {
        int i = slot_of(*word);
        if (i < 0 || !n->children[i]) return false;

        if (trie_delete(n->children[i], word + 1)) {
            free(n->children[i]);
            n->children[i] = NULL;
            n->child_count--;
        }
    }
    /* Prunable only if nothing else needs this node: no children AND not
       itself the end of a shorter word. */
    return n->child_count == 0 && !n->terminal;
}

static void trie_free(TrieNode *n)
{
    if (!n) return;
    for (int i = 0; i < ALPHABET; i++) trie_free(n->children[i]);
    free(n);
}

static void print_word(const char *w) { printf("  %s\n", w); }

int main(void)
{
    TrieNode *root = trie_node_new();
    if (!root) return 1;

    const char *words[] = { "cat","car","cart","care","dog","do","door" };
    for (size_t i = 0; i < 7; i++) trie_insert(root, words[i]);

    printf("contains 'car':   %s\n", trie_contains(root, "car")  ? "yes" : "no");
    printf("contains 'ca':    %s\n", trie_contains(root, "ca")   ? "yes" : "no");
    printf("prefix   'ca':    %s\n", trie_has_prefix(root, "ca") ? "yes" : "no");

    printf("completions for 'ca':\n");
    trie_complete(root, "ca", print_word);      /* car, care, cart, cat */

    printf("completions for 'do':\n");
    trie_complete(root, "do", print_word);      /* do, dog, door */

    trie_delete(root, "cart");
    printf("after deleting 'cart', 'car' still present: %s\n",
           trie_contains(root, "car") ? "yes" : "no");

    trie_free(root);
    return 0;
}

	Trie	Hash table	Balanced BST
Exact lookup	O(m)	O(1) average, O(m) to hash	O(m log n)
Prefix search	O(m + k) for k results	O(n) — full scan	O(m log n + k)
Sorted iteration	yes, natural	no	yes
Worst case	O(m), no degradation	O(n) on collisions	O(log n)
Memory	high; shares prefixes	moderate	moderate
Best for	autocomplete, routing, dictionaries	exact-match lookup	ordered data, ranges

Key Takeaways

• A trie stores one character per edge, so the path from the root spells the key and a flag marks which prefixes are complete words.
• Lookup costs O(m) in the key length and is independent of how many keys the trie holds — no degradation as it grows.
• Prefix queries are the trie's reason to exist: walk to the prefix node, then collect everything beneath it.
• Node representation dominates memory: fixed 26- or 256-way arrays are fast and wasteful; sorted arrays, lists, or a radix tree that collapses single-child chains are far smaller.
• Deletion may only prune a node that has no children and is not itself terminal, or it will remove a prefix that other words still need.

🧪 Practice

1. Add trie_count_words and trie_longest_prefix_of(root, text) that returns the length of the longest stored word that prefixes text.
2. Replace the fixed 26-pointer array with a linked list of children and measure the memory difference on a 100,000-word dictionary.
3. Build a trie from /usr/share/dict/words and implement an autocomplete that returns only the first 10 completions for a prefix.
4. Interview-style: "You need autocomplete over a million product names. Trie or hash table?" Hint: consider what a hash table must do to find every key beginning with three given characters.

Graph Representations

Theory

A graph is the most general structure here: a set of vertices and a set of edges connecting them. Trees and linked lists are both special cases — a tree is a connected graph with no cycles, a list is a tree where every node has one child. Graphs model road networks, dependency chains, social connections, state machines, and package managers.

Before writing any graph algorithm you must choose a representation, and that choice determines what is cheap:

Adjacency matrix. A V x V array where m[i][j] is 1 if an edge runs from i to j. Checking whether two vertices are connected is a single array access — O(1), unbeatable. But it always costs V² memory regardless of edge count, and listing a vertex's neighbours means scanning an entire row of V entries, most of them zero.

Adjacency list. For each vertex, a list of the vertices it connects to. Memory is O(V + E), which for a sparse graph is dramatically smaller. Iterating a vertex's neighbours takes time proportional to its degree — exactly what traversals need. Checking a specific edge costs O(degree) rather than O(1).

The deciding factor is density. A graph with V vertices has at most V² edges. Real graphs are almost always sparse — a road network vertex connects to a handful of others, not to a million. For those, the matrix wastes essentially all of its memory: 100,000 vertices needs 10¹⁰ matrix entries but perhaps 500,000 list entries.

   Graph:  0 --- 1
           |   / |
           |  /  |
           2 --- 3

   ADJACENCY MATRIX (V x V = 16 entries)     ADJACENCY LIST (V + 2E = 4 + 10)

        0  1  2  3                            0 -> 1, 2
     0  0  1  1  0                            1 -> 0, 2, 3
     1  1  0  1  1                            2 -> 0, 1, 3
     2  1  1  0  1                            3 -> 1, 2
     3  0  1  1  0

   has_edge(1,3): one lookup                  has_edge(1,3): scan 1's list
   neighbours(1): scan 4 entries              neighbours(1): read 3 entries
   memory: always V^2                         memory: proportional to real edges

Beyond representation, three properties change the code:

• Directed or undirected. An undirected edge is stored twice in an adjacency list (once in each endpoint's list) and symmetrically in a matrix.
• Weighted or unweighted. Weights live in the matrix cells or alongside each list entry. Unweighted shortest paths use BFS; weighted ones need Dijkstra.
• Self-loops and parallel edges may or may not be permitted, and the representation should say which.

The two fundamental traversals differ only in the container they use for the frontier, which is a genuinely useful thing to notice:

Breadth-first search uses a queue. It visits all vertices at distance 1, then distance 2, and so on — so on an unweighted graph it finds shortest paths.

Depth-first search uses a stack (often the call stack, via recursion). It follows one path as deep as possible before backtracking — which is what you want for cycle detection, topological sorting, and finding connected components.

Both are O(V + E) with an adjacency list, and both need a visited array; without it, a cycle makes either loop forever.

Examples

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

/* ---- adjacency list: an array of per-vertex edge lists ---- */
typedef struct Edge { int to; int weight; struct Edge *next; } Edge;

typedef struct {
    Edge **adj;        /* adj[v] is the head of v's edge list */
    int    nverts;
    bool   directed;
} Graph;

static int graph_init(Graph *g, int nverts, bool directed)
{
    g->adj = calloc((size_t)nverts, sizeof *g->adj);
    if (!g->adj) return -1;
    g->nverts = nverts;
    g->directed = directed;
    return 0;
}

static void graph_free(Graph *g)
{
    for (int v = 0; v < g->nverts; v++)
        for (Edge *e = g->adj[v], *next; e; e = next) { next = e->next; free(e); }
    free(g->adj);
    g->adj = NULL; g->nverts = 0;
}

static int add_directed(Graph *g, int from, int to, int weight)
{
    Edge *e = malloc(sizeof *e);
    if (!e) return -1;
    e->to = to; e->weight = weight;
    e->next = g->adj[from];          /* push at the front: O(1) */
    g->adj[from] = e;
    return 0;
}

static int graph_add_edge(Graph *g, int a, int b, int weight)
{
    if (a < 0 || a >= g->nverts || b < 0 || b >= g->nverts) return -1;
    if (add_directed(g, a, b, weight) != 0) return -1;
    /* An UNDIRECTED edge is two directed edges. */
    if (!g->directed && a != b && add_directed(g, b, a, weight) != 0) return -1;
    return 0;
}

/* ---- BFS: a QUEUE gives shortest paths on an unweighted graph ---- */
static void bfs(const Graph *g, int start, int *dist, int *parent)
{
    for (int v = 0; v < g->nverts; v++) { dist[v] = -1; parent[v] = -1; }

    int *queue = malloc((size_t)g->nverts * sizeof *queue);
    if (!queue) return;
    int head = 0, tail = 0;

    dist[start] = 0;
    queue[tail++] = start;

    while (head < tail) {
        int v = queue[head++];                    /* FIFO: nearest first */
        for (const Edge *e = g->adj[v]; e; e = e->next)
            if (dist[e->to] == -1) {              /* -1 doubles as "unvisited" */
                dist[e->to]   = dist[v] + 1;
                parent[e->to] = v;
                queue[tail++] = e->to;            /* enqueue for the next ring */
            }
    }
    free(queue);
}

/* ---- DFS: a STACK (here, recursion) explores one path to the end ---- */
static void dfs_visit(const Graph *g, int v, bool *visited, int depth)
{
    visited[v] = true;
    printf("%*s%d\n", depth * 2, "", v);          /* indent by depth */

    for (const Edge *e = g->adj[v]; e; e = e->next)
        if (!visited[e->to])
            dfs_visit(g, e->to, visited, depth + 1);
}

/* Cycle detection in a DIRECTED graph needs three states, not two:
   a vertex still on the current path (GRAY) means a back edge = cycle. */
typedef enum { WHITE = 0, GRAY, BLACK } Color;

static bool has_cycle_from(const Graph *g, int v, Color *color)
{
    color[v] = GRAY;                              /* on the current path */
    for (const Edge *e = g->adj[v]; e; e = e->next) {
        if (color[e->to] == GRAY) return true;    /* back edge -> cycle */
        if (color[e->to] == WHITE && has_cycle_from(g, e->to, color)) return true;
    }
    color[v] = BLACK;                             /* fully explored */
    return false;
}

static bool graph_has_cycle(const Graph *g)
{
    Color *color = calloc((size_t)g->nverts, sizeof *color);   /* all WHITE */
    if (!color) return false;

    bool cycle = false;
    for (int v = 0; v < g->nverts && !cycle; v++)
        if (color[v] == WHITE) cycle = has_cycle_from(g, v, color);

    free(color);
    return cycle;
}

int main(void)
{
    /* Undirected:  0-1, 0-2, 1-2, 1-3, 2-3, 3-4 */
    Graph g;
    if (graph_init(&g, 5, false) != 0) return 1;
    graph_add_edge(&g, 0, 1, 1); graph_add_edge(&g, 0, 2, 1);
    graph_add_edge(&g, 1, 2, 1); graph_add_edge(&g, 1, 3, 1);
    graph_add_edge(&g, 2, 3, 1); graph_add_edge(&g, 3, 4, 1);

    int dist[5], parent[5];
    bfs(&g, 0, dist, parent);
    printf("BFS distances from 0: ");
    for (int v = 0; v < 5; v++) printf("%d:%d ", v, dist[v]);
    putchar('\n');

    /* Reconstruct a shortest path by walking parents backwards. */
    printf("path 0 -> 4: ");
    int stack[5], top = 0;
    for (int v = 4; v != -1; v = parent[v]) stack[top++] = v;
    /* Decrement in its own statement: reading and modifying 'top' twice
       in one expression would be unsequenced, and so undefined. */
    while (top) { top--; printf("%d%s", stack[top], top ? " -> " : "\n"); }

    printf("DFS from 0:\n");
    bool visited[5] = {false};
    dfs_visit(&g, 0, visited, 0);
    graph_free(&g);

    /* Directed acyclic vs cyclic. */
    Graph dag;
    graph_init(&dag, 3, true);
    graph_add_edge(&dag, 0, 1, 1); graph_add_edge(&dag, 1, 2, 1);
    printf("DAG has cycle: %s\n", graph_has_cycle(&dag) ? "yes" : "no");
    graph_add_edge(&dag, 2, 0, 1);                /* close the loop */
    printf("after 2->0:   %s\n", graph_has_cycle(&dag) ? "yes" : "no");
    graph_free(&dag);
    return 0;
}

An adjacency matrix, for the dense case:

#include <stdio.h>
#include <stdlib.h>
#include <stdbool.h>

typedef struct { int *m; int n; } Matrix;   /* flat array, indexed m[i*n + j] */

static int mat_init(Matrix *g, int n)
{
    g->m = calloc((size_t)n * (size_t)n, sizeof *g->m);   /* always n^2 */
    if (!g->m) return -1;
    g->n = n;
    return 0;
}

static void mat_add(Matrix *g, int a, int b, int w)
{
    g->m[a * g->n + b] = w;
    g->m[b * g->n + a] = w;                /* undirected: symmetric */
}

/* The matrix's one decisive advantage: O(1) edge existence. */
static bool mat_has_edge(const Matrix *g, int a, int b)
{
    return g->m[a * g->n + b] != 0;
}

int main(void)
{
    Matrix g;
    if (mat_init(&g, 4) != 0) return 1;
    mat_add(&g, 0, 1, 1); mat_add(&g, 0, 2, 1);
    mat_add(&g, 1, 2, 1); mat_add(&g, 2, 3, 1);

    for (int i = 0; i < g.n; i++) {
        for (int j = 0; j < g.n; j++) printf("%d ", g.m[i * g.n + j]);
        putchar('\n');
    }
    printf("edge 0-3? %s\n", mat_has_edge(&g, 0, 3) ? "yes" : "no");

    free(g.m);
    return 0;
}

	Adjacency matrix	Adjacency list
Memory	O(V²) always	O(V + E)
Add edge	O(1)	O(1)
Check edge (u,v)	O(1)	O(degree(u))
Iterate neighbours of u	O(V)	O(degree(u))
BFS / DFS total	O(V²)	O(V + E)
Best when	dense, or edge checks dominate	sparse (almost always)

Key Takeaways

• Choose the representation from the density: adjacency lists cost O(V + E) and suit sparse graphs, which is nearly all real graphs; matrices cost O(V²) but check a specific edge in O(1).
• An undirected edge is two entries in an adjacency list — forgetting the second is the most common graph bug.
• BFS and DFS are the same algorithm with a different frontier container: a queue gives level order and unweighted shortest paths, a stack gives deep-first exploration.
• Both traversals need a visited array; without one, any cycle makes them run forever.
• Directed cycle detection needs three colors, not a boolean — a vertex still on the current path (gray) signals a back edge, while a finished one (black) does not.

🧪 Practice

1. Add graph_degree(g, v) and graph_print(g), then verify that an undirected graph's degrees sum to twice the edge count.
2. Implement an iterative DFS with an explicit stack and confirm it visits the same vertices as the recursive version (the order may differ).
3. Write a topological sort for a DAG using DFS finish times, and make it report an error when the graph contains a cycle.
4. Interview-style: "A social network has 10 million users averaging 200 friends each. Matrix or list?" Hint: compute both memory figures before answering.

<a id="103-generic-and-reusable-code"></a>

10.3 Generic and Reusable Code

Every structure so far was written for one element type. Writing IntVec, StrVec, and TaskVec by hand is how C code rots. This section covers the three techniques C offers for writing a container once — void *, macros, and intrusive links — plus the callback conventions and API design decisions that make a container usable by someone who did not write it.

void Pointer Based Containers

Theory

C has no templates, but it does have a universal pointer type. void * can hold the address of any object, and any object pointer converts to it and back without loss. That is enough to build a container that stores anything: keep void * elements, and let the caller worry about what they point to.

This is exactly how qsort and bsearch work, and the same trade-offs apply. What you gain is one implementation for every type. What you give up is significant and worth naming precisely:

All type checking disappears. The compiler will happily let you push a Person * and read it back as a char *. Nothing catches it — not at compile time, not at run time. The container cannot help you; only discipline can.

Ownership becomes ambiguous. When you push a void *, does the container now own that memory? Must the caller keep it alive? Who frees it? The type says nothing, so the documentation has to, and callers have to read it. This is the single largest source of bugs in void * containers.

Every element is an indirection. Storing void * means the data lives elsewhere, so iterating touches two cache lines per element instead of one, and each element is usually a separate allocation.

There are two distinct designs, and choosing between them matters more than the implementation details:

	Pointer container (void * elements)	Value container (element_size bytes)
Stores	addresses	copies of the data
Element allocation	caller's, one per element	inside the container's block
Memory layout	scattered	contiguous
Ownership	ambiguous, must be documented	unambiguous — the container owns its copy
Element size	not needed	required at construction
Mixed types	possible (rarely wise)	no
Resembles	void ** array	qsort's model

The value container — storing element_size and copying elements in with memcpy — is usually the better design. It keeps data contiguous, and ownership is unambiguous because the container holds its own copy. The pointer container earns its place when elements are large, when they are shared with other structures, or when they are polymorphic.

For a value container, the API cannot return elements by value (C cannot return an unknown type), so it returns void * pointers into its own storage — which are invalidated by any growth, exactly as with a typed dynamic array. This is worth stating loudly in the header.

One safety measure costs almost nothing: a thin, type-safe wrapper. Write the generic container once, then a handful of static inline functions per concrete type that cast for you. Callers use the typed API, get full type checking, and the generic code is still written once.

Examples

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

/* ---------------------------------------------------------------------
   A generic VALUE container: it stores copies, so ownership is clear.
   --------------------------------------------------------------------- */
typedef struct {
    unsigned char *data;      /* unsigned char*: byte arithmetic is legal */
    size_t elem_size;         /* bytes per element, fixed at init         */
    size_t len, cap;
} Vec;

static int vec_init(Vec *v, size_t elem_size)
{
    if (elem_size == 0) return -1;
    v->data = NULL; v->elem_size = elem_size; v->len = v->cap = 0;
    return 0;
}

static void vec_free(Vec *v) { free(v->data); v->data = NULL; v->len = v->cap = 0; }

/* Address of element i: byte arithmetic, which is why data is unsigned char*. */
static void *vec_at(const Vec *v, size_t i)
{
    return i < v->len ? v->data + i * v->elem_size : NULL;
}

static int vec_reserve(Vec *v, size_t want)
{
    if (want <= v->cap) return 0;

    size_t cap = v->cap ? v->cap : 4;
    while (cap < want) {
        if (cap > SIZE_MAX / 2) return -1;
        cap *= 2;
    }
    if (cap > SIZE_MAX / v->elem_size) return -1;      /* byte-size overflow */

    unsigned char *tmp = realloc(v->data, cap * v->elem_size);
    if (!tmp) return -1;
    v->data = tmp; v->cap = cap;
    return 0;
}

/* Copies elem_size bytes IN. The caller's object may die immediately after. */
static int vec_push(Vec *v, const void *elem)
{
    if (v->len == v->cap && vec_reserve(v, v->len + 1) != 0) return -1;
    memcpy(v->data + v->len * v->elem_size, elem, v->elem_size);
    v->len++;
    return 0;
}

/* Copies elem_size bytes OUT, so the caller supplies the destination. */
static int vec_get(const Vec *v, size_t i, void *out)
{
    if (i >= v->len) return -1;
    memcpy(out, v->data + i * v->elem_size, v->elem_size);
    return 0;
}

/* ---------------------------------------------------------------------
   Type-safe wrappers: written once per concrete type, they restore full
   compile-time checking while the generic code stays generic.
   --------------------------------------------------------------------- */
typedef struct { int id; double score; } Record;

static inline int  recvec_init(Vec *v)                    { return vec_init(v, sizeof(Record)); }
static inline int  recvec_push(Vec *v, Record r)          { return vec_push(v, &r); }
static inline Record *recvec_at(const Vec *v, size_t i)   { return (Record *)vec_at(v, i); }

int main(void)
{
    /* The same generic code, three element types, zero duplication. */
    Vec ints;   vec_init(&ints,  sizeof(int));
    Vec doubles;vec_init(&doubles, sizeof(double));
    Vec recs;   recvec_init(&recs);

    for (int i = 0; i < 5; i++)      vec_push(&ints, &i);
    for (double d = 0.5; d < 3; d++) vec_push(&doubles, &d);
    for (int i = 0; i < 3; i++)      recvec_push(&recs, (Record){ i, i * 1.5 });

    int iv;
    vec_get(&ints, 2, &iv);
    printf("ints[2] = %d\n", iv);

    printf("doubles: ");
    for (size_t i = 0; i < doubles.len; i++)
        printf("%.1f ", *(double *)vec_at(&doubles, i));    /* cast on every read */
    putchar('\n');

    /* The typed wrapper needs no cast and catches type errors at compile time. */
    printf("records: ");
    for (size_t i = 0; i < recs.len; i++) {
        Record *r = recvec_at(&recs, i);
        printf("(%d,%.1f) ", r->id, r->score);
    }
    putchar('\n');

    vec_free(&ints); vec_free(&doubles); vec_free(&recs);
    return 0;
}

A pointer container, where ownership must be stated explicitly:

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

/* A container of void* elements. The 'destroy' callback IS the ownership
   contract: non-NULL means the container owns and frees its elements;
   NULL means the caller retains ownership. Documented in the type. */
typedef struct {
    void  **items;
    size_t  len, cap;
    void  (*destroy)(void *);     /* NULL = the container does not own items */
} PtrList;

static void plist_init(PtrList *l, void (*destroy)(void *))
{
    l->items = NULL; l->len = l->cap = 0; l->destroy = destroy;
}

static int plist_push(PtrList *l, void *item)
{
    if (l->len == l->cap) {
        size_t cap = l->cap ? l->cap * 2 : 8;
        void **tmp = realloc(l->items, cap * sizeof *tmp);
        if (!tmp) return -1;
        l->items = tmp; l->cap = cap;
    }
    l->items[l->len++] = item;
    return 0;
}

static void plist_free(PtrList *l)
{
    if (l->destroy)                                  /* only if we own them */
        for (size_t i = 0; i < l->len; i++) l->destroy(l->items[i]);
    free(l->items);
    plist_init(l, NULL);
}

int main(void)
{
    /* OWNING list: strdup'd strings are freed by plist_free. */
    PtrList owned;
    plist_init(&owned, free);
    plist_push(&owned, strdup("alpha"));
    plist_push(&owned, strdup("beta"));
    for (size_t i = 0; i < owned.len; i++) printf("%s ", (char *)owned.items[i]);
    putchar('\n');
    plist_free(&owned);                              /* frees each string too */

    /* BORROWING list: string literals must NOT be freed. */
    PtrList borrowed;
    plist_init(&borrowed, NULL);
    plist_push(&borrowed, (void *)"gamma");
    plist_push(&borrowed, (void *)"delta");
    for (size_t i = 0; i < borrowed.len; i++) printf("%s ", (char *)borrowed.items[i]);
    putchar('\n');
    plist_free(&borrowed);                           /* frees only the array */
    return 0;
}

Key Takeaways

• void * gives one implementation for all types, at the cost of every compile-time type check the language would otherwise perform.
• Prefer a value container storing elem_size bytes over a pointer container: data stays contiguous and the container unambiguously owns its copies.
• Ownership is the hardest part of a void * API — state it in the header, and encode it in the type where you can, such as an optional destroy callback.
• Pointers returned into a value container's storage are invalidated by any growth, exactly as with a typed dynamic array.
• Thin static inline typed wrappers restore full type safety at zero run-time cost while the generic implementation is still written once.

🧪 Practice

1. Add vec_set, vec_remove, and vec_swap_remove to the generic value container, keeping all byte arithmetic correct.
2. Write type-safe wrappers for int and char * vectors, then try to push an int into the string vector and confirm the compiler rejects it.
3. Build a generic foreach(Vec *v, void (*fn)(void *elem, void *ctx), void *ctx) and use it to sum a vector of doubles.
4. Interview-style: "What does a void * container give up compared with a C++ template?" Hint: think about when errors are detected and how many times the code is compiled per type.

Comparator and Destructor Callbacks

Theory

A generic container can store anything, but sooner or later it needs to do something type-specific: compare two elements to sort them, free an element that owns memory, hash a key, or copy an element deeply. It cannot know how — so the caller supplies a function pointer that does.

This is the same mechanism qsort uses, generalized. The container calls back into code you wrote, at the moment it needs type knowledge. Three callbacks cover nearly everything:

Comparator — int (*cmp)(const void *a, const void *b). Returns negative, zero, or positive, and must be a consistent total order. Used for sorting, for ordered containers, and for equality tests.

Destructor — void (*destroy)(void *elem). Releases whatever the element owns. Its presence or absence is the cleanest way to encode ownership: a container given a destructor owns its elements; one given NULL borrows them. Note that free matches this signature exactly, which is why PtrList above could take it directly.

Hash — uint64_t (*hash)(const void *key). Required for generic hash tables, and must agree with the comparator: if two keys compare equal they must hash equal, or lookups will miss entries that are present.

Three design points separate a usable callback API from an awkward one.

Provide a context parameter. A bare int (*cmp)(const void *, const void *) cannot express "sort by whichever field the user selected" without a global variable — which breaks reentrancy and thread safety. Adding a void *ctx parameter that the container passes through untouched solves it cleanly. This is why POSIX has qsort_r and why nearly every modern C callback API carries a context pointer. Design yours with one from the start; adding it later breaks every caller.

Bundle related callbacks into a struct. A container needing compare, hash, destroy, and copy should take one const Ops * rather than four parameters. New capabilities can then be added without changing every call site, and a single static const Ops per type is defined once and reused.

Be explicit about what the container may call and when. May destroy be called on a partially constructed element after an allocation failure? Is the comparator allowed to be called with an element and itself? Unstated answers become version-dependent bugs.

Finally, note the cost. An indirect call through a function pointer usually cannot be inlined, so a generic sort is several times slower than a type-specialized one. That is an acceptable price almost everywhere and unacceptable in a hot inner loop — which is what macro-generated containers, covered next, exist to solve.

Examples

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

/* ---------------------------------------------------------------------
   One Ops struct bundles everything type-specific. Adding a callback
   later does not change any call site.
   --------------------------------------------------------------------- */
typedef struct {
    size_t    size;                                     /* bytes per element */
    int     (*cmp)(const void *a, const void *b, void *ctx);  /* note ctx */
    void    (*destroy)(void *elem);                     /* NULL = not owned  */
    uint64_t (*hash)(const void *elem);                 /* NULL = no hashing */
} Ops;

/* ---------------------------------------------------------------------
   A generic sortable list built on Ops.
   --------------------------------------------------------------------- */
typedef struct {
    unsigned char *data;
    size_t         len, cap;
    const Ops     *ops;
} List;

static void list_init(List *l, const Ops *ops)
{
    l->data = NULL; l->len = l->cap = 0; l->ops = ops;
}

static void list_free(List *l)
{
    if (l->ops->destroy)                       /* the destructor IS the contract */
        for (size_t i = 0; i < l->len; i++)
            l->ops->destroy(l->data + i * l->ops->size);
    free(l->data);
    l->data = NULL; l->len = l->cap = 0;
}

static int list_push(List *l, const void *elem)
{
    if (l->len == l->cap) {
        size_t cap = l->cap ? l->cap * 2 : 8;
        unsigned char *tmp = realloc(l->data, cap * l->ops->size);
        if (!tmp) return -1;
        l->data = tmp; l->cap = cap;
    }
    memcpy(l->data + l->len * l->ops->size, elem, l->ops->size);
    l->len++;
    return 0;
}

/* Insertion sort: short, and it shows the ctx threading clearly.
   ctx flows from the caller, through the container, into the comparator,
   with the container never inspecting it. */
static void list_sort(List *l, void *ctx)
{
    size_t         sz  = l->ops->size;
    unsigned char *tmp = malloc(sz);
    if (!tmp) return;

    for (size_t i = 1; i < l->len; i++) {
        memcpy(tmp, l->data + i * sz, sz);                 /* lift element i */
        size_t j = i;
        while (j > 0 && l->ops->cmp(l->data + (j - 1) * sz, tmp, ctx) > 0) {
            memcpy(l->data + j * sz, l->data + (j - 1) * sz, sz);   /* shift up */
            j--;
        }
        memcpy(l->data + j * sz, tmp, sz);                 /* drop it in */
    }
    free(tmp);
}

/* ---------------------------------------------------------------------
   A concrete element type, with its callbacks defined once.
   --------------------------------------------------------------------- */
typedef struct { char *name; int age; double salary; } Person;

typedef enum { BY_NAME, BY_AGE, BY_SALARY } SortKey;

/* One comparator handles every field, because ctx carries the choice.
   Without ctx this would need a global variable or three comparators. */
static int person_cmp(const void *a, const void *b, void *ctx)
{
    const Person *p = a, *q = b;
    SortKey key = *(const SortKey *)ctx;

    switch (key) {
    case BY_NAME:   return strcmp(p->name, q->name);
    case BY_AGE:    return (p->age > q->age) - (p->age < q->age);
    case BY_SALARY: return (p->salary > q->salary) - (p->salary < q->salary);
    }
    return 0;
}

/* The element owns its name, so the destructor must free it. */
static void person_destroy(void *elem)
{
    Person *p = elem;
    free(p->name);
    p->name = NULL;                       /* defensive: catch a double free */
}

static uint64_t person_hash(const void *elem)
{
    const Person *p = elem;
    uint64_t h = 1469598103934665603ULL;
    for (const char *s = p->name; *s; s++) { h ^= (unsigned char)*s; h *= 1099511628211ULL; }
    return h;
    /* Must agree with person_cmp under BY_NAME: equal names -> equal hashes. */
}

/* Defined once, referenced everywhere. */
static const Ops PERSON_OPS = {
    .size = sizeof(Person),
    .cmp = person_cmp,
    .destroy = person_destroy,
    .hash = person_hash,
};

static void dump(const List *l, const char *label)
{
    printf("%-18s", label);
    for (size_t i = 0; i < l->len; i++) {
        const Person *p = (const Person *)(l->data + i * l->ops->size);
        printf("%s(%d) ", p->name, p->age);
    }
    putchar('\n');
}

int main(void)
{
    List people;
    list_init(&people, &PERSON_OPS);

    const char *names[] = { "carol", "alice", "bob" };
    const int   ages[]  = { 41, 29, 35 };

    for (int i = 0; i < 3; i++) {
        Person p = { strdup(names[i]), ages[i], 50000.0 + i * 1000 };
        if (!p.name || list_push(&people, &p) != 0) { free(p.name); break; }
        /* Ownership of p.name has moved into the list -- do NOT free it here. */
    }

    dump(&people, "unsorted:");

    SortKey key = BY_NAME;  list_sort(&people, &key); dump(&people, "by name:");
    key = BY_AGE;           list_sort(&people, &key); dump(&people, "by age:");

    printf("hash of first: %llu\n",
           (unsigned long long)people.ops->hash(people.data));

    list_free(&people);          /* calls person_destroy on every element */
    return 0;
}

Why the context parameter is not optional:

#include <stdio.h>
#include <stdlib.h>

/* WITHOUT ctx, a configurable comparator needs shared mutable state. */
static int g_descending = 0;                    /* a global: not thread-safe */

static int cmp_global(const void *a, const void *b)
{
    int x = *(const int *)a, y = *(const int *)b;
    int r = (x > y) - (x < y);
    return g_descending ? -r : r;               /* two threads sorting in
                                                   different directions race */
}

/* WITH ctx, the direction travels with the call: reentrant and thread-safe. */
static int cmp_ctx(const void *a, const void *b, void *ctx)
{
    int x = *(const int *)a, y = *(const int *)b;
    int r = (x > y) - (x < y);
    return *(const int *)ctx ? -r : r;
}

int main(void)
{
    int v[] = { 3, 1, 2 };

    g_descending = 1;
    qsort(v, 3, sizeof *v, cmp_global);         /* standard qsort has no ctx */
    printf("%d %d %d\n", v[0], v[1], v[2]);     /* 3 2 1 */

    int descending = 0;
    printf("cmp_ctx(1,2) ascending  = %d\n", cmp_ctx(&v[2], &v[1], &descending));
    descending = 1;
    printf("cmp_ctx(1,2) descending = %d\n", cmp_ctx(&v[2], &v[1], &descending));
    return 0;
}

Callback	Signature	Purpose	Omitting it means
Compare	int (*)(const void *, const void *, void *ctx)	ordering, equality	no sorting or ordered lookup
Destroy	void (*)(void *)	release owned resources	the container borrows, caller frees
Hash	uint64_t (*)(const void *)	bucket selection	no hash-table use
Copy	int (*)(void *dst, const void *src)	deep copy	shallow memcpy only

Key Takeaways

• Callbacks supply the type-specific behavior a generic container cannot know: comparing, destroying, hashing, and copying.
• Always include a void *ctx parameter the container passes through untouched — without it, configurable comparators need globals, which breaks reentrancy and thread safety.
• The presence of a destructor is the cleanest encoding of ownership: with one, the container owns its elements; with NULL, it borrows them.
• Bundle related callbacks in an Ops struct so new capabilities can be added without changing every call site.
• A hash callback must agree with the comparator — equal elements must hash equally, or lookups will miss entries that are present.

🧪 Practice

1. Add a copy callback to Ops and implement list_clone that deep-copies every element, correctly handling a failure partway through.
2. Write comparators for a Person list that sort by salary descending and then by name ascending, using only ctx to select between orderings.
3. Replace the insertion sort in list_sort with a call to qsort, and explain why the ctx parameter cannot be passed through the standard qsort.
4. Interview-style: "Why do modern C callback APIs almost always take a context pointer?" Hint: consider two threads calling the same function with different configurations.

Macro-Generated Containers

Theory

The void * approach costs type safety and an unindexable indirect call per comparison. There is another way to get generic containers in C, and it operates at a different stage of the build: generate real, typed code with the preprocessor.

The idea is to write the container once as a macro whose parameter is a type, then instantiate it per element type. DEFINE_VEC(int) expands into a complete int vector — a real struct, real functions taking int, real comparisons the compiler can inline. This is C's closest analogue to C++ templates, and the resulting code is exactly what you would have written by hand.

The gains are the mirror image of void *'s losses:

• Full type checking. Pushing a double into an int vector is a compile error.
• No indirection. Elements are stored by value in a typed array; comparisons are inline operators, not calls through a pointer.
• Optimizable. The compiler sees concrete types and can vectorize, unroll, and inline. A macro-generated sort typically runs several times faster than qsort.

The costs are equally real:

• Code bloat. Each instantiation is a full copy of every function. Ten types means ten copies in the binary.
• Miserable diagnostics. An error inside a macro expansion is reported at the instantiation line, often as a wall of text about tokens you never wrote.
• Undebuggable. The whole expansion is one logical line, so a debugger cannot step through it and breakpoints inside it are impossible.
• Awkward to write. Every line needs a trailing backslash, and the code cannot be compiled or tested on its own.

Two preprocessor operators make this possible:

• ## (token pasting) joins tokens to build names: vec_##T##_push becomes vec_int_push when T is int. This is how each instantiation gets distinct function names.
• # (stringizing) turns a parameter into a string literal, useful for generating format strings and debug output.

A crucial detail: the type must be a single token to paste into a name. unsigned int and char * will not work directly. The standard workaround is a typedef first (typedef char *str;), or a separate name parameter (DEFINE_VEC(char *, str)).

The alternative style, used by several well-known single-header libraries, is the X-macro / include trick: write the container in a header that reads #define T ... from the includer, then #include it once per type. It keeps the code readable — real lines, no backslashes, and it can be syntax-highlighted — at the cost of an unusual include pattern.

In practice, the choice is: use void * by default for lower binary size and comprehensible errors; reach for macro generation when profiling shows the indirect calls matter, or when the type safety is worth the diagnostics.

Examples

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

/* ---------------------------------------------------------------------
   DEFINE_VEC(T) expands into a complete, typed dynamic array.
   Every line but the last needs a trailing backslash, and nothing --
   not even a space -- may follow one.
   --------------------------------------------------------------------- */
#define DEFINE_VEC(T)                                                        \
                                                                             \
    typedef struct {                                                         \
        T     *data;                                                         \
        size_t len, cap;                                                     \
    } Vec_##T;                        /* ## pastes: Vec_int, Vec_double */   \
                                                                             \
    static inline void vec_##T##_init(Vec_##T *v)                            \
    {                                                                        \
        v->data = NULL; v->len = v->cap = 0;                                 \
    }                                                                        \
                                                                             \
    static inline void vec_##T##_free(Vec_##T *v)                            \
    {                                                                        \
        free(v->data); v->data = NULL; v->len = v->cap = 0;                  \
    }                                                                        \
                                                                             \
    static inline int vec_##T##_push(Vec_##T *v, T value)                    \
    {                                                                        \
        if (v->len == v->cap) {                                              \
            size_t cap = v->cap ? v->cap * 2 : 8;                            \
            T *tmp = realloc(v->data, cap * sizeof *tmp);                    \
            if (!tmp) return -1;                                             \
            v->data = tmp; v->cap = cap;                                     \
        }                                                                    \
        v->data[v->len++] = value;    /* a real typed assignment */          \
        return 0;                                                            \
    }                                                                        \
                                                                             \
    static inline int vec_##T##_pop(Vec_##T *v, T *out)                      \
    {                                                                        \
        if (v->len == 0) return -1;                                          \
        *out = v->data[--v->len];                                            \
        return 0;                                                            \
    }                                                                        \
                                                                             \
    /* The comparison is an inline operator, not a call through a            \
       function pointer -- this is the whole performance argument. */        \
    static inline void vec_##T##_sort(Vec_##T *v)                            \
    {                                                                        \
        for (size_t i = 1; i < v->len; i++) {                                \
            T key = v->data[i];                                              \
            size_t j = i;                                                    \
            while (j > 0 && v->data[j - 1] > key) {                          \
                v->data[j] = v->data[j - 1];                                 \
                j--;                                                         \
            }                                                                \
            v->data[j] = key;                                                \
        }                                                                    \
    }

/* A multi-token type must be typedef'd to a single token before pasting. */
typedef char *str;

/* Each line generates an entire typed container. */
DEFINE_VEC(int)
DEFINE_VEC(double)
DEFINE_VEC(str)

int main(void)
{
    Vec_int vi;
    vec_int_init(&vi);
    int values[] = { 5, 2, 9, 1, 7 };
    for (int i = 0; i < 5; i++) vec_int_push(&vi, values[i]);

    vec_int_sort(&vi);
    printf("ints: ");
    for (size_t i = 0; i < vi.len; i++) printf("%d ", vi.data[i]);
    putchar('\n');

    Vec_double vd;
    vec_double_init(&vd);
    vec_double_push(&vd, 3.5);
    vec_double_push(&vd, 1.25);
    vec_double_sort(&vd);
    printf("doubles: %.2f %.2f\n", vd.data[0], vd.data[1]);

    /* vec_int_push(&vi, 3.7);  <-- would be a type ERROR, caught at compile
       time. The void* version would silently accept it. */

    Vec_str vs;
    vec_str_init(&vs);
    vec_str_push(&vs, "hello");
    printf("strings: %s\n", vs.data[0]);

    vec_int_free(&vi); vec_double_free(&vd); vec_str_free(&vs);
    return 0;
}

A macro-generated intrusive-free linked list, showing stringizing alongside pasting:

#include <stdio.h>
#include <stdlib.h>

#define DEFINE_LIST(T, FMT)                                                  \
                                                                             \
    typedef struct Node_##T {                                                \
        T                value;                                              \
        struct Node_##T *next;                                               \
    } Node_##T;                                                              \
                                                                             \
    static inline int list_##T##_push(Node_##T **head, T value)              \
    {                                                                        \
        Node_##T *n = malloc(sizeof *n);                                     \
        if (!n) return -1;                                                   \
        n->value = value; n->next = *head; *head = n;                        \
        return 0;                                                            \
    }                                                                        \
                                                                             \
    static inline void list_##T##_print(const Node_##T *head)                \
    {                                                                        \
        /* # stringizes the type name into the label. */                     \
        printf("%s: ", #T);                                                  \
        for (const Node_##T *n = head; n; n = n->next)                       \
            printf(FMT " ", n->value);                                       \
        putchar('\n');                                                       \
    }                                                                        \
                                                                             \
    static inline void list_##T##_free(Node_##T *head)                       \
    {                                                                        \
        while (head) { Node_##T *next = head->next; free(head); head = next; }\
    }

DEFINE_LIST(int, "%d")
DEFINE_LIST(float, "%.1f")

int main(void)
{
    Node_int *ints = NULL;
    for (int i = 1; i <= 3; i++) list_int_push(&ints, i * 11);
    list_int_print(ints);                  /* int: 33 22 11 */
    list_int_free(ints);

    Node_float *floats = NULL;
    list_float_push(&floats, 2.5f);
    list_float_push(&floats, 1.5f);
    list_float_print(floats);              /* float: 1.5 2.5 */
    list_float_free(floats);
    return 0;
}

# Inspect an expansion when a macro-generated error makes no sense.
# -E stops after preprocessing; a formatter makes the result readable.
$ gcc -E prog.c | sed -n '/Vec_int/,/^$/p' | head -20

# Without formatting, the whole instantiation is ONE line -- which is also
# why a debugger cannot step through it and breakpoints inside it fail.

	void * container	Macro-generated container
Type checking	none	full, at compile time
Element storage	void * or opaque bytes	the real type, by value
Comparison	indirect call	inlined operator
Binary size	one copy	one copy per type
Error messages	normal	expansion-site walls of text
Debugger stepping	normal	impossible inside the macro
Runtime type flexibility	can hold mixed types	fixed at compile time
Best when	many types, size matters	few types, speed matters

Key Takeaways

• Macro generation produces real typed code per element type, restoring full type checking and letting the compiler inline comparisons that a void * container must make through a pointer.
• ## pastes tokens to build per-type names and # stringizes them; the type must be a single token, so multi-word types need a typedef first.
• The costs are code bloat, diagnostics reported at the instantiation site, and the inability to step through the expansion in a debugger.
• Inspect a confusing expansion with gcc -E; it is the only practical way to debug a macro-generated container.
• Default to void * for flexibility and comprehensible errors, and switch to macro generation when profiling shows the indirect calls actually matter.

🧪 Practice

1. Extend DEFINE_VEC with insert, remove, and find, then instantiate it for a struct Point typedef'd to a single token.
2. Deliberately introduce a syntax error inside DEFINE_VEC and read the resulting message; then use gcc -E to locate the real problem.
3. Benchmark sorting a million ints with qsort against vec_int_sort upgraded to quicksort. Explain the difference in terms of the comparison.
4. Interview-style: "When would you choose macro-generated containers over void * ones?" Hint: name what each approach costs and which cost your hot loop actually pays.

Intrusive Data Structures

Theory

Every container so far contains its elements: the list allocates a node that holds your data, or the vector copies your data into its array. An intrusive structure inverts this. The link fields live inside your own struct, and the container is just the code that manipulates them.

   NON-INTRUSIVE (the list owns nodes that point at your data)

     list -> +--------+     +--------+
             | next   |---->| next   |---> NULL
             | data * |     | data * |
             +--------+     +--------+
                  |              |
                  v              v
             +--------+     +--------+
             | Task   |     | Task   |     two allocations per element
             +--------+     +--------+     two pointer hops to reach data

   INTRUSIVE (the links live inside your struct)

     list -> +-----------+       +-----------+
             | Task      |       | Task      |
             |  id       |       |  id       |
             |  name     |       |  name     |
             |  link.next|------>|  link.next|---> NULL
             +-----------+       +-----------+

             one allocation, data reached directly, and the SAME Task
             can carry a second link field to sit in a second list

The consequences are substantial enough that the Linux kernel, BSD's <sys/queue.h>, and most embedded systems use intrusive lists almost exclusively:

One allocation instead of two. The node is the element. Insertion cannot fail on allocation, because there is nothing to allocate — which matters enormously in kernels, interrupt handlers, and any code where failure has no good recovery.

No indirection. The link and the data are in the same cache line, so traversal touches half as much memory.

One element, several containers. Add two link fields and the same object can sit in a free list and a hash bucket simultaneously, or in both an LRU list and a priority queue. A non-intrusive container cannot express this without duplicating pointers to the element.

O(1) removal given only the element. You already hold the object; its links are right there. No lookup needed.

The cost is a genuine coupling: your struct must know about the container, so the container cannot store types you do not control. You cannot put an int or a third-party struct in an intrusive list without wrapping it.

The technique that makes it work is recovering the containing struct from a pointer to its embedded link. offsetof (from <stddef.h>) gives the byte distance from the start of a struct to a member; subtracting it from the member's address yields the struct's address. That is the famous container_of macro:

#define container_of(ptr, type, member) \
    ((type *)((char *)(ptr) - offsetof(type, member)))

Because the link fields are identical for every element type, the traversal code is written once and is genuinely type-agnostic — no void *, no callbacks, no code duplication per type.

Two cautions. container_of is only valid when ptr really points at that member of that type; get the type wrong and you compute a bogus address with no diagnostic. And ownership is entirely the caller's: the container never allocates or frees, so removing an element from a list does not free it.

Examples

#include <stdio.h>
#include <stdlib.h>
#include <stddef.h>      /* offsetof */
#include <string.h>

/* ---------------------------------------------------------------------
   The generic link. Every element embeds one (or several) of these.
   This is the Linux kernel's list_head, simplified.
   --------------------------------------------------------------------- */
typedef struct Link { struct Link *prev, *next; } Link;

/* Recover the enclosing struct from a pointer to its embedded Link.
   'member' names WHICH link, so an element in two lists is unambiguous. */
#define container_of(ptr, type, member) \
    ((type *)((char *)(ptr) - offsetof(type, member)))

/* A circular list with a sentinel: next/prev are never NULL, so every
   operation is branch-free. */
static void link_init(Link *l)          { l->prev = l->next = l; }

static void link_insert_before(Link *at, Link *n)
{
    n->prev = at->prev; n->next = at;
    at->prev->next = n; at->prev = n;
}

static void link_remove(Link *n)
{
    n->prev->next = n->next;
    n->next->prev = n->prev;
    link_init(n);                        /* self-link: removing twice is safe */
}

static int link_empty(const Link *head) { return head->next == head; }

/* Iterate the links of a list bounded by its sentinel. */
#define list_for_each(pos, head) \
    for (Link *pos = (head)->next; pos != (head); pos = pos->next)

/* Iterate safely when the body may remove the current element. */
#define list_for_each_safe(pos, tmp, head)                       \
    for (Link *pos = (head)->next, *tmp = pos->next;             \
         pos != (head); pos = tmp, tmp = pos->next)

/* ---------------------------------------------------------------------
   An element that lives in TWO lists at once -- the thing a non-intrusive
   container cannot express without duplicating the element.
   --------------------------------------------------------------------- */
typedef struct {
    int  id;
    char name[24];
    int  priority;

    Link all_link;        /* membership in the "every task" list */
    Link ready_link;      /* membership in the "runnable" list   */
} Task;

static Task *task_new(int id, const char *name, int priority)
{
    Task *t = malloc(sizeof *t);          /* ONE allocation: node and data */
    if (!t) return NULL;
    t->id = id;
    snprintf(t->name, sizeof t->name, "%s", name);
    t->priority = priority;
    link_init(&t->all_link);
    link_init(&t->ready_link);
    return t;
}

int main(void)
{
    Link all_tasks, ready;
    link_init(&all_tasks);
    link_init(&ready);

    const char *names[] = { "compile", "test", "deploy", "notify" };
    for (int i = 0; i < 4; i++) {
        Task *t = task_new(i, names[i], i % 2);
        if (!t) break;

        /* Insertion CANNOT FAIL -- there is nothing to allocate. */
        link_insert_before(&all_tasks, &t->all_link);
        if (t->priority == 1)
            link_insert_before(&ready, &t->ready_link);   /* the SAME object */
    }

    printf("all tasks:\n");
    list_for_each(p, &all_tasks) {
        Task *t = container_of(p, Task, all_link);       /* link -> element */
        printf("  %d %-8s prio=%d\n", t->id, t->name, t->priority);
    }

    printf("ready tasks:\n");
    list_for_each(p, &ready) {
        Task *t = container_of(p, Task, ready_link);     /* the OTHER link */
        printf("  %d %s\n", t->id, t->name);
    }

    /* Remove from one list without touching the other, and without any
       lookup -- we already hold the element. */
    list_for_each_safe(p, tmp, &ready) {
        Task *t = container_of(p, Task, ready_link);
        if (t->id == 1) {
            link_remove(&t->ready_link);                 /* still in all_tasks */
            printf("unqueued %s (still tracked: %s)\n", t->name,
                   link_empty(&t->all_link) ? "no" : "yes");
        }
    }

    /* The container never owns anything: freeing is entirely ours. */
    list_for_each_safe(p, tmp, &all_tasks) {
        Task *t = container_of(p, Task, all_link);
        link_remove(&t->all_link);
        link_remove(&t->ready_link);
        free(t);
    }
    printf("all empty: %s\n", link_empty(&all_tasks) ? "yes" : "no");
    return 0;
}

How container_of computes the address:

#include <stdio.h>
#include <stddef.h>

typedef struct Link { struct Link *prev, *next; } Link;

typedef struct {
    int  id;          /* offset 0  */
    char name[24];    /* offset 4  */
    Link hook;        /* offset 32 (after padding) */
} Item;

#define container_of(ptr, type, member) \
    ((type *)((char *)(ptr) - offsetof(type, member)))

int main(void)
{
    Item it = { 7, "example", { NULL, NULL } };
    Link *l = &it.hook;                    /* all the container ever sees */

    printf("offsetof(Item, hook) = %zu\n", offsetof(Item, hook));
    printf("&it       = %p\n", (void *)&it);
    printf("&it.hook  = %p\n", (void *)l);

    /* Subtract the member's offset from its address to recover the struct. */
    Item *back = container_of(l, Item, hook);
    printf("recovered = %p  id=%d name=%s\n", (void *)back, back->id, back->name);
    printf("identical: %s\n", back == &it ? "yes" : "no");
    return 0;
}

	Non-intrusive	Intrusive
Allocations per element	2 (node + data)	1 (the element itself)
Insertion can fail	yes (malloc)	no
Pointer hops to reach data	2	1
Element in multiple containers	needs duplicate pointers	one extra link field each
Remove given the element	needs a lookup	O(1), links are right there
Works with types you do not control	yes	no — the struct must embed the link
Type safety	via void * or macros	via container_of, unchecked

Key Takeaways

• An intrusive structure puts the link fields inside your struct, so the element is the node — one allocation, no indirection, and insertion that cannot fail.
• container_of recovers the enclosing struct from an embedded link by subtracting offsetof, which is what lets one traversal implementation serve every element type.
• Embedding several link fields lets one object belong to several containers at once, which non-intrusive containers cannot express without duplicating pointers.
• The container never allocates or frees, so ownership stays entirely with the caller; removing an element does not destroy it.
• The cost is coupling — your struct must embed the container's link — so intrusive structures cannot hold primitives or third-party types without a wrapper.

🧪 Practice

1. Add link_insert_after and list_count, then build an intrusive LRU cache that moves an accessed element to the front in O(1).
2. Give Task a third link field and place the same task in an all-tasks list, a ready list, and a per-owner list simultaneously.
3. Write list_for_each_entry(pos, head, type, member) that yields typed element pointers directly, hiding the container_of call from the loop body.
4. Interview-style: "Why does the Linux kernel use intrusive lists everywhere?" Hint: consider what a non-intrusive insertion must do that can fail, and what a kernel can do when it does.

API Design for Libraries

Theory

A container that only its author can use is not reusable, no matter how good the algorithm is. Turning working code into a library is a distinct skill, and in C — with no namespaces, no destructors, and no exceptions — the conventions carry all the weight the language does not.

Prefix everything. C has one global namespace, so every exported symbol needs a project prefix: vec_push, not push. Without it, linking two libraries that both define list_init fails, or worse, silently binds to the wrong one. The same applies to macros and typedefs. Make every non-exported function static.

Hide the representation. If callers can see your struct's fields, they will read them, and you can never change the layout again without breaking every user. The opaque pointer (or handle) pattern declares the type in the header without defining it:

typedef struct Vec Vec;         /* in the header: an incomplete type */

Callers can hold a Vec * but cannot dereference it, cannot see its size, and cannot allocate one on the stack — so they must use your vec_create. In exchange you can change everything about the layout without recompiling their code. The cost is one heap allocation per object and no inlining across the boundary; for performance-critical small types, exposing the struct and documenting the fields as private is the usual compromise.

Pair every constructor with exactly one destructor. vec_create / vec_destroy. Make the destructor accept NULL (as free does), so error paths do not need a check. Never require the caller to release something through a different mechanism than the one that produced it.

Make ownership explicit in the names and the docs. Does vec_push copy the string or take it? Does vec_get return a borrowed pointer valid until the next mutation, or a copy the caller must free? Every function that takes or returns a pointer needs a documented answer. Conventions help: a _copy suffix for functions that duplicate, _ref or a const return for borrowed values, and _take or _own for transfer.

Report errors consistently. One convention for the whole library, as in Chapter 9. Say what happens on failure — in particular whether the object is still usable, which is what decides if the caller can retry.

Keep the header self-contained and minimal. It must compile when included first and alone. Include only what its declarations need, and put implementation-only includes in the .c file. Wrap it in an include guard and, for C++ consumers, extern "C".

Design for testability and the future. Take a context parameter in callbacks. Let callers supply allocators if the library might be used in an embedded or arena-based setting. Version the library, and treat every exported symbol as a promise you must keep.

Examples

A complete public header showing the opaque-handle pattern:

/* ============================== vec.h ============================== */
#ifndef VEC_H
#define VEC_H

#include <stddef.h>      /* size_t -- self-contained: include what you use */

#ifdef __cplusplus
extern "C" {             /* let C++ consumers link against C symbols */
#endif

/* Opaque handle: declared, never defined here. Callers can hold a Vec*
   but cannot see the fields, cannot know sizeof(Vec), and cannot put one
   on the stack -- so the layout is free to change without breaking them. */
typedef struct Vec Vec;

/* One error convention for the entire library. */
typedef enum {
    VEC_OK = 0,
    VEC_ERR_ALLOC   = -1,   /* out of memory; the vector is unchanged */
    VEC_ERR_BOUNDS  = -2,   /* index out of range; the vector is unchanged */
    VEC_ERR_INVALID = -3    /* NULL handle or a nonsensical argument */
} VecStatus;

/* Human-readable text for a status code. The returned string is static:
   the caller must NOT free it. */
const char *vec_strerror(VecStatus status);

/* --- lifecycle: exactly one constructor, exactly one destructor ------
 * vec_create: returns NULL on allocation failure.
 *   elem_size must be > 0. If 'destroy' is non-NULL the vector OWNS its
 *   elements and calls destroy on each during vec_destroy; if it is NULL
 *   the vector only stores bytes and owns nothing beyond its own buffer.
 * vec_destroy: accepts NULL (a no-op), so error paths need no check.
 */
Vec *vec_create(size_t elem_size, void (*destroy)(void *elem));
void vec_destroy(Vec *v);

/* --- capacity ------------------------------------------------------- */
size_t    vec_len(const Vec *v);
size_t    vec_capacity(const Vec *v);
VecStatus vec_reserve(Vec *v, size_t want);

/* --- element access -------------------------------------------------
 * vec_push COPIES elem_size bytes from 'elem'; the caller keeps ownership
 *   of the object it passed and may destroy it immediately after.
 * vec_at returns a BORROWED pointer into the vector's own storage. It is
 *   invalidated by any push, reserve, or destroy. Do not free it.
 * vec_get COPIES the element out into caller-supplied storage, which is
 *   the safe choice when the vector may be modified afterwards.
 */
VecStatus vec_push(Vec *v, const void *elem);
void      *vec_at(const Vec *v, size_t index);
VecStatus vec_get(const Vec *v, size_t index, void *out);

/* --- iteration ------------------------------------------------------
 * 'ctx' is passed through untouched, so callbacks need no globals.
 * Returning non-zero from fn stops the iteration early.
 */
VecStatus vec_foreach(const Vec *v, int (*fn)(void *elem, void *ctx), void *ctx);

#ifdef __cplusplus
}
#endif

#endif /* VEC_H */

The implementation, where the struct actually lives:

/* ============================== vec.c ============================== */
#include "vec.h"
#include <stdlib.h>
#include <string.h>
#include <stdint.h>

/* The definition is here, not in the header: callers cannot depend on it. */
struct Vec {
    unsigned char *data;
    size_t         elem_size;
    size_t         len, cap;
    void         (*destroy)(void *elem);
};

/* Internal helpers are static: they never reach the global namespace. */
static void *slot(const Vec *v, size_t i) { return v->data + i * v->elem_size; }

const char *vec_strerror(VecStatus status)
{
    switch (status) {
    case VEC_OK:            return "success";
    case VEC_ERR_ALLOC:     return "allocation failed";
    case VEC_ERR_BOUNDS:    return "index out of bounds";
    case VEC_ERR_INVALID:   return "invalid argument";
    }
    return "unknown error";
}

Vec *vec_create(size_t elem_size, void (*destroy)(void *elem))
{
    if (elem_size == 0) return NULL;

    Vec *v = malloc(sizeof *v);
    if (!v) return NULL;

    v->data = NULL;
    v->elem_size = elem_size;
    v->len = v->cap = 0;
    v->destroy = destroy;
    return v;
}

void vec_destroy(Vec *v)
{
    if (!v) return;                       /* NULL-tolerant, like free() */

    if (v->destroy)                       /* only if we were told we own them */
        for (size_t i = 0; i < v->len; i++) v->destroy(slot(v, i));

    free(v->data);
    free(v);
}

size_t vec_len(const Vec *v)      { return v ? v->len : 0; }
size_t vec_capacity(const Vec *v) { return v ? v->cap : 0; }

VecStatus vec_reserve(Vec *v, size_t want)
{
    if (!v) return VEC_ERR_INVALID;
    if (want <= v->cap) return VEC_OK;

    size_t cap = v->cap ? v->cap : 4;
    while (cap < want) {
        if (cap > SIZE_MAX / 2) return VEC_ERR_ALLOC;
        cap *= 2;
    }
    if (cap > SIZE_MAX / v->elem_size) return VEC_ERR_ALLOC;

    unsigned char *tmp = realloc(v->data, cap * v->elem_size);
    if (!tmp) return VEC_ERR_ALLOC;       /* v is UNCHANGED and still usable */

    v->data = tmp;
    v->cap  = cap;
    return VEC_OK;
}

VecStatus vec_push(Vec *v, const void *elem)
{
    if (!v || !elem) return VEC_ERR_INVALID;

    if (v->len == v->cap) {
        VecStatus st = vec_reserve(v, v->len + 1);
        if (st != VEC_OK) return st;
    }
    memcpy(slot(v, v->len), elem, v->elem_size);   /* COPY: caller keeps its object */
    v->len++;
    return VEC_OK;
}

void *vec_at(const Vec *v, size_t index)
{
    if (!v || index >= v->len) return NULL;
    return slot(v, index);                          /* BORROWED, not owned */
}

VecStatus vec_get(const Vec *v, size_t index, void *out)
{
    if (!v || !out)        return VEC_ERR_INVALID;
    if (index >= v->len)   return VEC_ERR_BOUNDS;
    memcpy(out, slot(v, index), v->elem_size);
    return VEC_OK;
}

VecStatus vec_foreach(const Vec *v, int (*fn)(void *elem, void *ctx), void *ctx)
{
    if (!v || !fn) return VEC_ERR_INVALID;
    for (size_t i = 0; i < v->len; i++)
        if (fn(slot(v, i), ctx) != 0) break;        /* non-zero stops early */
    return VEC_OK;
}

Using it, with the header's promises made concrete:

/* ============================== main.c ============================== */
#include "vec.h"
#include <stdio.h>
#include <stdlib.h>
#include <string.h>

/* Elements own a heap string, so the vector needs a destructor. */
typedef struct { int id; char *label; } Item;

static void item_destroy(void *elem) { free(((Item *)elem)->label); }

static int print_item(void *elem, void *ctx)
{
    Item *it = elem;
    int *limit = ctx;                       /* ctx: no global needed */
    printf("  %d: %s\n", it->id, it->label);
    return --(*limit) <= 0 ? 1 : 0;         /* non-zero stops the iteration */
}

int main(void)
{
    Vec *v = vec_create(sizeof(Item), item_destroy);   /* owning vector */
    if (!v) { fprintf(stderr, "out of memory\n"); return EXIT_FAILURE; }

    const char *labels[] = { "alpha", "beta", "gamma", "delta" };
    for (int i = 0; i < 4; i++) {
        Item it = { i, strdup(labels[i]) };
        if (!it.label) break;

        VecStatus st = vec_push(v, &it);
        if (st != VEC_OK) {
            fprintf(stderr, "push: %s\n", vec_strerror(st));
            free(it.label);                 /* push failed: still OURS to free */
            break;
        }
        /* push succeeded: the copy inside the vector owns it.label now. */
    }

    printf("len=%zu cap=%zu\n", vec_len(v), vec_capacity(v));

    int limit = 2;
    printf("first two:\n");
    vec_foreach(v, print_item, &limit);

    /* Borrowed pointer: valid only until the next mutation. */
    Item *first = vec_at(v, 0);
    if (first) printf("first label: %s\n", first->label);

    vec_destroy(v);          /* calls item_destroy on every element */
    vec_destroy(NULL);       /* documented as safe */
    return EXIT_SUCCESS;
}

Decision	Options	Guidance
Struct visibility	opaque handle vs. exposed	opaque unless inlining or stack allocation matters
Allocation	library allocates vs. caller provides storage	library-allocates by default; caller-provided for embedded
Errors	status enum, errno-style, NULL	one convention, documented, used everywhere
Element ownership	copy in vs. take pointer	copy by default; a destructor callback makes taking explicit
Returned pointers	borrowed vs. owned	borrowed with a documented lifetime; say what invalidates it
Naming	prefixed vs. bare	always prefixed — C has one namespace
Callbacks	with ctx vs. without	always with ctx

Key Takeaways

• Prefix every exported symbol and mark everything else static — C has a single global namespace and no other protection against collisions.
• An opaque handle (typedef struct Vec Vec; with no definition in the header) lets you change the layout without recompiling callers, at the cost of an allocation and no cross-boundary inlining.
• Pair exactly one constructor with one destructor, make the destructor accept NULL, and never require release through a different mechanism than the one that allocated.
• Document ownership for every pointer crossing the API: what is copied, what is borrowed, what invalidates a returned pointer, and who frees what when a call fails partway.
• Use one error convention throughout, state whether the object remains usable after a failure, and give every callback a void *ctx so callers never need globals.

🧪 Practice

1. Add vec_pop, vec_remove, and vec_clear to the library, updating the header documentation to state the ownership and invalidation rules for each.
2. Split an existing single-file container into foo.h and foo.c with an opaque handle, and verify that main.c still compiles when the struct's field order changes.
3. Write a test that exercises every error path — NULL handle, out-of-bounds index, zero element size — and confirm the vector remains usable after each.
4. Interview-style: "What are the trade-offs of an opaque pointer API in C?" Hint: weigh what the caller can no longer do against what you become free to change.

---