basic/src/Memory.c

#include "Memory.h"

#include <stdio.h>
#include <stdlib.h>
#include <string.h>

typedef struct {
    u32 units;
    i32 next;
} Slot;

static Slot* memory = nullptr;
static u32 maxUnits = 0;
static Slot baseSlot = {.units = 0, .next = -1};
static Slot* slots = &baseSlot;
static constexpr i32 CANARY = (i32)0xEFBEADDE;

static i32 memoryGetSlotIndex(const Slot* s) {
    return (i32)(s - memory);
}

void memoryInit(void* p, u32 n) {
    u32 offset = (u64)p % sizeof(Slot);
    if(offset > 0) {
        offset = (u32)sizeof(Slot) - offset;
    }

    memory = (Slot*)(void*)((char*)p + offset);
    maxUnits = (n - offset) / sizeof(Slot);

    Slot* s = memory;
    s->next = -1;
    s->units = maxUnits;
    slots->next = 0;
}

static Slot* memoryNextSlot(const Slot* s) {
    if(s->next == -1) {
        return nullptr;
    }
    return memory + s->next;
}

void* memoryAllocate(size_t bytes) {
    if(bytes == 0) {
        return nullptr;
    }
    u32 units = (u32)((bytes + sizeof(Slot) - 1) / sizeof(Slot) + 1);
    if(units > maxUnits) {
        return nullptr;
    }
    Slot* previous = nullptr;
    Slot* current = slots;
    while(current != nullptr) {
        if(current->units >= units) {
            break;
        }
        previous = current;
        current = memoryNextSlot(current);
    }
    if(current == nullptr) {
        return nullptr;
    }
    if(current->units == units) {
        previous->next = current->next;
    } else {
        Slot* newSlot = current + units;
        newSlot->next = current->next;
        newSlot->units = current->units - units;
        previous->next = memoryGetSlotIndex(newSlot);
    }
    current->next = CANARY;
    current->units = units;
    return current + 1;
}

void memoryFree(void* p) {
    if(p == nullptr) {
        return;
    }
    Slot* s = (Slot*)p - 1;
    if(s->next != CANARY) {
        fprintf(stderr, "free with corupt canary\n");
        abort();
    }
    Slot* previous = slots;
    Slot* current = memoryNextSlot(slots);
    while(current != nullptr && current < s) {
        previous = current;
        current = memoryNextSlot(current);
    }

    if(current == nullptr) {
        s->next = -1;
    } else if(s + s->units == current) {
        s->units += current->units;
        s->next = current->next;
    } else {
        s->next = memoryGetSlotIndex(current);
    }

    if(previous + previous->units == s) {
        previous->units += s->units;
        previous->next = s->next;
    } else {
        previous->next = memoryGetSlotIndex(s);
    }
}

void memoryDump() {
    // for(size_t i = 0; i < maxUnits * sizeof(Slot); i++) {
    //     fprintf(stderr, "%02x", (unsigned)((char*)memory)[i] & 0xFF);
    //     if((i + 1) % 30 == 0) {
    //         fputc('\n', stderr);
    //     }
    // }
    // fputc('\n', stderr);
    fputs("Free Slots ", stderr);
    u32 sum = 0;
    Slot* current = memoryNextSlot(slots);
    while(current != nullptr) {
        fprintf(stderr, "%u, ", current->units);
        sum += current->units;
        current = memoryNextSlot(current);
    }
    fprintf(stderr, " = %u\n", sum);
}

i32 memoryConvertToIndex(void* p) {
    return memoryGetSlotIndex((Slot*)p);
}

void* memoryConvertToPointer(i32 index) {
    return memory + index;
}