Coalesce adjacent blocks in memory freelist

Challenge

Dynamic memory allocators (like dlmalloc and ptmalloc) suffer from external fragmentation when small blocks are freed. Coalescing traverses adjacent free blocks and merges them into a single larger block.

Your Task

Implement:

struct chunk_hdr {
    size_t size;
    int is_free;
    struct chunk_hdr *next;
};

int coalesce_free_chunks(struct chunk_hdr *head);

Traverse the chunk list starting at head. Whenever two adjacent chunks are both free (curr->is_free && curr->next->is_free), coalesce them.

Coalescing Rules

1. Add the second chunk's header and payload size to the first chunk: curr->size += sizeof(struct chunk_hdr) + curr->next->size.
2. Unlink the second chunk: curr->next = curr->next->next.
3. Do not advance curr immediately, because the newly enlarged chunk may be adjacent to another free chunk.
4. Return the total count of merge operations performed.

Input format

head: pointer to first chunk_hdr in linked list.

Output format

Returns integer count of coalesced merges.

Constraints

C11 freestanding. In-place linked list manipulation.

Starter code

#include <stddef.h>

/* The harness provides:
struct chunk_hdr {
    size_t size;
    int is_free;
    struct chunk_hdr *next;
};
*/

int coalesce_free_chunks(struct chunk_hdr *head) {
    (void)head;
    return 0;
}

Common mistakes

Advancing curr before checking if curr->next is also free; forgetting to include sizeof(struct chunk_hdr) in merged size.

Edge cases to handle

No free chunks returns 0; multiple consecutive free chunks all merge into one; single chunk list.

Background lessons

• free and ownership
• Memory safety — the whole bug class