// Blatt 05, Systemprogrammierung WS2011/2012
// FH Bielefeld, FB Technik, Carsten Gips
//
#include <iostream>


// Groesse des simulierten Heaps
#define MEM_POOL_SIZE ((unsigned long)(100))  //(1024*1024))
// "magischer" Wert
#define MAGIC_VALUE 0xDEADBEAF

using namespace std;

// Verwaltungsstruktur
struct MemBlock {
    size_t size;
    MemBlock *next;
};


// simulierter Heap
static char memPool[MEM_POOL_SIZE];
// Zeiger auf Freispeicherliste
static MemBlock *freeMem = 0;


// Deklaration der Speicherverwaltungsfunktionen
// Diese Funktionen muessen Sie selbst implementieren!
void *fbtMalloc(size_t size);
void fbtFree(void *ptr);
void init();
void print();

// main
int main(int argv, char* argc[])
{

    float* f = (float*)fbtMalloc(sizeof(float));
    print();

    return 0;
}

void* fbtMalloc(size_t size)
{
    if (freeMem == 0)
    {
        init();
    }

    // aktueller Speicherbereich
    MemBlock* tmp = freeMem;
    // vorheriger Speicherbereich
    MemBlock* prev = 0;

    while(tmp)
    {
        // teile Speicherbereich auf und alloziere einen
        if (tmp->size > size + 2*sizeof(MemBlock) + 8)
        {
            // naechster Speicherbereich
            // und zu allozierender Speicherbereich
            MemBlock* next = tmp->next;
            MemBlock* ptr = tmp;

            // naechster/neuer Speicherbereich
            // und aktuallisiere Groesse vom neuen Speicherbereich
            tmp += (size + sizeof(MemBlock));
            tmp->size = ptr->size - (size + sizeof(MemBlock));

            // aktuallisiere Groesse vom zu allozierenden Speicherbereich
            // und markiere zu allozierenden Speicherbereich
            ptr->size = size;
            ptr->next = (MemBlock*)MAGIC_VALUE;

            // verkette naechsten Speicherbereich
            tmp->next = next;

            // verkette vorherigen Speicherbereich, falls vorhanden
            // ansonsten verschiebe Pointer von freeMem auf neuen Speicherbereich
            if (prev)
                prev->next = tmp;
            else
                freeMem = tmp;

            // gebe allozierten Speicherbereich zurueck
            return (void*)ptr;
        }
        // alloziere Speicherbereich
        else if (tmp->size > size)
        {
            MemBlock* ptr = tmp;
            tmp = tmp->next;
            ptr->size = size;
            ptr->next = (MemBlock*)MAGIC_VALUE;

            if (prev)
                prev->next = tmp;
            else
                freeMem = tmp;

            return (void*)ptr;
        }
        prev = tmp;
        tmp = tmp->next;
    }

    return 0;
}

void fbtFree(void* ptr)
{
    MemBlock* tmp = (MemBlock*)ptr;
    if (tmp->next == (MemBlock*)MAGIC_VALUE)
    {
        tmp->next = freeMem;
        freeMem = tmp;
    }
    else
    {
        cout << "Fehler: Speicherbereich ist nicht alloziert." << endl;
    }
}

void init()
{
    freeMem = (MemBlock*)memPool;
    freeMem->size = MEM_POOL_SIZE;
    freeMem->next = 0;
}

void print()
{
    MemBlock* tmp = freeMem;

    while(tmp)
    {
        cout << "freier Speicherbereich: " << tmp->size << ", Adresse: " << tmp << endl;
        tmp = tmp->next;
    }
}