Free List Management: Search Without Losing Ownership

You can now describe blocks. The next task, free-list-operations, connects all tracked blocks, both allocated and free, through their next fields. The historical variable name free_list_head remains in the API, but this particular list is not restricted to free nodes.

State the list invariant

A well-formed list has a head that is either NULL or a valid initialized header. Following next visits each tracked block once and eventually reaches NULL. Every node has a capacity and a free flag. Allocated nodes stay in the list so they can become reusable later.

The exercise provides valid nodes; it asks you to preserve reachability and interpret the flags. Appending requires a fresh non-NULL node not already present in the chain. Appending the head again can create a cycle, so that input is outside the contract.

List order is logical. It need not be sorted by address, and linked neighbors need not be physically adjacent. Follow next to search; use the previous module's byte geometry when physical adjacency matters later.

Trace first fit one decision at a time

Consider this list in traversal order:

Node	Capacity	Free flag	Next
A	24	1	B
B	80	0	C
C	48	1	D
D	32	1	NULL

For request 30:

1. A is free but 24 < 30, so continue.
2. B is large enough but allocated, so continue. Its bytes still belong to a client.
3. C is free and 48 >= 30, so return C immediately.
4. D would also fit, but first fit does not inspect later nodes after a match.

An exact capacity match is eligible. Do not replace >= with >. Best fit would choose the smallest adequate free block, D here, and requires a different search. Whether either policy fragments less depends on the workload; neither eliminates fragmentation.

Finding is different from claiming

find_free_block is a query: it must leave the free flag, capacity, links, and head unchanged. Two searches for 30 therefore both return C. In the later allocator, the caller claims C by setting its free flag to 0 before giving its payload to a client. A search after that claim returns D.

This boundary matters: if a helper secretly claims a block, using it for inspection consumes storage. If an allocator forgets to claim the returned block, two live allocations can overlap. Our exercises are sequential; making a full search-and-claim operation safe across threads requires additional coordination.

If no node fits, this helper returns NULL. It does not call sbrk. A later allocation routine may then attempt checked growth: round the request under its alignment policy, check header addition and the signed increment bound, obtain storage, initialize its header, and link it only after success. Keeping the search helper small lets you test its contract independently.

Append without severing the chain

There are two cases:

Before	Link changes	After
Empty head	Set new node's next=NULL; set head to the new node	One-node list
A → B → NULL	Set new node C's next=NULL; set B's next=C	A → B → C → NULL

Do not overwrite head->next unless the head really is the tail. That would detach existing nodes. get_last_block returns NULL for the empty list and the node whose next is NULL otherwise. It does not remove the tail.

With only a head pointer, finding the tail and appending each take O(n) time. A maintained tail could make append O(1), but it introduces another invariant. Implement the supplied interface first.

Count reusable capacity correctly

For the A–D example, free count is 3 and total free capacity is 24+48+32=104. Exclude allocated B even though it is large. Exclude headers because the function reports payload capacity. Do not sum only blocks adequate for some recent request: the query has no request argument.

A request for 100 still cannot fit in any one block. Total free space and largest usable block answer different questions. Joining arbitrary list neighbors would claim intervening storage that might be live or outside the arena. Later coalescing needs both free status and verified physical adjacency.

These helpers use O(1) extra space; finding, counting, and summing can each visit O(n) nodes. The task bounds counts and sums so their declared return types can represent the result.

Complete a changing-list trace

Start with A(16 free) → B(64 used) → C(40 free) → NULL. Fill these results before opening the answer:

Operation	Result or resulting statistic
Find 40, without claiming	?
Find 40 again	?
Append D with capacity 24 and free=1	Free count=?, free capacity=?
Caller claims C; find 20	?

Check your state transitions

Both initial searches return C and preserve the list. Appending D yields three free nodes and capacity 16+40+24=80. Once the caller marks C allocated, a search for 20 skips A, B, and C and returns D. The remaining free capacity is 40, even though it is split across A and D.

Independently trace an initially empty list: append E(32 used), append F(32 free), search for 32 twice, then search for 33. Draw every next pointer and record all three search results. Explain why matching capacity alone is insufficient.

Build and diagnose

Implement get_last_block and append's empty/nonempty cases. Then add first fit and the two aggregate queries. Verify an empty list, a one-node list, an exact fit after a used node, repeated read-only searches, and an append that preserves at least three older nodes.

If a test hangs, inspect termination and cycles. If a search chooses a used block, inspect the combined eligibility predicate. If a count changes after searching, inspect unintended mutation. If earlier nodes disappear after append, inspect which link you updated. Use the quiz to diagnose those specific skills before combining these helpers into the next module's allocator.