Allocation dynamique¶

Pourquoi ?¶

L'allocation dynamique permet d'utiliser de la mémoire en dehors de la pile (dans la zone appellée tas). L'interet principal est que la durée de vie de cette mémoire est indépendante de la pile. Ainsi, une fonction peut réserver de la mémoire et se terminer, la mémoire reste disponnible.

Exemple : on voudrait une fonction responsable de creer un tableau de taille donnée en paramètre. On pourrait être tenté d'écrire

int * creer_tableau(int taille)
{
    int tab[taille];
    return tab;
}

Ce code est faux pour deux raisons :

il est interdit de creer des tableaux de pile de taille contenue dans une variable en ANSI C

int tab[2]; /* ok */
#define TRUC 2
int tab[TRUC]; /* ok */
int n = 2;
int tab[n]; /* pas ok ! */

la mémoire allouée pour le tableau se trouve sur la pile de la fonction. Lorsque l'ont fait return tab, on renvoie donc l'adresse d'une variable locale dont l'emplacement mémoire risque d'être réutilisé pour autre chose par le système dès la fin de la fonction. Il faut donc écrire :

int * creer_tableau(int taille)
{
    int * tab = ... /* appel à une fonction d'allocation */
    return tab;
}

Comment ?¶

Pour manipuler la mémoire allouée sur le tas, les fonctions ont donc besoins de pointeurs, qui seront eux des variables de pile normales. Les fonctions d'allocation, comme malloc() ou calloc() vont donc renvoyer des adresses mémoires. A charge du programmeur de sauvegarder ces adresses dans des pointeurs.

Voici un exemple avec malloc() :

int * creer_tableau(int taille)
{
    int * tab = (int*) malloc(sizeof(int)*taille);
    return tab;
}

malloc() prend en paramètre la taille en octet que l'on souhaite allouer. Ici on veut taille entiers, il faut donc commencer par calculer la taille en octer d'un entier, grace à l'opérateur sizeof(), et la multiplier par notre variable taille qui est le nombre d'entier que l'on veut.

malloc() renvoie un pointeur générique, noté avec le type spécial void* Pour permettre au compilateur de vérifier que l'affectation int * tab = ... est correcte au niveau du typage, il est donc d'usage de caster le résultat de malloc, d'où le int* entre parenthèses.

Il existe une autre fonction d'allocation, appelée calloc(), plus spécifiquement dédié à l'allocation de tableau. Celle ci prend deux paramètres : le nombre de cases et la taille en octet d'une case. De plus les valeurs du tableau sont initialisées à 0.

Il existe enfin une troisième fonction, realloc() permettant de modifier la taille d'une zone mémoire précédemment allouée. Attention, un appel à realloc provoque potentiellement une copie de la zone mémoire lorsqu'il n'est pas possible d'étendre la zone mémoire considérée sans la déplacer.

Dangers ?¶

Le principal danger est de perdre les adresses. En effet, pour libérer la mémoire, ces adresses sont nécessaires. Par exemple :

void une_fonction()
{
    int * tab = creer_tableau(100);
    ... /* utilisation du tableau */
} /* fin de la fonction */

Ici lorsque la fonction est terminée, sa pile est libérée, et plus aucune variable accessible sur la pile ne contient l'adresse du tableau (qui est sur la tas). Il n'est donc plus possible de libérer la mémoire. Il faut soit que la fonction libère la mémoire en ajoutant la ligne :

free(tab);

soit qu'elle renvoie l'adresse du tableau afin qu'il soit libéré dans une autre fonction plus tard.

Le deuxième danger est que les fonctions d'allocation peuvent échouer (par exemple lorsqu'il n'y a pas assez de mémoire disponible. Dans ce cas elles renvoient une valeur de pointeur spéciale notée NULL (constante définie dans stdlib.h). Essayer d'accéder à l'adresse NULL provoque toujours un segmentation fault. Et la, à charge du programmeur de retrouver d'où vient l'erreur... Afin de lui faciliter la vie, il faut donc prendre l'habitude de toujours tester le retour des fonctions d'allocations. On écrira donc :

int * creer_tableau(int taille)
{
    int * tab = (int*) malloc(sizeof(int)*taille);
    if(tab==NULL){
        fprintf(stderr,"probleme d'allocation dans creer_tableau");
        exit(1);
    }
    return tab;
}

exit() est une fonction de stdlib.h permettant de mettre fin au programme immédiatement.

sizeof¶

Attention avec sizeof(), comme indiqué plus haut, il ne s'agit pas d'une fonction mais d'un opérateur, même si la syntaxe ressemble à un appel de fonction. Il faut lui mettre dans les parenthèse le nom d'un type. Si vous mettez une variable, ca marche quand même et ca renvoie la taille du type, ce comportement peut préter à confusion.

Exemple :

void f(int * tab)
{
    printf("%d\n",sizeof(tab));
}
int main()
{
    int tab[10];
    f(tab);
    return 0;
}

Qu'affiche ce programme, pourquoi ?

Quelques exercices¶

Ecrire un programme qui alloue un tableau de 30 float avec malloc puis l'affiche.
modifiez votre programme pour qu'il fasse l'allocation avec calloc, l'affichage est-il différent ?
si vous ne l'avez pas fait, ajouter les instructions pour libérer la mémoire
ajoutez l'option -g à la compilation du programme. Lancez ensuite la commande valgrind ./a.out : cet utilitaire permet de tracer les allocations / libération de mémoire, et vous dit si vous avez bien tout libéré. Commentez les appels à free() dans votre code et restestez.
ecrire une fonction qui prend en paramètre deux chaine de caractères et renvoie une nouvelle chaine concaténant les deux paramètres. Par exemple
```
char * s = concat("sa","lut");
printf("%s\n",s);
```
doit afficher salut Le résultat sera alloué avec un malloc(). Il faudra donc penser à faire à ajouter un free()...
regarder le manuel de la fonction getline() : il existe de nombreuses fonctions qui réalisent des allocations mémoire. Il faut bien le savoir quand on les utilise car c'est alors à nous d'appeler les free() correspondant.

Tableau à deux dimensions¶

ecrire une fonction int** alloue(int n, int m); qui alloue un tableau de char à deux dimensions de n lignes et m colones.
ecrire une fonction void libere(int** tab, int n, int m);qui libère la mémoire associée.

Application au mini projet¶

On souhaite supprimer les constantes NBC et NBL, et pouvoir gérer des grilles de tailles différentes. Pour cela, nous allons ajouter dans grid.h un nouveau type structuré Grid contenant :
- un char** grid
- deux entiers nbc et nbl
Ajoutez dans grid.h/.c la fonction Grid* allocate_grid(int n, int m); qui :
- alloue une variable de type Grid sur le tas
- alloue son champs grid (cf exercice plus haut sur l'allocation de tableau à deux dimensions)
Ajoutez la fonction free_grid(Grid *); qui libère toute la mémoire occupée par la grille (le tableau à deux dimensions puis la variable de type Grid.
Modifiez toutes vos fonctions pour qu'elle prennent en paramètre des Grid* à la place de char grille[NBL][NBC+1]
Modifiez le programme pour que lorsque l'option de lecture depuis un fichier n'est pas passée, le programme lise quand même la grille dans le fichier levels/default.
Il faut adapter la fonction de lecture dans un fichier, car on ne connaît plus la taille. Pour connaître le nombre de lignes, il faudra faire une première lecture complète du fichier. Pour le nombre de colonne, on se base sur la première ligne. Modifiez la fonction pour qu'elle utilise getline(), cela vous permettra de ne pas fixer de taille max pour les lignes. Attention à ne pas faire de fuite mémoire (utilisez valgrind pour vérifier). Si le fichier est mal formé (les lignes ne font pas toutes la même taille par exemple), quittez le programme proprement en affichant un message d'erreur. Squelette du code :

int nbl,nbc;
size_t size_buf=0;
FILE * stream;
char * buf=NULL;
Grid * g;
int i,j;

stream = ... 
nbl = count_nb_line(stream); /* fonction a écrire */
rewind(...); /* pour remettre la position de lecture du fichier au début, voir la manpage */
nbc = getline(&buf,&size_buf,stream);
if(nbc==-1){ /* erreur, le fichier est certainement mal formé */ ...}
else nbc--; /* getline compte le retour à la ligne */
g=allocate_grid(nbl,nbc);
copy(buf,g->grid[0]); /* fonction a écrire, qui ne copie que les caractères que l'on veut (pas \0 ni \n) */
for (i=1;i<nbl;i++)
{
    int size_tmp = getline(&buf,&size_buf,stream);
    if(size_tmp!=nbc+1){
        /* il y a un probleme, il faut quitter le programme */
        ...
    }
    copy(buf,g->grid[i]); 
}
free(buf);

Pourquoi n'y a t il qu'un free() alors que getline qui fait des allocations dynamique est appellée dans une boucle ? (la réponse est dans la page de manuel de la fonction getline :))
Assurez vous que l'on ne stocke plus les '\0' ou des '\n' dans la mémoire. Attention, la fonction debug() doit toujours marcher (il faudra sûrement la réécrire).

Rendu¶

N'oubliez pas de pousser votre travail sur gitlab !

Dans un répertoire nommé login_tp5 copiez vos .c, makefile et .h. Vous pouvez y ajouter un fichier texte README si vous avez des choses à expliquer à joindre à votre rendu. Depuis le répertoire parent, tapez la commande tar czf login_tp5.tgz login_tp5. Déposez sur blackboard le fichier obtenu.