Make Allocation Reuse Freed Blocks

You now have a list of initialized blocks and an operation that ends payload ownership. Integrate them by making my_malloc search before asking for more space. The list contains all blocks; its historical name free_list_head does not mean every node is free.

Separate search from claim

find_free_block(size) walks the list in order and returns the first header whose free flag is set and whose capacity is at least size. Searching must not change the list, capacity, or flags. my_malloc claims a selected header by setting free=0, then returns its immediate payload.

Why separate these steps? A helper caller can inspect a candidate without consuming it, while the allocator has one clear ownership transition. Forgetting the claim lets two successive allocations return the same live payload. Claiming during search makes a read-only helper unexpectedly consume capacity.

Use this decision sequence:

size is zero                 → NULL, no mutation
first free capacity >= size  → claim it, return payload
no candidate                 → checked growth, initialize, append, return payload
growth fails                 → NULL, preserve all existing state

The provided growth helper carries forward checked size arithmetic and header alignment from the previous module. Padding before a new header means logical neighbors need not be physical neighbors. This exercise does not split or coalesce blocks.

Work a complete reuse history

Start with A:48 free → B:24 used → C:80 free. The following requests use list order, not closest size:

Operation	Search result	State afterwards	Growth
malloc(32)	A fits first	A used, B used, C free	none
malloc(32)	A/B used; C fits	A used, B used, C used	none
free(first result)	recover A	A free, B used, C used	none
malloc(48)	A fits exactly	all used	none
malloc(49)	no eligible node	append D if growth succeeds	required

Each reuse retains the selected block's original capacity. A's size remains 48 after serving 32, because no split created a separate block for the other 16 bytes. Shrinking size to the request would lose reusable capacity and make a later 48-byte request unnecessarily grow the heap.

When a block is freed, preserve its next link. Unlinking A would make it unreachable for the next scan; replacing its successor with NULL would also lose B and C. The live payloads in other blocks must survive the entire history.

Distinguish three reasons for apparent free space failure

Consider [16 free, 64 used, 16 free] and a request for 24. There are 32 free payload bytes in total, but no eligible individual block has capacity 24. The middle live allocation prevents a contiguous 24-byte claim. Summing free capacity is useful accounting, not a proof that a request fits.

In [96 free, 24 free], a 24-byte request uses the 96-byte block because it occurs first. That is first fit; best fit would pick 24. The unused capacity inside a claimed unsplit block is internal fragmentation. Small separated free blocks illustrate external fragmentation. Splitting/coalescing are later policy choices with their own geometry checks.

The comparison must be capacity >= request: a free capacity of 48 satisfies 48, but not 49. Being large enough is insufficient when a block is live. Being free is insufficient when its capacity is too small.

Make failure preserve the old state

Suppose no free block fits and the growth helper returns NULL. Keep the old list and every live payload unchanged. A failed request must not mark another block used merely because it was visited, append a failure sentinel, or erase a successor.

The helper rejects sizes whose header-plus-padding reservation cannot fit the signed increment type. On ordinary allocation failure it also leaves the list unchanged. A zero request does not run a search that might accidentally claim a free block.

The allocation API returns a payload; the list stores headers. Convert through the actual block_header_t layout. my_free(NULL) is a no-op; other arguments must be live payload pointers. The supplied magic check assumes that precondition and can detect some readable metadata corruption, not safely validate any address.

Finish the search and commit trace

Start with A:24 free → B:72 free → C:40 used. Call find_free_block(32), then my_malloc(32), then my_malloc(16), then free the 32-byte allocation. Record header selection and all flags after each operation.

Reveal the trace

The helper returns B and changes nothing. The first allocation claims B; A is still free. The second allocation claims A. Freeing the first result makes B free again. Capacities remain 24, 72, 40 throughout, and the list remains A→B→C. None of these operations grows the heap.

Verify ownership before adding policies

Build the search helper and check that repeated searches return the same unclaimed header. Then integrate the claim and confirm that consecutive live allocations are distinct. Preserve data in a still-live neighbor while another block is repeatedly freed and reused. A malloc→free→malloc address check alone does not test first fit, capacity retention, or search purity.

As an independent variation, begin with [40 free, 16 used, 80 free], request 41 then 40, and explain why both requests succeed without growth but in reverse capacity order. Later, test a request larger than every free block despite sufficient total free bytes.

This contract is single-threaded. An atomic head pointer would not make the entire find-and-claim transition atomic: two callers could both observe the same free flag. Synchronization and OS interaction must cover the complete state transition before this design can serve concurrent callers. The next module builds realloc and calloc on the ownership and capacity rules established here.