malloc with Reuse: The Real Allocator

This is the critical integration problem. Your malloc must now REUSE freed blocks instead of always calling sbrk.

The Key Test

void *p1 = my_malloc(100);
my_free(p1);
void *p2 = my_malloc(50);  // Should reuse p1's block!

assert(p2 == p1);  // MUST be true!

If p2 != p1, your allocator is broken - it's ignoring freed blocks.

How It Works

1. First malloc(100):
   ┌──────────────┬─────────────────────┐
   │ size=100     │     user data       │
   │ free=0       │                     │
   └──────────────┴─────────────────────┘
   ↑ free_list_head

2. After free():
   ┌──────────────┬─────────────────────┐
   │ size=100     │     (reusable)      │
   │ free=1  ◄─── │     AVAILABLE!      │
   └──────────────┴─────────────────────┘

3. Next malloc(50):
   - Search list for free block >= 50
   - Found! Block has size=100, that's >= 50
   - Mark it as used (free=0)
   - Return same pointer!

Your Task

Modify malloc to search for free blocks first:

// Find a free block that can fit 'size' bytes
// Returns NULL if no suitable block exists
block_header_t *find_free_block(size_t size);

// malloc with reuse:
// 1. Search for existing free block that fits
// 2. If found, mark as used and return it
// 3. If not found, request new space from OS
void *my_malloc(size_t size);

First-Fit Algorithm

block_header_t *find_free_block(size_t size) {
    block_header_t *current = free_list_head;
    while (current != NULL) {
        if (current->free && current->size >= size) {
            return current;  // Found one!
        }
        current = current->next;
    }
    return NULL;  // None found
}

Constraints

• MUST reuse freed blocks when possible
• Use first-fit (return first block that fits)
• Only call sbrk when no free block can satisfy the request
• Tests will verify that malloc -> free -> malloc returns the same address