Appendix A: A Simple Allocator
alloc-with-reuse

Update alloc() to search the free list before bump-allocating:

fn alloc(size: i64) i64 {
    var total: i64 = (size + 7) / 8 * 8 + 8;

    // Search the free list for a large enough block
    var prev: i64 = 0;
    var curr: i64 = free_list;
    while (curr != 0) {
        var block_size: i64 = load64(curr);
        if (block_size >= total) {
            // Remove from free list
            var next: i64 = load64(curr + 8);
            if (prev == 0) {
                free_list = next;
            } else {
                store64(prev + 8, next);
            }
            return curr + 8;
        }
        prev = curr;
        curr = load64(curr + 8);
    }

    // No free block found -- bump allocate
    var block: i64 = heap_ptr;
    heap_ptr += total;
    if (heap_ptr > heap_limit) { return 0; }
    store64(block, total);
    return block + 8;
}

First-fit strategy: walk the free list, take the first block that's large enough. If nothing fits, fall back to bump allocation.

Test -- alloc, free, alloc again reuses the freed block:

    check(
        \\var heap_ptr: i64 = 500000;
        \\var heap_limit: i64 = 900000;
        \\var free_list: i64 = 0;
        \\fn alloc(size: i64) i64 {
        \\    var total: i64 = (size + 7) / 8 * 8 + 8;
        \\    var prev: i64 = 0;
        \\    var curr: i64 = free_list;
        \\    while (curr != 0) {
        \\        var block_size: i64 = load64(curr);
        \\        if (block_size >= total) {
        \\            var next: i64 = load64(curr + 8);
        \\            if (prev == 0) { free_list = next; }
        \\            else { store64(prev + 8, next); }
        \\            return curr + 8;
        \\        }
        \\        prev = curr;
        \\        curr = load64(curr + 8);
        \\    }
        \\    var block: i64 = heap_ptr;
        \\    heap_ptr += total;
        \\    if (heap_ptr > heap_limit) { return 0; }
        \\    store64(block, total);
        \\    return block + 8;
        \\}
        \\fn free(ptr: i64) i64 {
        \\    var block: i64 = ptr - 8;
        \\    store64(block + 8, free_list);
        \\    free_list = block;
        \\    return 0;
        \\}
        \\var a: i64 = alloc(100);
        \\var b: i64 = alloc(200);
        \\free(a);
        \\var c: i64 = alloc(50);
        \\c == a
    , 1);  // c reuses a's freed block

a was freed and its 112-byte block went onto the free list. When we allocate 50 bytes (total 56 with header), the free list has a 112-byte block -- large enough. We reuse it. c == a confirms they got the same address.

### A dynamic array

Now let's use the allocator to build something useful: a growable array. Fixed-size arrays require knowing the size at declaration time. A dynamic array starts small and grows as needed -- like Zig's ArrayList, Python's list, or C++'s vector.