malloc

malloc.c

#include "malloc.h"

/*
 * nchunks
 *      Représente le nombre de chunk "disponible" pour ce chunk.
 *      Il y a donc nchunks - 1 chunks disponibles pour l'utilisateur.
 * next
 *      Pointe vers le prochain chunk de la liste.
 */
typedef struct chunk {
    size_t nchunks;
    struct chunk *next;
} chunk;

/*
 * MIN_CHUNK_ALLOC
 *      Défini le nombre minimum de chunk à allouer.
 */
#define MIN_CHUNK_ALLOC 2048

/*
 * Gère la liste de chunk.
 * ptr
 *      S'il est NULL, la fonction renvoie le premier chunk de la liste,
 *      ou NULL si la liste est vide.
 *      Sinon ptr devient le premier élément de la liste. La fonction
 *      retourne alors NULL
 */
chunk* firstChunk(chunk *ptr) {
    static chunk *first = NULL;

    if(ptr == NULL) {
        return first;
    }

    first = ptr;
    return NULL;
}

/*
 * Prends un chunk* en entrée (ptr), et le modifie pour créer deux chunks,
 * l'un de taille nchunks et l'autre de la taille restante.
 * Le premier est créé à la fin de l'espace disponible de ptr.
 * La fonction retourne alors l'adresse suivant ce chunk, castée en void*.
 */
void* alloc(chunk *ptr, size_t nchunks) {
    ptr->nchunks -= nchunks;
    chunk *mem = ptr + ptr->nchunks;
    mem->nchunks = nchunks;
    mem->next = NULL;
    return (void*)(mem + 1);
}

/*
 * Tout comme la fonction malloc, cette fonction renvoie un pointeur
 * sur une zone mémoire de taille size qui peut être utilisée sans
 * risques.
 * Si size == 0, ou que l'allocation est un échec, la fonction renvoie
 * NULL.
 */
void* malloc(size_t size) {
    if(size == 0) {
        return NULL;
    }

    //calcule le nombre de chunks nécessaires
    size_t nchunks = 2 + (size - 1) / 2;
    chunk *p = firstChunk(NULL), *prev = p;

    //on boucle sur tout les chunks en espérant en trouver
    //un qui ait assez de mémoire
    while(p) {
        //si on a la taille exacte, alors on enlève le chunk
        //de la liste, et on renvoie l'adresse suivante castée
        //en void*
        if(p->nchunks == nchunks) {
            prev->next = p ? NULL : p->next;
            p->next = NULL;
            return (void*)(p + 1);
        }

        //le chunk a plus de mémoire que nécessaire
        //on le coupe et on le renvoie
        else if(p->nchunks > nchunks) {
            return alloc(p, nchunks);
        }

        //on fait avancer l'"itérateur"
        prev = p;
        p = p->next;
    }

    //si on veut allouer plus que le minimum
    if(nchunks > MIN_CHUNK_ALLOC) {
        chunk *mem = (chunk*)sbrk(nchunks * sizeof(chunk));

        //si l'allocation échoue
        if((int)mem == -1) {
            return NULL;
        }

        //on mets à jour nchunks, mais pas next
        //car il ne sera jamais lu (enfin CETTE VALEUR
        //de next ne le sera jamais) donc c'est inutile
        mem->nchunks = nchunks;
        return (void*)(mem + 1);
    }

    //on alloue la quantité minimale de mémoire
    chunk *mem = (chunk*)sbrk(MIN_CHUNK_ALLOC * sizeof(chunk));

    //échec
    if((int)mem == -1) {
        return NULL;
    }

    //on mets à jour le chunk
    mem->nchunks = MIN_CHUNK_ALLOC;
    
    //on va chercher sa position dans la liste des chunks
    //ayant de la mémoire "libre"
    prev = p = firstChunk(NULL);

    while(p && p < mem) {
        prev = p;
        p = p->next;
    }

    //le chunk suivant mem est p
    mem->next = p;

    //prev == p == firstChunk(NULL)
    if(prev == p) {
        firstChunk(mem);
    }

    else {
        prev->next = mem;
    }

    //on split le chunk
    return alloc(mem, nchunks);
}

/*
 * Récupère la mémoire à l'adresse ptr ssi elle a été allouée à
 * l'aide de malloc().
 *
 * Attention le pointeur doit être considéré comme invalide après
 * un appel à free, il serait judicieux de le mettre à NULL ensuite.
 * 
 * e.g.:
 *
 *      char *str = malloc(42);
 *      //travail avec str
 *      free(str);
 *      str = NULL;
 *
 * Si deux appels à free sont fait sur le même pointeur sont fait
 * (même == alloué une seule fois) le comportement est indéterminé
 * (même si on peut dire que dans la version actuelle il boucle, mais
 * ça peut se modifier, mais bon autant rester "fidèle" à la spéc.
 *
 * BTW cette erreur peut se produire dans main_malloc2.c,
 * car les pointeurs ne sont par remis à NULL après la désallocation...
 */
void free(void* ptr) {
    if(ptr == NULL) {
        return;
    }

    chunk *p = firstChunk(NULL), *prev = p, *ptr_c = (chunk*)ptr - 1;

    //on trouve la position du chunk nouvellement libre
    while(p && p < ptr_c) {
        prev = p;
        p = p->next;
    }

    //le chunk suivant est p
    ptr_c->next = p;

    //prev == p == firstChunk(NULL)
    if(prev == p) {
        firstChunk(ptr_c);
    }

    else {
        //si les chunks prev & ptr_c sont consécutifs alors on les joint
        if(prev + prev->nchunks == ptr_c) {
            prev->nchunks += ptr_c->nchunks;
            ptr_c = prev;
        }

        else {
            prev->next = ptr_c;
        }
    }

    //si ptr_c & p sont consécutifs
    if(ptr_c + ptr_c->nchunks == p) {
        ptr_c->nchunks += p->nchunks;
        ptr_c->next = p->next;
    }
}

malloc.h

#ifndef MALLOC
#define MALLOC

#include <unistd.h>

void* malloc(size_t size);
void free(void *ptr);

#endif