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.