Lists, Pools & Arenas

Lists, intrusive nodes, pools, arenas, and fragmentation

Intrusive lists store linkage inside caller-owned objects. Fixed-block pools recycle equal-sized objects in constant time. Arenas perform aligned bump allocation with bulk reset. These patterns provide dynamic lifetimes while retaining a predictable maximum footprint.

Linked lists make insertion and removal cheap only when you already have the node or position. Search remains O(n), every node costs pointers, and pointer chasing destroys locality. Arrays are usually better unless stable addresses, intrusive membership, or frequent O(1) splice operations are the real requirement.

A fixed-block pool threads its free list through unused blocks. Allocation removes the head; free validates address, alignment, membership, and allocation state before returning a block. O(1) alone is insufficient if double free can create a cycle or two clients can receive one block.

An arena aligns the current offset upward, checks both alignment arithmetic and size addition for overflow/capacity, then advances monotonically. It cannot free individual objects, which is precisely why allocation is simple and fragmentation-free. Reset occurs only when every arena object is dead.

Patterns and when they apply

intrusive list

Tasks, timers, descriptors with stable ownership. Cost: Link fields in every object; poor locality. Avoid when: Allocating wrapper nodes unnecessarily.

fixed-block pool

Packets, events, control objects of one size. Cost: Internal fragmentation to block size. Avoid when: Unvalidated foreign or double free.

arena

Phase-scoped parsing or initialization objects. Cost: Bulk lifetime only. Avoid when: Reset while references survive.

Pool allocation

1. Partition caller memory into aligned equal blocks.
2. Link every free block through its first bytes.
3. Pop one block and mark its slot allocated.
4. On free, validate range/alignment/state before pushing it back.

Allocation and free have bounded constant work with no external heap fragmentation.

Checklist

• Can a pointer be foreign or misaligned?
• How is double free detected?
• Who serializes pool access?
• What is internal fragmentation?
• When is arena reset legal?

Medium - Intrusive Ready List

Every RTOS ready list, timer list and wait queue. The node is embedded inside the task control block rather than allocated around it.

Implement insert, remove, and move-to-front for an intrusive doubly linked list. Nodes are owned by tasks and no allocation is allowed.

Intrusive doubly linked list (Linux-style)

O(1) insert-at-tail, remove, and move-to-front on a circular intrusive list with a sentinel head. Nodes are embedded in owner structures; the list never allocates. Removing an unlinked node is a contract violation, not a runtime check.

#include <stdbool.h>
#include <stddef.h>

typedef struct node { struct node *prev, *next; } node_t;
typedef struct { node_t sentinel; } list_t;

void list_init(list_t *list) {
    /* Empty list: the sentinel points to itself in both directions. */
    list->sentinel.prev = &list->sentinel;
    list->sentinel.next = &list->sentinel;
}

bool list_empty(const list_t *list) {
    return list->sentinel.next == &list->sentinel;
}

void list_insert(list_t *list, node_t *node) {
    /* Splice between the current tail and the sentinel: 4 pointer writes. */
    node_t *tail = list->sentinel.prev;
    node->prev = tail;
    node->next = &list->sentinel;
    tail->next = node;
    list->sentinel.prev = node;
}

void list_remove(node_t *node) {
    /* Because every node lives between two real neighbors (the sentinel
       counts), removal needs no NULL or head checks. */
    node->prev->next = node->next;
    node->next->prev = node->prev;
    node->prev = node->next = node;   /* self-link marks 'not in a list' */
}

void list_move_to_front(list_t *list, node_t *node) {
    list_remove(node);
    node_t *first = list->sentinel.next;
    node->prev = &list->sentinel;
    node->next = first;
    first->prev = node;
    list->sentinel.next = node;
}

node_t *list_front(const list_t *list) {
    return list_empty(list) ? NULL : list->sentinel.next;
}

• Intrusive means the link pointers live inside the object being linked (a task control block, a timer), not in a separately allocated container node. One object, one allocation, zero malloc in the list code — this is how the Linux kernel and every RTOS ready list works.
• The sentinel node is the design's superpower: the list is circular and 'empty' just means the sentinel points at itself. Every node always has a real prev and next, so insert and remove need no special cases for head, tail, or empty.
• Remove is two pointer writes through the node's own neighbors — that is why it is O(1) without knowing the list head, which is exactly what a scheduler needs when a task blocks.
• Self-linking a removed node turns 'is it linked?' into a one-compare check (node->next == node) and makes double-remove corrupt detectable in debug builds.
• Recover the owning struct with offsetof (container_of): the node address minus the member offset gives the task block back.

Cases the tests must cover

• Insert A,B,C then front-to-back traversal yields A,B,C
• Remove the middle node: A,C remain linked both directions
• move_to_front on the tail makes it the new front
• Insert after removing everything rebuilds from empty correctly
• list_empty true only right after init or full drain

How it gets written wrong

• NULL-terminating instead of circular-with-sentinel: every operation grows head/tail special cases and bugs breed there.
• Forgetting to self-link on remove, leaving stale neighbors that a later remove writes through — silent corruption of an unrelated list.
• Putting the node in two lists at once through the same member; an intrusive node belongs to exactly one list per node member.

Easy - Detect Free-List Corruption

Detecting a corrupted free list in a pool allocator, which is what a double-free produces: a node that points back into the chain.

Use slow/fast pointers to detect a cycle in a fixed-block allocator free list without modifying it.

Floyd's cycle detection for free-list audit

Returns true if the singly linked free list contains a cycle. Reads only; never modifies links. O(1) space regardless of list size.

#include <stdbool.h>
#include <stddef.h>

typedef struct block { struct block *next_free; } block_t;

bool free_list_has_cycle(const block_t *head) {
    const block_t *slow = head;
    const block_t *fast = head;
    while (fast != NULL && fast->next_free != NULL) {
        slow = slow->next_free;              /* 1 step */
        fast = fast->next_free->next_free;   /* 2 steps */
        if (slow == fast) return true;       /* lap complete: cycle exists */
    }
    return false;                            /* fast reached the end */
}

• A corrupted free list (double-free is the usual cause) creates a cycle, and allocating from a cycled free list hands the same block to two owners. Walking a cycle with a NULL check loops forever — you need proof, not patience.
• Floyd's tortoise and hare: two pointers advance at speeds 1 and 2. Inside any cycle the hare gains exactly one node per step on the tortoise, so if a cycle exists they must meet; if they meet, a cycle exists. Both directions are guaranteed.
• The loop condition checks fast and fast->next before the double step — that is the only NULL-deref guard needed, because slow trails fast and can never run off the end first.
• O(1) space is the point: a debug build can run this audit from an assert or a watchdog task without allocating anything, even with a corrupted heap.

Cases the tests must cover

• Linear list of 100 blocks → false
• Tail pointing back to the head → true
• Self-loop on the only node → true
• Empty list (NULL head) → false
• Cycle starting mid-list (rho shape) → true

How it gets written wrong

• Advancing fast twice without the intermediate NULL check — crash on a healthy odd-length list.
• Marking visited nodes by writing a flag or flipping pointer bits: the contract forbids modifying the list, and a corrupted allocator may be mid-write.
• Using a visited-set with malloc inside an allocator-debug path; if the heap is the suspect, malloc is not your friend.

Medium - Fixed-Block Allocator

The standard replacement for malloc in firmware: a fixed number of equally sized blocks with a free list threaded through the blocks themselves.

Initialize N equal blocks inside caller-owned memory and implement O(1) allocate/free. Reject misaligned, foreign, and double-freed pointers.

Fixed-block pool with allocation bitmap

Manages at most 32 equal blocks in caller storage. Rejects foreign, misaligned, and double-freed pointers.

#include <stdbool.h>
#include <stddef.h>
#include <stdint.h>

typedef struct block { struct block *next; } block_t;
typedef struct { uint8_t *base; size_t block_size,count; block_t *free; uint32_t used; } pool_t;

bool pool_init(pool_t *p, void *memory, size_t bytes,
               size_t block_size, size_t count) {
    size_t align = _Alignof(block_t);
    if (!p || !memory || count==0u || count>32u || block_size<sizeof(block_t) ||
        (uintptr_t)memory % align != 0u || block_size % align != 0u ||
        count > bytes / block_size) return false;
    p->base=memory; p->block_size=block_size; p->count=count; p->free=NULL; p->used=0u;
    for (size_t i=count; i!=0u; --i) {
        block_t *b=(block_t *)(p->base+(i-1u)*block_size);
        b->next=p->free; p->free=b;
    }
    return true;
}

void *pool_alloc(pool_t *p) {
    if (!p || !p->free) return NULL;
    block_t *b=p->free; p->free=b->next;
    size_t slot=((uint8_t *)b-p->base)/p->block_size;
    p->used|=UINT32_C(1)<<slot; return b;
}

bool pool_free(pool_t *p, void *ptr) {
    if (!p || !ptr) return false;
    uintptr_t base=(uintptr_t)p->base, address=(uintptr_t)ptr;
    if (address<base || address-base>=p->count*p->block_size ||
        (address-base)%p->block_size!=0u) return false;
    size_t slot=(address-base)/p->block_size; uint32_t bit=UINT32_C(1)<<slot;
    if ((p->used&bit)==0u) return false;
    p->used&=~bit; block_t *b=ptr; b->next=p->free; p->free=b; return true;
}

• The free list lives inside currently unused blocks.
• A bitmap records allocation state so double-free is rejected.
• Alignment and division checks make every block a valid block_t without overflowing geometry arithmetic.

Cases the tests must cover

• allocate all then exhaust
• free/reuse
• foreign pointer
• interior pointer
• double free
• invalid geometry and alignment

How it gets written wrong

• Payload types may require stricter alignment than block_t; choose block geometry for the strongest stored type.
• Concurrent or ISR access needs a critical section or a separately proven lock-free design.

Medium - Bitmap Slot Allocator

Allocating from a fixed slot set where the blocks must stay in a specific memory region - DMA-capable RAM, a battery-backed section, or a cache-aligned area.

Allocate the first free slot from up to 256 fixed slots using a bitmap. Implement allocate, release, and largest contiguous free run.

256-slot bitmap allocator with free-run query

slot_alloc returns the lowest free slot index or -1 when full. slot_free releases a valid allocated slot and rejects double-free/out-of-range. slot_largest_free_run returns the longest run of consecutive free slots. 256 slots tracked in 8 words.

#include <stdbool.h>
#include <stddef.h>
#include <stdint.h>

#define SLOT_WORDS 8u   /* 8 * 32 = 256 slots */

typedef struct {
    uint32_t used[SLOT_WORDS];   /* bit i of word w = slot 32*w + i is taken */
} slot_pool_t;

void slot_pool_init(slot_pool_t *pool) {
    for (unsigned w = 0u; w < SLOT_WORDS; w++) pool->used[w] = 0u;
}

int slot_alloc(slot_pool_t *pool) {
    if (pool == NULL) return -1;
    for (unsigned w = 0u; w < SLOT_WORDS; w++) {
        uint32_t free_mask = ~pool->used[w];
        if (free_mask != 0u) {
            /* Isolate the lowest free bit: x & -x. */
            uint32_t bit = free_mask & (0u - free_mask);
            pool->used[w] |= bit;
            /* Count trailing zeros of bit via de Bruijn-free loop (<= 31). */
            unsigned i = 0u;
            while (bit >>= 1u) i++;
            return (int)(w * 32u + i);
        }
    }
    return -1;   /* all 256 slots taken */
}

bool slot_free(slot_pool_t *pool, unsigned slot) {
    if (pool == NULL || slot >= 256u) return false;
    uint32_t bit = 1u << (slot & 31u);
    if ((pool->used[slot / 32u] & bit) == 0u) return false;  /* double free */
    pool->used[slot / 32u] &= ~bit;
    return true;
}

unsigned slot_largest_free_run(const slot_pool_t *pool) {
    unsigned best = 0u, run = 0u;
    for (unsigned w = 0u; w < SLOT_WORDS; w++) {
        for (unsigned i = 0u; i < 32u; i++) {
            if ((pool->used[w] & (1u << i)) == 0u) {
                run++;
                if (run > best) best = run;
            } else {
                run = 0u;
            }
        }
    }
    return best;
}

• A bitmap allocator trades 1 bit per slot for O(1) free and tiny metadata: 256 slots cost 32 bytes. Compare with a free list, which needs a whole pointer per free block.
• x & -x isolates the lowest set bit in one AND — two's complement negation flips every bit left of the lowest 1, so only that bit survives the AND. Finding its index is a trailing-zero count (use __builtin_ctz where allowed).
• Allocation scans words, not bits: any word that is not 0xFFFFFFFF has a free slot, so the common case touches one word — that is the O(words) worst case with an O(1) fast path.
• slot_free validates before clearing: out-of-range and double-free both return false, because in a slot allocator a double free silently hands one resource (DMA channel, message slot) to two owners.
• The largest-run query powers defragmentation decisions and contiguous allocations (e.g., adjacent DMA buffer slots) and is a straight 256-bit scan.

Cases the tests must cover

• Allocate all 256 slots, then one more returns -1
• Freed slot is the next one returned by alloc (lowest-first policy)
• Double free returns false and the slot stays allocated
• Free 10 consecutive mid-pool slots: largest_free_run reports 10
• slot 255 allocate/free works (word 7, bit 31 edge)

How it gets written wrong

• Shifting 1 << 32 for slot 32 within a word — mask the index with & 31.
• Skipping the double-free check: a free-bit clear is idempotent, so corruption stays invisible until two owners collide.
• Using ~used[w] and then counting from bit 31 — lowest-first policy is what makes frees deterministic and testable.

Medium - Aligned Arena Allocator

Carving one static region into differently aligned objects at startup: DMA descriptors needing 32-byte alignment, structures needing natural alignment, byte buffers needing none.

Implement bump allocation with arbitrary power-of-two alignment, overflow checks, a high-water mark, and reset. No individual free operation.

Bump arena with alignment and high-water mark

Bump-allocates size bytes at any power-of-two alignment from a caller-owned buffer. Returns NULL (offset unchanged) on invalid alignment, arithmetic overflow, or exhaustion. arena_reset frees everything at once; arena_high_water reports peak usage. No per-object free.

#include <stdbool.h>
#include <stddef.h>
#include <stdint.h>

typedef struct {
    uint8_t *base;
    size_t capacity;
    size_t offset;
    size_t high_water;
} arena_t;

void arena_init(arena_t *a, void *buffer, size_t capacity) {
    a->base = (uint8_t *)buffer;
    a->capacity = capacity;
    a->offset = 0u;
    a->high_water = 0u;
}

void *arena_alloc(arena_t *a, size_t size, size_t alignment) {
    if (a == NULL || alignment == 0u || (alignment & (alignment - 1u)) != 0u)
        return NULL;                       /* alignment must be a power of two */
    /* Round the offset up without overflow: check before adding. */
    size_t mask = alignment - 1u;
    if (a->offset > SIZE_MAX - mask) return NULL;
    size_t aligned = (a->offset + mask) & ~mask;
    if (aligned > a->capacity || size > a->capacity - aligned)
        return NULL;                       /* [aligned, aligned+size) must fit */
    a->offset = aligned + size;
    if (a->offset > a->high_water) a->high_water = a->offset;
    return a->base + aligned;
}

void arena_reset(arena_t *a) {
    a->offset = 0u;                        /* memory is abandoned, not zeroed */
}

size_t arena_high_water(const arena_t *a) {
    return a->high_water;
}

• A bump allocator is a stack you cannot pop: allocation is a pointer increment, and free is a bulk reset. For frame-scoped or init-scoped firmware allocations this replaces malloc entirely — O(1), zero fragmentation, deterministic.
• Aligning up is (offset + alignment - 1) & ~(alignment - 1): the add forces any misaligned offset into the next alignment period, and the mask clears the low bits back to the boundary. It only works for power-of-two alignment — hence the validation.
• Every add is preceded by an overflow check (offset > SIZE_MAX - mask, size > capacity - aligned). The naive aligned + size <= capacity check can wrap to a small number and hand out memory past the buffer.
• On failure the offset is untouched, so a rejected allocation never wedges the arena — the caller can free scope (reset) or try a smaller request.
• The high-water mark tells you after a test run how small the arena could have been; sizing by measurement beats guessing.

Cases the tests must cover

• Aligned alloc returns pointer with address % alignment == 0
• Allocation exactly filling capacity succeeds; one more byte fails
• Failed alloc leaves offset unchanged (retry with smaller size works)
• alignment 3 (not power of two) returns NULL
• Reset then re-alloc returns the base address again; high_water survives reset

How it gets written wrong

• The capacity check aligned + size <= capacity wraps on overflow — always subtract instead.
• Masking without validating power-of-two alignment: (x + 5) & ~5 is not alignment to 6.
• Zeroing or poisoning on reset in release builds: fine in debug, but it turns O(1) reset into O(n) — the contract says reset only moves the offset.

Easy - Reverse a Singly Linked List

Reversing a chain in place - flipping a captured event list for newest-first display, or reversing an intrusive list without touching the objects it links.

Reverse an intrusive singly linked list iteratively and return the new head. Do not allocate, recurse, or lose nodes.

Iterative three-pointer list reversal

Reverses a singly linked list in place and returns the new head (the old tail). NULL in, NULL out. No allocation, no recursion; every node is preserved.

#include <stddef.h>

typedef struct node { struct node *next; int key; } node_t;

node_t *list_reverse(node_t *head) {
    node_t *prev = NULL;   /* the already-reversed prefix */
    node_t *cur = head;    /* the node whose link we flip */
    while (cur != NULL) {
        node_t *next = cur->next;  /* save before overwriting */
        cur->next = prev;          /* flip this link backwards */
        prev = cur;                /* reversed prefix grows */
        cur = next;                /* march on */
    }
    return prev;                   /* NULL for empty input — correct */
}

• Three pointers walk down the list: prev is the part already reversed, cur is being flipped, next saves the rest before the link is overwritten. Without saving next first, flipping cur->next severs the list and the remainder leaks.
• Each iteration flips exactly one link, so n nodes cost n steps and two extra pointers — O(n) time, O(1) space. Recursion also works but spends O(n) stack, which is exactly what small MCUs do not have.
• When cur runs off the end, prev points at the old tail — the new head. The empty list case falls out naturally: prev starts NULL and is returned unchanged.
• The invariant 'prev is a correctly reversed list and cur.. is untouched' holds before and after every iteration; saying it out loud is how you know the loop is right.

Cases the tests must cover

• A->B->C becomes C->B->A with head C
• Single node returns itself
• NULL returns NULL
• Two nodes swap order
• Node count and key multiset are identical before and after

How it gets written wrong

• Writing cur->next = prev before saving cur->next — the tail of the list is lost.
• Returning head instead of prev; head still points at the old first node, now the tail.
• Forgetting to NULL-terminate: the first node naturally gets next = NULL from the initial prev = NULL — do not 'fix' that.

Easy - Merge Sorted Intrusive Lists

Combining two sorted timer or event lists into one - merging a task's private deadlines into the global timer list on resume.

Merge two sorted intrusive lists by relinking their existing nodes. Preserve relative order for equal keys.

Stable merge of two sorted intrusive lists

Relinks the nodes of two key-sorted lists into one sorted list and returns the new head. Equal keys keep a's node before b's (stable). No new nodes, O(1) extra space; both input lists are consumed.

#include <stddef.h>

typedef struct node { struct node *next; int key; } node_t;

node_t *list_merge(node_t *a, node_t *b) {
    node_t dummy;                 /* fake head kills the empty-output special case */
    node_t *tail = &dummy;
    while (a != NULL && b != NULL) {
        if (b->key < a->key) {    /* strict < : ties take from a first (stable) */
            tail->next = b;
            b = b->next;
        } else {
            tail->next = a;
            a = a->next;
        }
        tail = tail->next;
    }
    tail->next = (a != NULL) ? a : b;   /* splice the whole surviving run */
    return dummy.next;
}

• Walk both heads and repeatedly append the smaller key to the output. Because inputs are sorted, the global next-smallest is always one of the two heads — no searching.
• The dummy head node removes the 'is output empty yet?' branch from every iteration; at the end, dummy.next is the real head. Stack-allocating it costs 8 bytes and zero heap.
• Stability is one character: b->key < a->key (strict) sends ties to the a branch. In firmware, stability preserves arrival order for equal-priority items.
• When one list empties, the other is already sorted, so the whole remainder is spliced with one pointer write — that is why merge is O(n + m), not O(n·m).
• Nodes are relinked, never copied: this is the only viable strategy for intrusive lists where the node's owner (task, timer) lives at a fixed address.

Cases the tests must cover

• [1,3,5] + [2,4,6] → 1,2,3,4,5,6
• Equal keys: a's nodes precede b's for each equal pair
• One empty list returns the other unchanged
• Both empty returns NULL
• All of a smaller than all of b: single splice, correct order

How it gets written wrong

• Using <= for the tie test, which silently inverts equal-key order (unstable).
• Handling the first node outside the loop and then duplicating logic inside — the dummy node exists to kill that duplication.
• Appending the remainder node-by-node after one list empties; correct but pointless — splice once.

Medium - Remove Nth Node from Tail

Trimming a bounded history list to a fixed length - dropping the oldest entry from a capped event log held as a singly linked chain.

Unlink the nth node from the end in one pass, return it to the caller, and handle n larger than the list length without modification.

One-pass removal of the nth node from the tail

Unlinks and returns the nth node from the end (n=1 is the tail). Returns NULL with the list untouched when n is 0 or exceeds the length. head may be updated when the head itself is removed.

#include <stddef.h>

typedef struct node { struct node *next; int key; } node_t;

node_t *list_remove_from_end(node_t **head, size_t n) {
    if (head == NULL || n == 0u) return NULL;
    node_t *fast = *head;
    /* Move fast n steps ahead; running out early means n > length. */
    for (size_t i = 0u; i < n; i++) {
        if (fast == NULL) return NULL;   /* list untouched */
        fast = fast->next;
    }
    /* slow_link points at the LINK that leads to the node before target. */
    node_t **slow_link = head;
    while (fast != NULL) {
        fast = fast->next;
        slow_link = &(*slow_link)->next;
    }
    node_t *removed = *slow_link;
    *slow_link = removed->next;    /* unlink (handles head via *head) */
    removed->next = NULL;          /* return it fully detached */
    return removed;
}

• Keep two cursors n nodes apart; when the front one falls off the end, the back one sits exactly on the node before the target. Distance-from-the-end becomes distance-between-pointers — one pass, no length pre-count.
• slow_link is a pointer to a pointer (the link field itself, starting at head). Unlinking through *slow_link handles head removal with zero special cases — the same trick Linus praises for elegant list code.
• All validation happens before any write: if n is too large, fast runs out during the lead-in and the function returns NULL without touching a single link, exactly as the contract demands.
• The removed node's next is cleared so the caller gets a cleanly detached node; leaving it linked invites a later double-unlink through stale pointers.

Cases the tests must cover

• [A,B,C,D] n=1 → returns D, list A,B,C
• n equal to length → head removed, *head updated
• n greater than length → NULL, every link byte-identical
• Single node, n=1 → returns it, *head becomes NULL
• n=0 → NULL, list unchanged

How it gets written wrong

• Counting the length first, then walking again — two passes where the gap trick needs one.
• Special-casing head removal with if (prev == NULL); the pointer-to-pointer form already covers it.
• Checking n against the length after partially unlinking — validation must complete before mutation.

Hard - Bottom-Up Merge Sort a List

Ordering a linked structure that cannot be moved into an array - sorting intrusive nodes by deadline where the objects themselves must stay put.

Sort an intrusive singly linked list stably without recursion or allocation, using iterative bottom-up merge sort.

Bottom-up (iterative) merge sort for linked lists

Stably sorts a singly linked list by key, ascending, in O(n log n) time and O(1) extra space: no recursion, no allocation, nodes are only relinked.

#include <stddef.h>

typedef struct node { struct node *next; int key; } node_t;

/* Merge two sorted runs, returning head via out and the new tail. */
static node_t *merge_runs(node_t *a, node_t *b, node_t **tail_out) {
    node_t dummy;
    node_t *tail = &dummy;
    while (a != NULL && b != NULL) {
        if (b->key < a->key) { tail->next = b; b = b->next; }
        else                 { tail->next = a; a = a->next; }
        tail = tail->next;
    }
    tail->next = (a != NULL) ? a : b;
    while (tail->next != NULL) tail = tail->next;  /* find true tail */
    *tail_out = tail;
    return dummy.next;
}

node_t *list_sort(node_t *head) {
    if (head == NULL || head->next == NULL) return head;
    size_t n = 0u;
    for (node_t *p = head; p != NULL; p = p->next) n++;
    node_t dummy;
    dummy.next = head;
    for (size_t width = 1u; width < n; width *= 2u) {
        node_t *prev_tail = &dummy;
        node_t *cur = dummy.next;
        while (cur != NULL) {
            /* Split off the LEFT run of up to 'width' nodes. */
            node_t *left = cur;
            size_t i = 1u;
            while (i < width && cur->next != NULL) { cur = cur->next; i++; }
            node_t *right = cur->next;
            cur->next = NULL;                    /* terminate left run */
            /* Split off the RIGHT run of up to 'width' nodes. */
            cur = right;
            node_t *next_pair = NULL;
            if (cur != NULL) {
                size_t j = 1u;
                while (j < width && cur->next != NULL) { cur = cur->next; j++; }
                next_pair = cur->next;
                cur->next = NULL;                /* terminate right run */
            }
            node_t *merged_tail;
            node_t *merged = merge_runs(left, right, &merged_tail);
            prev_tail->next = merged;
            prev_tail = merged_tail;
            cur = next_pair;
        }
    }
    return dummy.next;
}

• Top-down merge sort recurses to depth log n — fine on a desktop, a stack-overflow risk on an MCU. Bottom-up gets the same O(n log n) iteratively: merge adjacent runs of 1, then 2, then 4, doubling until one run remains.
• Every list starts as n sorted runs of length 1 (a single node is trivially sorted). Each pass merges pairs of runs into sorted runs of double width, so ceil(log2 n) passes over the data finish the job.
• All work is relinking: runs are cut by writing NULL and joined by writing next pointers. No node is copied, allocated, or freed — mandatory for intrusive lists.
• Stability comes from the merge taking from the left run on ties (b->key < a->key picks right only when strictly smaller), preserving original order of equal keys across every pass.
• The dummy head absorbs the 'new head of the list' special case for pass boundaries, just like in plain merge.

Cases the tests must cover

• Reverse-sorted 100-node list sorts ascending
• Already sorted list is unchanged (and stability keeps equal-key order)
• All equal keys: original node order preserved exactly
• n = 0, 1, 2 handled without entering the merge machinery
• Odd-length lists: the short final run merges correctly

How it gets written wrong

• Recursing depth-first: elegant, but log2(100k) stack frames of several words each is real RAM on a 20 KB device.
• Forgetting to NULL-terminate the split runs — the merge then walks past the run boundary into the next pair.
• Taking the right run on ties breaks stability, which visible reordering of equal-priority timers exposes.

Medium - Nested Arena Scopes

Nested scratch allocation: a parser takes a marker, allocates freely while decoding a frame, then rewinds the whole lot in one operation.

Extend a bump arena with save/restore marks so nested subsystems can roll back their allocations independently. Restoring moves only the offset and never zeroes memory.

Arena save/restore marks

arena_save returns the current offset. arena_restore rewinds to an older mark in O(1) and rejects marks from beyond the current offset. Allocation is checked against remaining capacity.

#include <assert.h>
#include <stdbool.h>
#include <stddef.h>
#include <stdint.h>

typedef struct { uint8_t *base; size_t cap; size_t off; } arena_t;
typedef struct { size_t off; } arena_mark_t;

static void arena_init(arena_t *a, uint8_t *mem, size_t cap)
{
    a->base = mem; a->cap = cap; a->off = 0U;
}

static void *arena_alloc(arena_t *a, size_t size)
{
    void *p;
    if (size > a->cap - a->off) return NULL;   /* subtraction form: no overflow */
    p = a->base + a->off;
    a->off += size;
    return p;
}

arena_mark_t arena_save(const arena_t *a)
{
    arena_mark_t m = { a->off };
    return m;
}

bool arena_restore(arena_t *a, arena_mark_t mark)
{
    if (mark.off > a->off) return false;   /* mark from the future: invalid */
    a->off = mark.off;                     /* rollback is just an offset move */
    return true;
}

int main(void)
{
    uint8_t mem[16];
    arena_t a;
    arena_mark_t m;
    uint8_t *p1, *p2;
    arena_init(&a, mem, sizeof mem);
    p1 = (uint8_t *)arena_alloc(&a, 4U);
    m = arena_save(&a);
    p2 = (uint8_t *)arena_alloc(&a, 8U);
    assert(p1 == mem && p2 == mem + 4U);
    assert(arena_alloc(&a, 5U) == NULL);       /* 12 used, 4 left */
    assert(arena_restore(&a, m));
    assert(arena_alloc(&a, 12U) == mem + 4U);  /* space reused after restore */
    return 0;
}

• A mark is just an offset; restore never touches memory, so it is O(1) and cannot fail on content.
• Nested scopes restore in LIFO order; restoring an inner mark invalidates outer marks taken after it.
• cap - off cannot underflow because off <= cap is the arena invariant.

Cases the tests must cover

• alloc after restore reuses the same address
• exhaustion returns NULL
• future mark rejected
• restore to the same mark twice is idempotent
• zero-size allocation returns the current offset

How it gets written wrong

• Objects restored away must be dead: dangling pointers into rewound space are use-after-free.
• Restore does not zero memory; stale bytes remain visible.

More in Embedded DSA

• The WorkbenchA complete embedded-first DSA course with theory, 80 challenges, complete C11 implementations, visual traces, mastery tracking, interview drills, and a constraint-driven firmware design arena.
• Arrays & WindowsTwo pointers, sliding windows, in-place compaction and streaming filters over sample buffers. Twelve problems with complete C11 solutions, complexity targets and edge-case tests.
• Search & LookupBinary search that actually terminates, lookup tables, perfect hashing and command dispatch. Eleven problems on getting a bounded answer out of a table without a heap allocation in sight.
• Trees, Graphs & StateTries for command tables, union-find for connectivity, and state machines that cannot reach an undefined state. Nine problems on structures that encode relationships rather than sequences.
• Parsing & ProtocolsFraming, COBS, incremental parsers and adversarial input. Nine problems on decoding a byte stream from a hostile world without a buffer overflow or an unbounded loop.
• Linked ListsEvery list variant, written for embedded C rather than for a whiteboard: singly and doubly linked, circular lists and sentinels that delete the boundary cases, the intrusive form kernels and firmware actually use, static pools and free lists for systems without malloc, reversal and cycle detection, and an honest account of when an array is the better answer.
• Sorting Under ConstraintWhich sort survives a 512-byte stack and a fixed deadline. Insertion sort for small nearly-sorted windows, heapsort when the worst case must be provable, counting sort for byte keys, and a bounded-depth quicksort - six problems with complete C11 solutions.
• Heaps & SchedulingBinary heaps as timer wheels and task schedulers, and wrap-safe time comparison - the bug that only shows up 49 days after the board is deployed. Eight problems with complete solutions.
• Integer & Fixed-Point MathComputing the right number with no floating-point unit. Q formats, multiply-before-divide, rounding instead of truncating, division by a constant as a multiply and shift, running averages that do not stall, and LFSR jitter for backoff.
• Stacks, Queues & RingsThe ring buffer and the SPSC queue: the two structures every firmware project actually ships. Ownership between an ISR and a main loop, overflow policy, and why the full/empty test is where the bugs are.
• Bits & BytesRegister fields, bit reversal, parity, endianness and portable packet decoding, without invoking undefined behaviour. Seven problems with complete C11 solutions and a step-by-step trace for each.
• Firmware CapstonesSix full-system problems: DMA ownership, wear-levelled persistence, crash-safe logging and proving a design meets its RAM and WCET budget. This is where every earlier stage gets used at once.