Implement a memory allocator with malloc/free

Problem

You are implementing a simplified memory allocator over a contiguous memory region.

Initialize the allocator with a fixed total size:

• allocator(totalSize) creates an allocator that manages bytes indexed from 0 to totalSize-1.

Implement two operations:

• malloc(size) -> pointer

• Allocates a contiguous block of size bytes.

• Returns a pointer representing the allocated block (you may define this as an integer start index, or an opaque handle that can later be passed to free).

• If no contiguous block of at least size bytes is available, return a null/invalid pointer (e.g., -1 or null).

• free(pointer) -> bool

• Frees the block previously returned by malloc.

• Returns true if the pointer was valid and the block was freed, otherwise returns false (e.g., double-free or unknown pointer).

Requirements / Clarifications

• The allocator must support many interleaved malloc and free calls.
• Freed space should become available for future allocations.
• You must correctly handle merging/coalescing of adjacent free blocks to reduce fragmentation.
• Discuss (and aim for) better-than-linear performance per operation if possible (e.g., around (O(\log n)) for finding a suitable free block).

Example (one possible interpretation)

• allocator(10)
• p1 = malloc(3) might return 0 (allocates [0..2])
• p2 = malloc(4) might return 3 (allocates [3..6])
• free(p1) frees [0..2]
• p3 = malloc(2) might return 0 (reuses part of [0..2])

What to deliver

Explain and implement the data structures and algorithms needed to support malloc and free efficiently, including coalescing and pointer validation.