malloc.h

#ifndef MALLOC_H
#define MALLOC_H

#include <memoryapi.h>
#include <stdbool.h>
#include <stdio.h>
#include <stdlib.h>
#include <windows.h>

#include <cmath>
#include <stdexcept>

#include "linked_list.h"

#define HEAP_SIZE 8000000

typedef struct {
    void* location;
    size_t size;
    bool freed;
} Block;

static LinkedList<Block> blockList = LinkedList<Block>();

void* myMalloc(const size_t size) {
    if (blockList.getHead() == nullptr) {
        SYSTEM_INFO sysInfo;
        GetSystemInfo(&sysInfo);

        float pageSize = (float)sysInfo.dwPageSize;
        int realHeapSize = std::ceil(HEAP_SIZE / pageSize) * pageSize;

        Block initialBlock;
        initialBlock.size = realHeapSize;
        initialBlock.location = VirtualAlloc(NULL, realHeapSize, MEM_RESERVE | MEM_COMMIT, PAGE_READWRITE);
        initialBlock.freed = true;
        blockList.shift(initialBlock);
    }

    Node<Block>* head = blockList.getHead();
    while (head->data.size < size || !head->data.freed) {
        head = head->next;
    }

    Block block;
    // Reserve a new block
    if (head->data.size > size) {
        block.size = size;
        block.freed = false;
        block.location = head->data.location;

        head->data.location = static_cast<char*>(head->data.location) + size;
        head->data.size -= size;

        blockList.shift(block);
    } else {
        block = head->data;
        block.freed = false;
    }

    return block.location;
}

void myFree(const void* location) {
    Node<Block>* ptr = blockList.getHead();
    while (ptr != nullptr && ptr->data.location != location)
        ptr = ptr->next;

    if (ptr == nullptr) {
        char buf[64];
        snprintf(buf, sizeof(buf), "Unknown memory ptr %p", location);
        throw std::runtime_error(buf);
    }

    ptr->data.freed = true;

    Node<Block>* freed = ptr;
    // Merge right
    ptr = freed->next;
    while (ptr != nullptr && ptr->data.freed) {
        freed->data.size += ptr->data.size;
        freed->next = ptr->next;

        Node<Block>* temp = ptr;
        ptr = ptr->next;

        // Free the node
        delete temp;
    }

    // Merge left
    ptr = freed->prev;
    while (ptr != nullptr && ptr->data.freed) {
        ptr->data.size += freed->data.size;
        ptr->next = freed->next;
        if (ptr->next != nullptr)
            ptr->next->prev = ptr;

        delete freed;
        freed = ptr;
    }
}

void debugBlock(const Block& block) {
    printf("Block:\n");
    printf("\tLocation: %p\n", block.location);
    printf("\tSize:     %zu\n", block.size);
    printf("\tIs free:  %d\n", block.freed);
}

void debugHeap() {
    Node<Block>* ptr = blockList.getHead();
    while (ptr != nullptr) {
        debugBlock(ptr->data);
        printf("\n");
        ptr = ptr->next;
    }
}

#endif