Integrate the Allocator and Its Contracts

The capstone combines my_malloc, my_free, my_realloc, and my_calloc around one block list. Its required behavior is first-fit reuse with data preservation and checked size arithmetic. Splitting and coalescing are optional extensions; the supplied reference retains whole blocks. Treat the exercise statement as the interface contract rather than assuming every technique from earlier lessons is mandatory.

One list, four operations

Each header records payload capacity, a free flag, and a successor. The list includes free and live blocks. At all observable points, every live payload belongs to exactly one allocation, no two live payload regions overlap, and a free block is eligible only when its capacity fits the request.

my_malloc(n) searches for the first eligible block, claims it, or extends the heap after validating the full size. Append a new header only after the allocation succeeds. my_free(p) marks a live allocation reusable; NULL is a no-op. The byte-oriented reference aligns its metadata headers and may leave padding between allocations, so a successor link does not by itself prove physical adjacency.

Trace reuse, resize, and zeroing together

Allocate A with capacity 32 and B with capacity 64. Fill A with byte 7 and B with byte 9. Free A. A request for 20 reuses A without splitting, so A keeps capacity 32. A subsequent growth request for 48 cannot fit there; B is still live, so allocate C, copy A's existing capacity, and only then free A. B's data must remain unchanged.

Now my_calloc(4, 4) can reuse A. It must clear the requested 16 bytes even though A contains dirty data. A's remaining capacity is not part of the new requested array. Finally, my_realloc(C, 0) frees C and returns NULL under our custom contract. A NULL return from positive-size growth failure instead leaves the old allocation live. These branches have different ownership outcomes despite the same return value.

Test failure after a live allocation exists: request SIZE_MAX and verify rejection, unchanged bytes, unchanged list links, and the old block still marked used. Checking multiplication for calloc alone is insufficient; malloc must also reject overflow in header and padding addition and conversion to the positive signed sbrk range.

If you add coalescing, preserve the spatial invariant

Two physically adjacent free blocks of capacities 32 and 64 with header size H merge to 32 + H + 64, because the second header becomes usable space. Three free blocks of 32 bytes merge to 96 + 2H, not just 96. Recover the header bytes exactly once.

With free/used/free neighbors, freeing the middle block may permit merging both sides. Repeated forward merging handles arbitrary runs; finding a free previous physical neighbor may change the returned header address. Never merge through a live allocation or across allocator padding merely because both blocks are linked. Coalescing can enable reuse of a larger block without further heap growth; a failed free-list search does not necessarily mean malloc fails, since heap extension may still succeed.

Boundaries of this capstone

This allocator is single-threaded, uses a program-break teaching model, and does not replace the platform C allocator. General-purpose alignment, arbitrary invalid-pointer detection, concurrent reclamation, mapping policies, and libc interposition are separate projects. my_malloc(0) and my_calloc with either factor zero return NULL. my_realloc(NULL, 0) allocates nothing. Non-NULL arguments to free/realloc must be live pointers returned by this allocator.

Reconstruct the key proof: why does a failed growth leave the original intact? Allocation is attempted before any old ownership or metadata is changed; failure returns immediately. Why must calloc clear a reused block? Free changes eligibility, not contents. Why can coalescing not be inferred from list order? The list is an ownership structure; only byte addresses establish adjacency.