Free-List Allocator (C)
Topics: allocator, malloc/free, block splitting, coalescing
Problem
Implement a first-fit free-list allocator over a fixed, caller-provided buffer — a real
malloc/free (unlike the bump arena, which never reclaims). Blocks are laid out contiguously, each
prefixed by a small header, forming an implicit free list you walk by following sizes.
typedef struct { size_t size; int used; } Header; // (provided)
typedef struct { unsigned char *buf; size_t cap; } Allocator;
void alloc_init(Allocator *a, void *buf, size_t cap); // one big free block (provided)
void *alloc_malloc(Allocator *a, size_t size); // first-fit + split; NULL if none
void alloc_free(Allocator *a, void *ptr); // mark free + coalesce neighbors
alloc_malloc: round size up to 8, scan blocks for the first free one that fits, split
off the remainder if it can hold a header + a usable payload, mark it used, return the payload
(header + 1). NULL if nothing fits.alloc_free: mark the block free, then merge adjacent free blocks so the space can be reused
by a larger later request.
Key concepts
- Header per block: the payload pointer is
(unsigned char*)h + HDR; from a freed pointer,
recover the header by subtracting HDR.
- Walk by size: the next block is
cur + HDR + cur->size — that's the implicit list.
- Split vs. waste: only split when the leftover fits another header + payload, else hand over the
whole block (a little internal fragmentation).
- Coalescing matters: without merging neighbors, repeated alloc/free fragments the heap and large
requests fail even with enough total free space.
Run
cc -std=c11 -O2 -Wall tests.c -o /tmp/alloc && /tmp/alloc
Sign in to submit your solution.