Simple malloc in Python

malloc_simple.py

class Malloc:
    """
    A very small educational simulation of a malloc/free memory allocator.

    The allocator manages a fixed-size contiguous block of memory represented
    by a Python bytearray. Memory is tracked using a free list containing
    tuples of (start, size).

    Pointers returned by malloc are simply integer indices into the bytearray.

    This implementation demonstrates the core allocator ideas:
    - first-fit allocation
    - block splitting
    - freeing memory
    - coalescing adjacent free blocks
    """

    def __init__(self, size):
        """
        Initialize the simulated heap.

        Args:
            size (int): Total number of bytes available in the heap.

        Creates:
            memory: The raw byte buffer representing the heap.
            free_list: A list of free blocks represented as (start, size).
            allocated: Mapping from pointer -> allocated block size.
        """
        self.memory = bytearray(size)
        self.free_list = [(0, size)]  # (start, size)
        self.allocated = {}

    def malloc(self, size):
        """
        Allocate a block of memory.

        Uses a simple first-fit strategy: the first free block large
        enough for the request is used.

        If the block is larger than requested, it is split and the
        remainder stays in the free list.

        Args:
            size (int): Number of bytes requested.

        Returns:
            int: Pointer (index into the bytearray) representing the
            start of the allocated memory.

        Raises:
            MemoryError: If no free block can satisfy the request.
        """
        for i, (start, block_size) in enumerate(self.free_list):
            if block_size >= size:
                ptr = start
                self.allocated[ptr] = size

                # Shrink or remove free block
                if block_size == size:
                    self.free_list.pop(i)
                else:
                    self.free_list[i] = (start + size, block_size - size)

                return ptr

        raise MemoryError("Out of memory")

    def free(self, ptr):
        """
        Free a previously allocated block.

        The block is returned to the free list and adjacent free blocks
        are merged to reduce fragmentation.

        Args:
            ptr (int): Pointer returned from malloc.

        Raises:
            ValueError: If the pointer was not previously allocated.
        """
        if ptr not in self.allocated:
            raise ValueError("Invalid pointer")

        size = self.allocated.pop(ptr)
        self.free_list.append((ptr, size))
        self.free_list = self._merge_free_blocks()

    def _merge_free_blocks(self):
        """
        Merge adjacent free blocks to prevent fragmentation.

        The free list is sorted by starting address, and any blocks
        that are contiguous in memory are combined into a single block.

        Returns:
            list[tuple[int, int]]: A new free list with merged blocks.
        """
        blocks = sorted(self.free_list)
        merged = []

        for start, size in blocks:
            if not merged:
                merged.append((start, size))
                continue

            last_start, last_size = merged[-1]

            if last_start + last_size == start:
                merged[-1] = (last_start, last_size + size)
            else:
                merged.append((start, size))

        return merged