|
== Gestion dynamique de la mémoire ==
Les déclarations de variables en C et dans beaucoup d'autres langages ont une limitation très importante : la taille des variables doit être connue à la compilation. Cela pose problème quand on ne sait qu'à l'exécution le nombre de données qu'on doit traiter. Pour résoudre ce problème, et pouvoir décider durant l'exécution d'un programme du nombre de variables à créer, il faudra nécessairement passer par de l'allocation dynamique de mémoire. Avec ce système, le programmeur dispose de fonctions qui permettent de demander au système une zone mémoire d'une certaine taille, qu'il pourra utiliser comme il le souhaite. En C, ces fonctions sont disponibles dans l'en-tête <ttcode><stdlib.h></ttcode>.
L'un des principaux avantages qu'offre le langage C est sa capacité à fournir au programmeur un contrôle poussé sur la gestion de la mémoire. Cette liberté nécessite néanmoins une grande rigueur, tant les problèmes pouvant survenir sont nombreux et souvent difficiles à diagnostiquer. On peut dire sans prendre beaucoup de risque que la plupart des erreurs de programmation en C, ont pour origine une mauvaise utilisation des fonctions de gestion de la mémoire. Il ne faut pas sous-estimer la difficulté de cette tâche. Autant cela est trivial pour un programme de quelques centaines de lignes, autant cela peut devenir un casse-tête quand ledit programme a subi des changements conséquents, pas toujours faits dans les règles de l'art.
=== <code>free</code>: libération de mémoire ===
Le C ne possède pas de mécanisme de ramasse-miettes, la mémoire allouée dynamiquement par un programme doit donc être explicitement libérée. La fonction <ttcode>free</ttcode> permet de faire cette libération.
<source lang="c">
L'utilisation du pointeur après libération de la zone allouée (ou la double libération d'une même zone mémoire) est une erreur courante qui provoque des résultats imprévisibles. Il est donc conseillé :
* d'attribuer la valeur nulle (<ttcode>NULL</ttcode>) au pointeur juste après la libération de la zone pointée, et à tout autre pointeur faisant référence à la même adresse,
* de tester la valeur nulle avant toute utilisation d'un pointeur.
De plus, donner à <ttcode>free</ttcode> l'adresse d'un objet qui n'a pas été alloué par une des fonctions d'allocation cause un comportement indéfini.
=== <code>calloc</code> : allocation avec initialisation à 0 ===
La fonction <ttcode>calloc</ttcode> permet d'allouer une zone mémoire dont tous les bits seront initialisés à 0. Son prototype est légèrement différent de celui de <ttcode>malloc</ttcode>, et est pratique pour l'allocation dynamique de tableaux.
Syntaxe :
</source>
De manière similaire à <ttcode>malloc</ttcode>, <ttcode>calloc</ttcode> retourne un pointeur de type <ttcode>void*</ttcode> pointant une zone de <ttcode>''nb_element''*''taille''</ttcode> octets allouée en mémoire, dont tous les bits seront initialisés à 0, ou retourne un pointeur nul en cas d'échec.
Exemple :
</source>
Notez que <ttcode>calloc</ttcode> place tous les ''bits'' à zéro, mais que ce n'est pas nécessairement une représentation valide pour un pointeur nul ni pour le nombre zéro en représentation flottante. Ainsi, pour initialiser à zéro un tableau de <ttcode>double</ttcode> de manière portable, par exemple, il est nécessaire d'assigner la valeur <ttcode>0.0</ttcode> à chaque élément du tableau. Étant donné qu'on initialise chaque élément « manuellement », on peut dans ce cas utiliser <ttcode>malloc</ttcode> plutôt que <ttcode>calloc</ttcode> (la première étant normalement beaucoup plus rapide que la seconde).
=== <code>realloc</code> ===
Il arrive fréquemment qu'un bloc alloué n'ait pas la taille suffisante pour accueillir de nouvelles données. La fonction <ttcode>realloc</ttcode> est utilisée pour changer (agrandir ou réduire) la taille d'une zone allouée par <ttcode>malloc</ttcode>, <ttcode>calloc</ttcode>, ou <ttcode>realloc</ttcode>.
Syntaxe :
* si ''ancien_bloc'' est nul, l'appel est équivalent à <code>malloc(nouvelle_taille)</code>.
* En cas de succès, <ttcode>realloc</ttcode> alloue un espace mémoire de taille ''nouvelle_taille'', copie le contenu pointé par le paramètre ''pointeur'' dans ce nouvel espace (en tronquant éventuellement si la nouvelle taille est inférieure à la précédente), puis libère l'espace pointé et retourne un pointeur vers la nouvelle zone mémoire.
* En cas d'échec, cette fonction ne libère pas l'espace mémoire actuel, et retourne une adresse nulle.
Notez bien que <ttcode>realloc</ttcode> ne peut que modifier des espaces mémoires qui ont été alloués par <ttcode>malloc</ttcode>, <ttcode>calloc</ttcode>, ou <ttcode>realloc</ttcode>. En effet, autoriser <ttcode>realloc</ttcode> à manipuler des espaces mémoires qui ne sont pas issus des fonctions de la bibliothèque standard pourrait causer des erreurs, ou des incohérences graves de l'état du processus. En particulier, les tableaux, automatiques comme statiques, ne peuvent être passés à <ttcode>realloc</ttcode>, comme illustré par le code suivant :
{{Erreur volontaire}}
</source>
Lorsque <ttcode>realloc</ttcode> reçoit la valeur de <ttcode>tab</ttcode>, qui est un pointeur sur le premier élément (i.e. <ttcode>&tab[0]</ttcode>), il ne peut la traiter, et le comportement est indéfini. Sur cet exemple, il est facile de voir l'erreur, mais dans l'exemple suivant, la situation est plus délicate :
<source lang="c">
</source>
La fonction <ttcode>double</ttcode> en elle-même ne comporte pas d'erreur, mais elle peut causer des plantages suivant la valeur de <ttcode>ptr</ttcode> qui lui est passée. Pour éviter des erreurs, il faudrait que la documentation de la fonction précise les contraintes sur la valeur de <ttcode>ptr</ttcode>... et que les programmeurs qui l'utilisent y fassent attention.
On peut aussi noter que, quand <ttcode>realloc</ttcode> réussit, le pointeur renvoyé peut très bien être égal au pointeur initial, ou lui être différent.
En particulier, il n'y a aucune garantie que, quand on diminue la taille de la zone mémoire, il le fasse « sur place ». C'est très probable, car c'est ce qui est le plus facile et rapide à faire du point de vue de l'implémentation, mais rien ne l'empêche par exemple de chercher un autre espace mémoire disponible qui aurait exactement la taille voulue, au lieu de garder la zone mémoire initiale.
On peut noter le test <ttcode>(n <= SIZE_MAX / 2)</ttcode>. Il permet d'éviter un ''débordement entier'' : si n était supérieur à cette valeur, le produit <ttcode>n * 2</ttcode> devrait avoir une valeur supérieure à <ttcode>SIZE_MAX</ttcode>, qui est la plus grande valeur représentable par le type <ttcode>size_t</ttcode>. Lorsque cette valeur est passée à <ttcode>realloc</ttcode>, la conversion en <ttcode>size_t</ttcode>, qui est un type entier non signé, se fera modulo <ttcode>SIZE_MAX + 1</ttcode>, et donc la fonction recevra une valeur différente de celle voulue. Si le test n'était pas fait, <ttcode>double</ttcode> pourrait ainsi retourner à l'appelant une zone mémoire de taille inférieure à celle demandée, ce qui causerait des bogues. Ce genre de bogue (non spécifique à <ttcode>realloc</ttcode>) est très difficile à détecter, car n'apparaît que lorsque l'on atteint des valeurs limites, ce qui est assez rare, et le problème peut n'être visible que bien longtemps après que l'erreur de calcul soit faite.
==== Gestion d'erreur ====
</source>
En effet, si <ttcode>realloc</ttcode> échoue, la valeur de <ttcode>ptr</ttcode> est alors nulle, et on aura perdu la référence vers l'espace de taille <ttcode>10 * sizeof(int)</ttcode> qu'on a déjà alloué. Ce type d'erreur s'appelle une ''fuite mémoire''. Il faut donc faire ainsi :
<source lang="c">
==== Exemple ====
<ttcode>realloc</ttcode> peut être utilisé quand on souhaite boucler sur une entrée dont la longueur peut être indéfinie, et qu'on veut gérer la mémoire assez finement. Dans l'exemple suivant, on suppose définie une fonction <code>lire_entree</code> qui :
* lit sur une entrée quelconque (par exemple <ttcode>stdin</ttcode>) un entier, et renvoie 1 si la lecture s'est bien passée ;
* renvoie 0 si aucune valeur n'est présente sur l'entrée, ou en cas d'erreur.
Cette fonction est utilisée pour construire un tableau d'entiers issus de cette entrée. Comme on ne sait à l'avance combien d'éléments on va recevoir, on augmente la taille d'un tableau au fur et à mesure avec <ttcode>realloc</ttcode>.
<source lang="c">
</source>
Ici, on utilise <ttcode>max</ttcode> pour se souvenir du nombre d'éléments que contient la zone de mémoire allouée, et <ttcode>i</ttcode> pour le nombre d'éléments effectivement utilisés. Quand on a pu lire un entier depuis l'entrée, et que <ttcode>i</ttcode> vaut <ttcode>max</ttcode>, on sait qu'il n'y a plus de place disponible et qu'il faut augmenter la taille de la zone de mémoire. Ici, on incrémente la taille <ttcode>max</ttcode> de 10 à chaque fois, mais il est aussi possible de la multiplier par 2, ou d'utiliser toute autre formule. On utilise par ailleurs le fait que, quand le pointeur envoyé à <ttcode>realloc</ttcode> est nul, la fonction se comporte comme <ttcode>malloc</ttcode>.
Le choix de la formule de calcul de <code>max</code> à utiliser chaque fois que le tableau est rempli résulte d'un compromis :
* augmenter <ttcode>max</ttcode> peu à peu permet de ne pas gaspiller trop de mémoire, mais on appellera <ttcode>realloc</ttcode> très souvent.
* augmenter très vite <ttcode>max</ttcode> génère relativement peu d'appels à <ttcode>realloc</ttcode>, mais une grande partie de la zone mémoire peut être perdue.
Une allocation mémoire est une opération qui peut être coûteuse en terme de temps, et un grand nombre d'allocations mémoire peut fractionner l'espace mémoire disponible, ce qui alourdit la tâche de l'allocateur de mémoire, et au final peut causer des pertes de performance de l'application. Aucune formule n'est universelle, chaque situation doit être étudiée en fonction de différents paramètres (système d'exploitation, capacité mémoire, vitesse du matériel, taille habituelle/maximale de l'entrée...).
Toutefois, l'essentiel est bien souvent d'avoir un algorithme qui marche, l'optimisation étant une question secondaire. Dans une telle situation, utilisez d'abord une méthode simple (incrémentation ou multiplication par une constante), et n'en changez que si le comportement du programme devient gênant.
== Problèmes et erreurs classiques ==
=== Défaut d'initialisation d'un pointeur ===
Pour éviter des erreurs, un pointeur devrait '''toujours''' être initialisé lors de sa déclaration ; soit à NULL, soit avec l'adresse d'un objet, soit avec la valeur de retour d'une fonction « sûre » comme <ttcode>malloc</ttcode>. Méditons sur l'exemple suivant :
{{Erreur volontaire}}
| 