Memory allocator with malloc, free and coalescing

Manage one arena of size bytes, addressed by offset from 0. You hand out and take back ranges of it, like malloc and free in C. Nothing is stored in the arena itself; track it in Python structures.

Part 1. malloc(n) -> address | None. Round n up to a multiple of align (a power of two, default 8), so every address is aligned. Use first fit: the lowest-addressed free range that is big enough, splitting off what is left. Return None when nothing fits; n <= 0 raises ValueError.

Part 2. free(address). A freed range merges with free neighbours on both sides, so freeing everything leaves one free range. Freeing an address twice, or an address that is not the start of an allocation, raises ValueError. stats() returns used, free, free_blocks, largest_free and fragmentation = 1 - largest_free / free (0 when nothing is free).

Part 3. A policy="best" option that takes the smallest range that fits (lowest address on ties) in O(log n) search time, and realloc(address, n): shrink in place, grow in place when the next range is free and big enough, otherwise move. If nothing fits, return None and leave the old allocation alone.

class Allocator:
    def __init__(self, size: int, align: int = 8, policy: str = "first"): ...
    def malloc(self, n: int) -> int | None: ...
    def free(self, addr: int) -> None: ...
    def realloc(self, addr: int, n: int) -> int | None: ...
    def stats(self) -> dict: ...

Example (Allocator(64, align=8)): malloc(5) -> 0, malloc(8) -> 8, malloc(17) -> 16 (takes 24 bytes), malloc(24) -> 40, malloc(1) -> None.