Implement a Simple Memory Allocator

Design and implement a simplified memory allocator exposing malloc(size) and free(ptr) over a single fixed-size heap (a contiguous byte array). The allocator must not request more memory from the operating system after initialization — it only manages the bytes it was given.

Walk from a straightforward correct implementation to an optimized one, and analyze the trade-offs.

Constraints & Assumptions

• The heap is one contiguous region, e.g. byte[N], with N fixed at init.
• malloc(size) returns a pointer/offset to a block of at least size usable bytes, or fails (returns null / sentinel) if no block can satisfy the request.
• free(ptr) marks a previously-allocated block reusable. You may assume ptr was returned by a prior malloc (but discuss defending against misuse).
• Single-threaded for the core problem; concurrency is a follow-up.
• Allocations should be aligned to a machine-friendly boundary (e.g. 8 or 16 bytes).

Clarifying Questions to Ask

• What is the heap size N, and the expected allocation size distribution (many small vs. few large)?
• What alignment guarantee must payloads satisfy?
• What is the contract for malloc(0), double-free, and freeing an invalid pointer — defined behavior or undefined?
• Are we optimizing for allocation latency, memory utilization, or worst-case fragmentation?
• Is the allocator single-threaded, or must it be thread-safe?

Part 1 — First-fit allocator with splitting

Implement malloc/free using a first-fit strategy: linearly scan the blocks (or a free list) and use the first free block large enough. When a chosen free block is larger than requested, split it so the remainder stays available. State the time/space complexity of each operation.

What This Part Should Cover

• A correct block model: header layout, the payload-vs-header pointer arithmetic, and how alignment is enforced.
• A working first-fit scan with a clear, justified MIN_PAYLOAD / minimum-split threshold.
• Correct per-operation complexity for malloc, free, and split, with reasoning rather than asserted constants.

Part 2 — Coalescing and fragmentation

Show how free should handle adjacent free blocks (the previous and next physical neighbors), and explain how this reduces external fragmentation. Distinguish external from internal fragmentation.

What This Part Should Cover

• A precise external-vs-internal fragmentation distinction (scattered gaps between blocks vs. slack inside a block).
• Two-sided coalescing with the previous and next physical neighbors, and why address-ordering makes the merge $O(1)$.
• An honest account of what coalescing does and does not buy — it limits, but cannot eliminate, external fragmentation.

Part 3 — Best-fit optimization

Propose an optimization that chooses the smallest free block that still fits the request, and pick a data structure that makes the lookup efficient. Justify the structure: explain why a plain min-heap keyed by size is not a clean fit, and what works instead.

What This Part Should Cover

• Names the query shape precisely (smallest free block with usable size $\geq$ request — a lower-bound / successor query, not a global minimum) and uses it to rule out a plain min-heap.
• Picks a structure whose operations match that query (ordered map / balanced BST keyed by size, or segregated size-class lists) and reasons about, rather than just names, the candidates.
• Recognizes that best-fit needs a second size-ordered index alongside the physical list, and states the consequence: every split and coalesce must keep both in sync.

Part 4 — Complexity & trade-off analysis

Compare first-fit and best-fit on allocation time, space/metadata overhead, and fragmentation behavior. State when each is preferable.

What This Part Should Cover

• A side-by-side comparison across allocation cost, free/coalesce cost, metadata overhead, and long-run fragmentation behavior.
• The key insight that minimizing leftover per allocation (best-fit) does not automatically minimize long-run fragmentation, and can manufacture tiny unusable slivers.
• A workload-aware verdict for latency vs. utilization vs. worst-case fragmentation, with no blanket "best-fit is better."