PDSC01

#include "myheap.h"
#include <stdio.h>
#include <stdlib.h>
#include <stddef.h>

/* http://moss.cs.iit.edu/cs351/assets/slides-malloc.pdf */

typedef struct node {
    char* start;
    char* end;
    size_t size;
    struct node *next;
} Node;

struct heap_s {
    char *area_dati;        /* Puntatore area dati */
    size_t size;            /* Dimensione massima */
    Node* free_list;        /* Lista partizioni libere */
    Node* used_list;        /* Lista partizioni occupate */
    Node *old_used_list;    /* Lista partizioni occupate pre-deframmentazione. */
    heap_policy_t policy;   /* Politica di allocazione */
};

heap_t heap;

heap_t *heapCreate(size_t heapSize) {
    /* Inizializzazione struttura heap: parto da un heap grande heapSize. Liste ancora vuote. Policy di default. */
    heap.area_dati = calloc(heapSize, sizeof(char));
    heap.size = heapSize;
    heap.free_list = NULL;
    heap.used_list = NULL;
    heap.policy = best_fit;

    /* Partizioni libere. Per adesso tutto l'heap è libero. */
    Node* node = (Node*)malloc(sizeof(Node));
    node->start = heap.area_dati;
    node->end = heap.area_dati + heapSize;
    node->size = heapSize;
    node->next = heap.free_list;
    heap.free_list = node;

    /* Partizioni usate */
    /* Nessuna, LOL */

    return &heap;
}

void heapDestroy(heap_t *h) {
    Node* p = heap.free_list;
    Node* tmp = NULL;
    while (p != NULL) {
        tmp = p;
        p = p->next;
        free(tmp);
    }

    p = heap.used_list;
    tmp = NULL;
    while (p != NULL) {
        tmp = p;
        p = p->next;
        free(tmp);
    }

    free(h->area_dati);
}

void *heapAlloc(heap_t *h, size_t size) {
    /* Per politiche best-fit e worst-fit. */
    size_t  this_size = 0,
            min_size = INT_MAX,
            max_size = 0;

    /* Puntatori ausiliari */
    Node* p = heap.free_list;
    Node* prev = NULL;
    Node* selected = NULL;

    /* Puntatore da restituire al chiamante. */
    void* pointer = NULL;

    switch (h->policy) {
        /* First fit: trovo la prima partizione libera che soddisfa la richiesta. */
        case first_fit: {
            while (p != NULL) {
                if (p->size >= size) {
                    selected = p;
                    break;
                }
                else
                    p = p->next;
            }
        }
            break;

        /* Worst fit: trovo la partizione piu' grande disponibile. */
        case worst_fit: {
            while (p != NULL) {
                this_size = p->size;
                if (this_size >= max_size) {
                    selected = p;
                    max_size = this_size;
                }
                p = p->next;
            }
        }
            break;

        /* Best fit: trovo la miglior partizione disponibile. */
        case best_fit:
            while (p != NULL) {
                this_size = p->size;
                if (this_size < min_size && this_size >= size) {
                    selected = p;
                    min_size = this_size;
                }
                p = p->next;
            }
            break;
    }

    /* Salvataggio del puntatore da restituire all'utente. */
    pointer = selected->start;

    /* Aggiornamento della used_list, con inserimento ordinato. */
    Node* node = (Node*)malloc(sizeof(Node));
    node->start = selected->start;
    /* Se chiedi 5 byte e il tuo blocco inizia dal byte 10, occupi i byte 10-11-12-13-14. */
    node->end = selected->start + size - 1;
    node->size = size;

    /* Inserimento ordinato nella lista used_list delle partizioni usate. */
    p = heap.used_list;
    prev = NULL;
    while (p != NULL) {
        if (p->start > node->start)
            break;
        prev = p;
        p = p->next;
    }
    if (prev != NULL) {
        node->next = prev->next;
        prev->next = node;
    }
    else {
        node->next = heap.used_list;
        heap.used_list = node;
    }

    /* Aggiornamento della free_list. */
    selected->start = selected->start + size;
    selected->size = selected->size - size;

    return pointer;
}

void heapFree(heap_t *h, void *p) {
    Node* tmp = heap.used_list;
    Node* prev = NULL;

    /* Rimozione della partizione passata dalla lista di quelle occupate */
    while (tmp != NULL) {
        if (p == tmp->start)
            break;
        prev = tmp;
        tmp = tmp->next;
    }
    prev->next = tmp->next;

    /* tmp punta alla partizione che sto liberando. Lo devo inserire nelle partizioni libere.
    Quindi niente free(). */

    /* Aggiunta ordinata della partizione alla lista delle partizioni libere. */
    Node* frl = heap.free_list;
    prev = NULL;

    while (frl != NULL) {
        if (frl->start > tmp->start)
            break;
        prev = frl;
        frl = frl->next;
    }

    if (prev != NULL) {
        tmp->next = prev->next;
        prev->next = tmp;
    }
    else {
        tmp->next = heap.free_list;
        heap.free_list = tmp;
    }

    /* Compattamento della lista delle partizioni libere. */
    tmp = heap.free_list;
    while (tmp != NULL && tmp->next != NULL) {
        if (tmp->end + 1 == tmp->next->start) {
            Node* me = tmp->next;
            char* start = tmp->start;
            char* end = tmp->next->end;
            size_t size = tmp->size + tmp->next->size;
            tmp->start = start;
            tmp->end = end;
            tmp->size = size;
            tmp->next = tmp->next->next;
            free(me);
        }
        tmp = tmp->next;
    }

    //int i = 3;
}

void heapSetPolicy(heap_t *h, heap_policy_t policy) {
    h->policy = policy;
}

void heapDefrag(heap_t *h) {
    Node* p = heap.used_list;
    char* cursor = heap.area_dati;
    size_t used_size = 0;

    /* Libero la vecchia tabella delle partizioni riallocate. */
    Node *poul = heap.old_used_list;
    while (poul != NULL) {
        Node *me = poul;
        poul = poul->next;
        free(me);
    }
    poul = NULL;
    heap.old_used_list = NULL;
    Node *pcoul = NULL;     /* Puntatore alla coda di old_used_list. */

    while (p != NULL) {
        /* La partizione occupata xyz prima era a... */
        Node *reallocated = (Node*)malloc(sizeof(Node));
        reallocated->start = p->start;
        reallocated->end = p->end;
        reallocated->size = p->size;

        used_size = used_size + p->size;

        /* Ora è a... */
        p->start = cursor;
        p->end = cursor + p->size - 1;
        cursor = p->end + 1;

        /* Inserimento in coda (così mantengo corrispondenza con used_list) */
        if (heap.old_used_list == NULL) {
            reallocated->next = heap.old_used_list;
            heap.old_used_list = reallocated;
            pcoul = heap.old_used_list;
        }
        else {
            pcoul->next = reallocated;
            reallocated->next = NULL;
            reallocated = pcoul;
        }

        p = p->next;
    }

    /* Libero la vecchia tabella delle partizioni libere. */
    /* Potrei fare un lavoro più fine, ma #sticazzi. */
    Node *pfl = heap.free_list;
    while (pfl != NULL) {
        Node *me = pfl;
        pfl = pfl->next;
        free(me);
    }
    pfl = NULL;
    heap.free_list = NULL;
    Node *compacted = (Node*)malloc(sizeof(Node));
    compacted->start = cursor;
    compacted->size = heap.size - used_size;
    compacted->end = cursor + compacted->size - 1;
    compacted->next = heap.free_list;
    heap.free_list = compacted;

    int i = 3;
}

void *heapNewPointer(heap_t *h, void *p) {
    Node *poul = heap.old_used_list;
    Node *pul = heap.used_list;
    while (poul != NULL) {
        if (poul->start == p)
            return pul->start;
        poul = poul->next;
        pul = pul->next;
    }
    return NULL;
}

void heapDefragClose(heap_t *h) {
    Node *poul = heap.old_used_list;
    while (poul != NULL) {
        Node *me = poul;
        poul = poul->next;
        free(me);
    }
    poul = NULL;
    heap.old_used_list = NULL;
}