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.