L'allocation dynamique

Il est à présent temps d’aborder la troisième et dernière utilisation majeure des pointeurs : l’allocation dynamique de mémoire.

Comme nous vous l’avons dit dans le chapitre sur les pointeurs, il n’est pas toujours possible de savoir quelle quantité de mémoire sera utilisée par un programme. Par exemple, si vous demandez à l’utilisateur de vous fournir un tableau, vous devrez lui fixer une limite, ce qui pose deux problèmes :

  • la limite en elle-même, qui ne convient peut-être pas à votre utilisateur ;
  • l’utilisation excessive de mémoire du fait que vous réservez un tableau d’une taille fixée à l’avance.

De plus, si vous utilisez un tableau de classe de stockage statique, alors cette quantité de mémoire superflue sera inutilisable jusqu’à la fin de votre programme.

Or, un ordinateur ne dispose que d’une quantité limitée de mémoire vive, il est donc important de ne pas en réserver abusivement. L’allocation dynamique permet de réserver une partie de la mémoire vive inutilisée pour stocker des données et de libérer cette même partie une fois qu’elle n’est plus nécessaire.

La notion d'objet

Jusqu’à présent, nous avons toujours recouru au système de types et de variables du langage C pour stocker nos données sans jamais vraiment nous soucier de ce qui se passait « en dessous ». Il est à présent temps de lever une partie de ce voile en abordant la notion d’objet.

En C, un objet est une zone mémoire pouvant contenir des données et est composée d’une suite contiguë d’un ou plusieurs multiplets. En fait, tous les types du langage C manipulent des objets. La différence entre les types tient simplement en la manière dont ils répartissent les données au sein de ces objets, ce qui est appelé leur représentation (celle-ci sera abordée dans la troisième partie du cours). Ainsi, la valeur 1 n’est pas représentée de la même manière dans un objet de type int que dans un objet de type double.

Un objet étant une suite contiguë de multiplets, il est possible d’en examiner le contenu en lisant ses multiplets un à un. Ceci peut se réaliser en C à l’aide de l’adresse de l’objet et d’un pointeur sur unsigned char, les types signed char, char et unsigned char du C ayant toujours une taille d’un multiplet. Notez qu’il est impératif d’utiliser le type unsigned char afin d’éviter des problèmes de conversions.

L’exemple ci-dessous affiche les multiplets composant un objet de type int et un objet de type double en hexadécimal.

#include <stdio.h>


int main(void)
{
    int n = 1;
    double f = 1.;
    unsigned char *byte = (unsigned char *)&n;

    for (unsigned i = 0; i < sizeof n; ++i)
        printf("%x ", byte[i]);

    printf("\n");
    byte = (unsigned char *)&f;

    for (unsigned i = 0; i < sizeof f; ++i)
        printf("%x ", byte[i]);

    printf("\n");
    return 0;
}
Résultat
1 0 0 0 
0 0 0 0 0 0 f0 3f

Il se peut que vous n’obteniez pas le même résultat que nous, ce dernier dépend de votre machine.

Comme vous le voyez, la représentation de la valeur 1 n’est pas du tout la même entre le type int et le type double.

Malloc et consoeurs

La bibliothèque standard fournit trois fonctions vous permettant d’allouer de la mémoire : malloc(), calloc() et realloc() et une vous permettant de la libérer : free(). Ces quatre fonctions sont déclarées dans l’en-tête <stdlib.h>.

malloc
void *malloc(size_t taille);

La fonction malloc() vous permet d’allouer un objet de la taille fournie en argument (qui représente un nombre de multiplets) et retourne l’adresse de cet objet sous la forme d’un pointeur générique. En cas d’échec de l’allocation, elle retourne un pointeur nul.

Vous devez toujours vérifier le retour d’une fonction d’allocation afin de vous assurer que vous manipulez bien un pointeur valide.

Allocation d’un objet

Dans l’exemple ci-dessous, nous réservons un objet de la taille d’un int, nous y stockons ensuite la valeur dix et l’affichons. Pour cela, nous utilisons un pointeur sur int qui va se voir affecter l’adresse de l’objet ainsi alloué et qui va nous permettre de le manipuler comme nous le ferions s’il référençait une variable de type int.

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


int main(void)
{
    int *p = malloc(sizeof(int));

    if (p == NULL)
    {
        printf("Échec de l'allocation\n");
        return EXIT_FAILURE;
    }

    *p = 10;
    printf("%d\n", *p);
    return 0;
}
Résultat
10
Allocation d’un tableau

Pour allouer un tableau, vous devez réserver un bloc mémoire de la taille d’un élément multiplié par le nombre d’éléments composant le tableau. L’exemple suivant alloue un tableau de dix int, l’initialise et affiche son contenu.

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


int main(void)
{
    int *p = malloc(sizeof(int) * 10);

    if (p == NULL)
    {
        printf("Échec de l'allocation\n");
        return EXIT_FAILURE;
    }

    for (unsigned i = 0; i < 10; ++i)
    {
        p[i] = i * 10;
        printf("p[%u] = %d\n", i, p[i]);
    }

    return 0;
}
Résultat
p[0] = 0
p[1] = 10
p[2] = 20
p[3] = 30
p[4] = 40
p[5] = 50
p[6] = 60
p[7] = 70
p[8] = 80
p[9] = 90

Autrement dit et de manière plus générale : pour allouer dynamiquement un objet de type T, il vous faut créer un pointeur sur le type T qui conservera son adresse.

Notez qu’il est possible de simplifier l’expression fournie à malloc() en écrivant sizeof(int[10]) qui a le mérite d’être plus concise et plus claire.

La fonction malloc() n’effectue aucune initialisation, le contenu du bloc alloué est donc indéterminé.

free
void free(void *ptr);

La fonction free() libère le bloc précédemment alloué par une fonction d’allocation dont l’adresse est fournie en argument. Dans le cas où un pointeur nul lui est fourni, elle n’effectue aucune opération.

Retenez bien la règle suivante : à chaque appel à une fonction d’allocation doit correspondre un appel à la fonction free().

Dès lors, nous pouvons compléter les exemples précédents comme suit.

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


int main(void)
{
    int *p = malloc(sizeof(int));

    if (p == NULL)
    {
        printf("Échec de l'allocation\n");
        return EXIT_FAILURE;
    }

    *p = 10;
    printf("%d\n", *p);
    free(p);
    return 0;
}

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


int main(void)
{
    int *p = malloc(sizeof(int[10]));

    if (p == NULL)
    {
        printf("Échec de l'allocation\n");
        return EXIT_FAILURE;
    }

    for (unsigned i = 0; i < 10; ++i)
    {
        p[i] = i * 10;
        printf("p[%u] = %d\n", i, p[i]);
    }

    free(p);
    return 0;
}

Remarquez que même si le deuxième exemple alloue un tableau, il n’y a bien eu qu’une seule allocation. Un seul appel à la fonction free() est donc nécessaire.

calloc
void *calloc(size_t nombre, size_t taille);

La fonction calloc() attend deux arguments : le nombre d’éléments à allouer et la taille de chacun de ces éléments. Techniquement, elle revient au même que d’appeler malloc() comme suit.

malloc(nombre * taille);

à un détail près : chaque multiplet de l’objet ainsi alloué est initialisé à zéro.

Faites attention : cette initialisation n’est pas similaire à celle des variables de classe de stockage statique ! En effet, le fait que chaque multiplet ait pour valeur zéro ne signifie pas qu’il s’agit de la représentation du zéro dans le type donné. Si cela est par exemple vrai pour les types entiers, ce n’est pas le cas pour les pointeurs (rappelez-vous : un pointeur nul référence une adresse invalide qui dépend de votre système) ou pour les nombres réels (nous y reviendrons plus tard). De manière générale, ne considérez cette initialisation utile que pour les entiers et les chaînes de caractères.

realloc
void *realloc(void *p, size_t taille);

La fonction realloc() libère un bloc de mémoire précédemment alloué, en réserve un nouveau de la taille demandée et copie le contenu de l’ancien objet dans le nouveau. Dans le cas où la taille demandée est inférieure à celle du bloc d’origine, le contenu de celui-ci sera copié à hauteur de la nouvelle taille. À l’inverse, si la nouvelle taille est supérieure à l’ancienne, l’excédent n’est pas initialisé.

La fonction attend deux arguments : l’adresse d’un bloc précédemment alloué à l’aide d’une fonction d’allocation et la taille du nouveau bloc à allouer. Elle retourne l’adresse du nouveau bloc ou un pointeur nul en cas d’erreur.

L’exemple ci-dessous alloue un tableau de dix int et utilise realloc() pour agrandir celui-ci à vingt int.

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


int main(void)
{
    int *p = malloc(sizeof(int[10]));

    if (p == NULL)
    {
        printf("Échec de l'allocation\n");
        return EXIT_FAILURE;
    }

    for (unsigned i = 0; i < 10; ++i)
        p[i] = i * 10;

    int *tmp = realloc(p, sizeof(int[20]));

    if (tmp == NULL)
    {
        free(p);
        printf("Échec de l'allocation\n");
        return EXIT_FAILURE;
    }
    
    p = tmp;

    for (unsigned i = 10; i < 20; ++i)
        p[i] = i * 10;

    for (unsigned i = 0; i < 20; ++i)
        printf("p[%u] = %d\n", i, p[i]);
  
    free(p);
    return 0;
}
Résultat
p[0] = 0
p[1] = 10
p[2] = 20
p[3] = 30
p[4] = 40
p[5] = 50
p[6] = 60
p[7] = 70
p[8] = 80
p[9] = 90
p[10] = 100
p[11] = 110
p[12] = 120
p[13] = 130
p[14] = 140
p[15] = 150
p[16] = 160
p[17] = 170
p[18] = 180
p[19] = 190

Remarquez que nous avons utilisé une autre variable, tmp, pour vérifier le retour de la fonction realloc(). En effet, si nous avions procéder comme ceci.

p = realloc(p, sizeof(int[20]));

Il nous aurait été impossible de libérer le bloc mémoire référencé par p en cas d’erreur puisque celui-ci serait devenu un pointeur nul. Il est donc impératif d’utiliser une seconde variable afin d’éviter des fuites de mémoire.

Les tableaux multidimensionnels

L’allocation de tableaux multidimensionnels est un petit peu plus complexe que celles des autres objets. Techniquement, il existe deux solutions : l’allocation d’un seul bloc de mémoire (comme pour les tableaux simples) et l’allocation de plusieurs tableaux eux-mêmes référencés par les éléments d’un autre tableau.

Allocation en un bloc

Comme pour un tableau simple, il vous est possible d’allouer un bloc de mémoire dont la taille correspond à la multiplication des longueurs de chaque dimension, elle-même multipliée par la taille d’un élément. Toutefois, cette solution vous contraint à effectuer une partie du calcul d’adresse vous-même puisque vous allouez en fait un seul tableau.

L’exemple ci-dessous illustre ce qui vient d’être dit en allouant un tableau à deux dimensions de trois fois trois int.

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


int main(void)
{
    int *p = malloc(sizeof(int[3][3]));

    if (p == NULL)
    {
        printf("Échec de l'allocation\n");
        return EXIT_FAILURE;
    }

    for (unsigned i = 0; i < 3; ++i)
        for (unsigned j = 0; j < 3; ++j)
        {
            p[(i * 3) + j] = (i * 3) + j;
            printf("p[%u][%u] = %d\n", i, j, p[(i * 3) + j]);
        }

    free(p);
    return 0;
}
Résultat
p[0][0] = 0
p[0][1] = 1
p[0][2] = 2
p[1][0] = 3
p[1][1] = 4
p[1][2] = 5
p[2][0] = 6
p[2][1] = 7
p[2][2] = 8

Comme vous le voyez, une partie du calcul d’adresse doit être effectuée en multipliant le premier indice par la longueur de la première dimension, ce qui permet d’arriver à la bonne « ligne ». Ensuite, il ne reste plus qu’à sélectionner le bon élément de la « colonne » à l’aide du second indice.

Bien qu’un petit peu plus complexe quant à l’accès aux éléments, cette solution à l’avantage de n’effectuer qu’une seule allocation de mémoire.

Dans ce cas ci, la taille du tableau étant connue à l’avance, nous aurions pu définir le pointeur p comme un pointeur sur un tableau de 3 int et ainsi nous affranchir du calcul d’adresse.

int (*p)[3] = malloc(sizeof(int[3][3]));
Allocation de plusieurs tableaux

La seconde solution consiste à allouer plusieurs tableaux plus un autre qui les référencera. Dans le cas d’un tableau à deux dimensions, cela signifie allouer un tableau de pointeurs dont chaque élément se verra affecter l’adresse d’un tableau également alloué dynamiquement. Cette technique nous permet d’accéder aux éléments des différents tableaux de la même manière que pour un tableau multidimensionnel puisque nous utilisons cette fois plusieurs tableaux.

L’exemple ci-dessous revient au même que le précédent, mais utilise le procédé qui vient d’être décrit. Notez que puisque nous réservons un tableau de pointeurs sur int, l’adresse de celui-ci doit être stockée dans un pointeur de pointeur sur int (rappelez-vous la règle générale lors de la présentation de la fonction malloc()).

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


int main(void)
{
    int **p = malloc(sizeof(int*[3]));

    if (p == NULL)
    {
        printf("Échec de l'allocation\n");
        return EXIT_FAILURE;
    }

    for (unsigned i = 0; i < 3; ++i)
    {
        p[i] = malloc(sizeof(int[3]));

        if (p[i] == NULL)
        {
            printf("Échec de l'allocation\n");
            return EXIT_FAILURE;
        }
    }

    for (unsigned i = 0; i < 3; ++i)
        for (unsigned j = 0; j < 3; ++j)
        {
            p[i][j] = (i * 3) + j;
            printf("p[%u][%u] = %d\n", i, j, p[i][j]);
        }

    for (unsigned i = 0; i < 3; ++i)
        free(p[i]);

    free(p);
    return 0;
}

Si cette solution permet de faciliter l’accès aux différents éléments, elle présente toutefois l’inconvénient de réaliser plusieurs allocations et donc de nécessiter plusieurs appels à la fonction free().

Les tableaux de longueur variable

À côté de l’allocation dynamique manuelle (matérialisée par des appels aux fonctions malloc() et consœurs) que nous venons de voir, il existe une autre solution pour allouer dynamiquement de la mémoire : les tableaux de longueur variable (ou variable length arrays en anglais, souvent abrégé en VLA).

Définition

En fait, jusqu’à présent, nous avons toujours défini des tableaux dont la taille était soit déterminée, soit déterminable lors de la compilation.

int t1[3]; /* Taille déterminée */
int t2[] = { 1, 2, 3 }; // Taille déterminable

Toutefois, la taille d’un tableau étant spécifiée par une expression entière, il est parfaitement possible d’employer une variable à la place d’une constante entière. Ainsi, le code suivant est parfaitement correct.

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


int
main(void)
{
    size_t n;

    printf("Entrez la taille du tableau : ");

    if (scanf("%zu", &n) != 1)
    {
        printf("Erreur lors de la saisie\n");
        return EXIT_FAILURE;
    }

    int tab[n];

    for (size_t i = 0; i < n; ++i)
    {
        tab[i] = i * 10;
        printf("tab[%zu] = %d\n", i, tab[i]);
    }

    return 0;
}
Résultat
Entrez la taille du tableau : 10
tab[0] = 0
tab[1] = 10
tab[2] = 20
tab[3] = 30
tab[4] = 40
tab[5] = 50
tab[6] = 60
tab[7] = 70
tab[8] = 80
tab[9] = 90

Dans le cas où la taille du tableau ne peut pas être déterminée à la compilation, le compilateur va lui-même ajouter des instructions en vue d’allouer et de libérer de la mémoire dynamiquement.

Un tableau de longueur variable ne peut pas être initialisé lors de sa définition. Ceci tient au fait que le compilateur ne peut effectuer aucune vérification quant à la taille de la liste d’initialisation étant donné que la taille du tableau ne sera connue qu’à l’exécution du programme.

int tab[n] = { 1, 2, 3 }; // Incorrect

Une structure ne peut pas contenir de tableaux de longueur variable.

Utilisation

Un tableau de longueur variable s’utilise de la même manière qu’un tableau, avec toutefois quelques ajustements. En effet, s’agissant d’un tableau, s’il est employé dans une expression, il sera converti en un pointeur sur son premier élément. Toutefois, se pose alors la question suivante.

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


void affiche_tableau(int (*tab)[/* Heu ... ? */], unsigned n, unsigned m)
{
    for (unsigned i = 0; i < n; ++i)
        for (unsigned j = 0; j < m; ++j) {
            tab[i][j] = i * m + j;
            printf("tab[%u][%u] = %d\n", i, j, tab[i][j]);
        }
}


int
main(void)
{
    size_t n, m;

    printf("Entrez la longueur et la largeur du tableau : ");

    if (scanf("%zu %zu", &n, &m) != 2)
    {
        printf("Erreur lors de la saisie\n");
        return EXIT_FAILURE;
    }

    int tab[n][m];

    affiche_tableau(tab, n, m);
    return 0;
}

Comment peut-on préciser le type du paramètre tab étant donné que la taille du tableau ne sera connue qu’à l’exécution ? :euh:
Dans un tel cas, il est nécessaire d’inverser l’ordre des paramètres afin d’utiliser ceux-ci pour préciser au compilateur que le type ne sera déterminé qu’à l’exécution. Partant, la définition de la fonction affiche_tableau() devient celle-ci.

void affiche_tableau(size_t n, size_t m, int (*tab)[m]);
{
    for (unsigned i = 0; i < n; ++i)
        for (unsigned j = 0; j < m; ++j) {
            tab[i][j] = i * m + j;
            printf("tab[%u][%u] = %d\n", i, j, tab[i][j]);
        }
}

Ainsi, nous précisons au compilateur que le paramètre tab sera un pointeur sur un tableau de m int, m n’étant connu qu’à l’exécution.

Application en dehors des tableaux de longueur variable

Notez que cette syntaxe n’est pas réservée aux tableaux de longueur variable. En effet, si elle est obligatoire dans le cas de leur utilisation, elle peut être employée dans d’autres situations. Si nous reprenons notre exemple d’allocation d’un tableau multidimensionnel en un bloc et le modifions de sorte que l’utilisateur puisse spécifier la taille de ses dimensions, nous pouvons écrire ceci et dès lors éviter le calcul d’adresse manuel.

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


int main(void)
{
    size_t n, m;

    printf("Entrez la longueur et la largeur du tableau : ");

    if (scanf("%zu %zu", &n, &m) != 2)
    {
        printf("Erreur lors de la saisie\n");
        return EXIT_FAILURE;
    }

    int (*p)[m] = malloc(sizeof(int[n][m]));

    if (p == NULL)
    {
        printf("Échec de l'allocation\n");
        return EXIT_FAILURE;
    }

    for (size_t i = 0; i < n; ++i)
        for (size_t j = 0; j < m; ++j)
        {
            p[i][j] = (i * n) + j;
            printf("p[%zu][%zu] = %d\n", i, j, p[i][j]);
        }

    free(p);
    return 0;
}
Résultat
Entrez la longueur et la largeur du tableau : 3 3
p[0][0] = 0
p[0][1] = 1
p[0][2] = 2
p[1][0] = 3
p[1][1] = 4
p[1][2] = 5
p[2][0] = 6
p[2][1] = 7
p[2][2] = 8
Limitations

Pourquoi dans ce cas s’ennuyer avec l’allocation dynamique manuelle me direz-vous ? En effet, si le compilateur peut se charger de ce fardeau, autant le lui laisser, non ? Eh bien, parce que si cette méthode peut s’avérer salvatrice dans certains cas, elle souffre de limitations par rapport à l’allocation dynamique manuelle.

Durée de vie

La première limitation est que la classe de stockage des tableaux de longueur variable est automatique. Finalement, c’est assez logique, puisque le compilateur se charge de tout, il faut bien fixer le moment où la mémoire sera libérée. Du coup, comme pour n’importe quelle variable automatique, il est incorrect de retourner l’adresse d’un tableau de longueur variable puisque celui-ci n’existera plus une fois la fonction terminée.

int *ptr(size_t n)
{
    int tab[n];

    return tab; /* Incorrect */
}
Goto

La seconde limitation tient au fait qu’une allocation dynamique est réalisée lors de la définition du tableau de longueur variable. En effet, finalement, la définition d’un tableau de longueur variable peut être vue comme suit.

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


int
main(void)
{
    size_t n;

    printf("Entrez la taille du tableau : ");

    if (scanf("%zu", &n) != 1)
    {
        printf("Erreur lors de la saisie\n");
        return EXIT_FAILURE;
    }

    int tab[n]; /* int *tab = malloc(sizeof(int) * n); */

    /* free(tab); */
    return 0;
}

Or, assez logiquement, si l’allocation est passée, typiquement avec une instruction de saut comme goto, nous risquons de rencontrer des problèmes… Dès lors, le code suivant est incorrect.

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


int
main(void)
{
    size_t n;

    printf("Entrez la taille du tableau : ");

    if (scanf("%zu", &n) != 1)
    {
        printf("Erreur lors de la saisie\n");
        return EXIT_FAILURE;
    }

    goto boucle; /* Faux, car on saute l'allocation */

    if (n < 1000)
    {
        int tab[n]; /* int *tab = malloc(sizeof(int) * n); */

    boucle:
        for (size_t i = 0; i < n; ++i)
            tab[i] = i * 10;

        /* free(tab); */
    }

    return 0;
}

Dit plus formellement, il n’est pas permis de sauter après la définition d’un tableau de longueur variable si le saut est effectué en dehors de sa portée.

Taille des objets alloués

Une autre limitation vient du fait que la quantité de mémoire pouvant être allouée de cette manière est plus retreinte qu’avec malloc() et consœurs. Ceci tient à la manière dont la mémoire est allouée par le compilateur dans le cas des tableaux de longueur variable, qui diffère de celle employée par malloc(). Nous n’entrerons pas dans les détails ne s’agissant pas de l’objet de ce cours, mais globalement et de manière générale, évitez d’allouer un tableau de longueur variable si vous avez besoin de plus de 4 194 304 multiplets (soit le plus souvent environ 4 mégaoctets).

Gestion d’erreur

La dernière limitation tient à l’impossibilité de mettre en place une gestion d’erreur. En effet, il n’est pas possible de savoir si l’allocation a réussi ou échoué et votre programme est dès lors condamné à s’arrêter brutalement si cette dernière échoue.

Ce chapitre nous aura permis de découvrir la notion d’objet ainsi que le mécanisme de l’allocation dynamique. Dans le chapitre suivant, nous verrons comment manipuler les fichiers.

En résumé
  1. Un objet est une zone mémoire pouvant contenir des données composée d’une suite contiguë d’un ou plusieurs multiplets ;
  2. La représentation d’un type détermine de quelle manière les données sont réparties au sein d’un objet de ce type ;
  3. Il est possible de lire le contenu d’un objet multiplet par multiplet à l’aide d’un pointeur sur unsigned char ;
  4. La fonction malloc() permet d’allouer dynamiquement un objet d’une taille donnée ;
  5. La fonction calloc() fait de même en initialisant chaque multiplet à zéro ;
  6. La valeur zéro n’est pas forcément représentée en initialisant tous les multiplets d’un objet à zéro, cela dépend des types ;
  7. La fonction realloc() permet d’augmenter ou de diminuer la taille d’un bloc précédemment alloué avec malloc() ou calloc() ;
  8. Il est possible de préciser la taille d’un tableau à l’aide d’une variable auquel cas le compilateur se charge pour nous d’allouer et de libérer de la mémoire pour ce tableau ;
  9. L’utilisation de tels tableaux souffre de limitations par rapport à l’allocation dynamique manuelle.