Security-X

Forum Security-X => Programmation => Cours => Discussion démarrée par: XmichouX le octobre 30, 2011, 13:33:46

Titre: Allocation dynamique
Posté par: XmichouX le octobre 30, 2011, 13:33:46
Allocation dynamique

Dans la section ci-dessus, nous avons vu des tableaux alloués de manière statique. L'espace mémoire était réservé pour le tableau et pas alloué à la demande. Dans l'ancienne norme du C (C89), on ne pouvait pas créer un tableau en mettant entre crochets une variable. Il fallait mettre des données brutes.
Les tableaux statiques sont donc alloués à la compilation, contrairement aux allocations dynamiques, faites à l'exécution (à la demande).

C'est entre autres pour cela qu'on a inventé l'allocation dynamique de mémoire, c'est-à-dire, à la demande du développeur.

Pour cela, le C met à la disposition du développeur la fonction bien connue malloc dont le prototype est le suivant :

Citer
void *malloc(size_t taille_en_octets);

Le type size_t est un type spécial qui correspond à unsigned int ou unsigned long selon l'architecture. Bref, size_t correspond à un nombre d'une certaine taille non signé (positif). On va allouer de la mémoire, pas en détruire.

La fonction retourne un pointeur sur un void. Malloc retourne donc l'adresse (contenu du pointeur renvoyé void*) où commence la mémoire allouée pour le programmeur. La fonction ne sachant pas sur quoi va pointer l'adresse, elle retourne un pointeur sur le type void, autrement dit, un pointeur générique.

On alloue de la mémoire dynamique comme ceci :

int *ptr = NULL;
ptr = (int*) malloc (5 * sizeof(*ptr))
free(ptr);

Ici, on alloue de la mémoire pour un tableau de 5 entiers. L'espace réservé en mémoire est bien un tableau (réservé sur le tas), mais ptr est bien un pointeur, dont la valeur est l'adresse de ce tableau dynamique. Enfin je dis un tableau juste parce que dans mon esprit, je crée un tableau. Concrètement, il y a juste une réservation de 5 cases mémoire de 4 octets sur le tas.
L'allocation dynamique peut aussi bien être utilisée dans le main que dans une fonction basique.
Avantage : Sauf si on spécifie explicitement (à l'aide de free()) vouloir libérer l'espace alloué, celui-ci ne sera pas libéré, car il n'est pas réservé dans la zone de pile ! (Si vous avez bien suivi l'explication dans le premier post, vous devriez comprendre)
On peut donc tout à fait créer un tableau dynamique dans une fonction lambda et retourner un pointeur sur celui-ci à la fonction principale.
On libère l'espace alloué en écrivant : free(pointeur sur l'espace alloué);
Lorsqu'on fait de l'allocation dynamique, il faut toujours vérifier que le pointeur a bien reçu et n'est pas NULL (malloc() n'a pas pu retourner d'adresse). C'est d'ailleurs pour cette raison qu'il faut initialiser son pointeur à NULL.
On peut également allouer de la mémoire dans la zone de pile pour un tableau statique dans une fonction et retourner un pointeur dessus, sauf que ceci n'est pas viable/durable. Comme pour avant, le tableau statique créé dans la fonction sera local et disparaît à la fin de la fonction. Il ne disparaît pas vraiment, mais le moindre appel de fonction est susceptible de l'écraser. On ne peut donc pas l'utiliser.

Exemple :

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

#define N 5

int* tableau_statique () {
    int tab[N] = {1, 2, 3, 4, 5};
    int *ptr = tab;
    return ptr;
}

int* tableau_dynamique () {
    int *ptr = NULL;
    ptr = (int*) malloc(N*sizeof(*ptr));
    if (ptr == NULL)
return NULL;
    *ptr = 1;
    *(ptr+1) = 2;

    int *p = ptr+1;
    *++p = 3;
    *++p = 4;
    *++p = 5;
    return ptr;
}

int main () {
    int *PTR = NULL;
    int i = 0;

    PTR = tableau_statique();

    for (i = 0; i < N; i++)
        printf ("Tableau[%i] = %i\n", i, PTR[i]);

    PTR = tableau_dynamique();
    if (PTR == NULL)
return -1;

    for (i = 0; i < N; i++)
        printf ("Tableau[%i] = %i\n", i, PTR[i]);

    free(PTR);
return 0;
}

Note : Le cast du retour de malloc, n'est pas obligatoire pour la raison suivante : le cast d'un type void vers un autre type et vice versa, se fait de manière implicite. Vous pouvez tout de même le faire si vous jugez ça plus propre ou/et plus clair.

Vous remarquerez que dans le fonction tableau_dynamique, j'utilise la notation *++ptr = nombre.
Cette instruction incrémente de un le contenu du pointeur (l'adresse) puis place le nombre à l'adresse contenue incrémentée.
Si vous faites *ptr++ = nombre, le nombre sera d'abord mis à l'adresse, puis le pointeur sera incrémenté.

Note : Si on a par exemple : int val = 5; int * ptr = &val; et que l'on veut incrémenter la valeur via le pointeur, il faut ou bien écrire ++*ptr ou bien (*ptr)++.
Pourquoi ai-je mis des parenthèses ici ? Parce que l'opérateur ++ (incrémentation) est prioritaire sur l'étoile, ce qui signifie que sans les parenthèses, c'est la valeur de ptr (adresse de val) qui est incrémentée et non le contenu pointé (valeur de val).

Ce code peut par exemple retourner :

Citer
Tableau[0] = 1
Tableau[1] = 15
Tableau[2] = 1
Tableau[3] = 2293500
Tableau[4] = 5
Tableau[0] = 1
Tableau[1] = 2
Tableau[2] = 3
Tableau[3] = 4
Tableau[4] = 5

La premier parcours est incorrect (tableau statique alloué sur la pile dans une fonction), alors que le deuxième alloué dynamiquement sur le tas est correct et fiable.
On retrouve des traces du tableau statique tout de même, le 0 et le 5.
Si vous appelez une autre fonction dans votre programme (qui initialise un ou plusieurs tableaux par exemple), vous verrez que lorsque vous afficherez votre tableau statique, tout aura été écrasé, et vous retrouverez certainement des données initialisées dans la fonction appelée entre temps. À vous d'essayer.

Quand on a aucune expérience en programmation en général, on se demande à quoi peut bien servir malloc. Je vais prendre au hasard un exemple concret que j'avais pour un projet très facile :)

Je devais faire un pendu. J'avais donc établi une liste de mots codée en dur dans le programme, du style :
char dico[][20] = {"BOUCLIER", "AMOUR", "PASSION", ....};Ensuite, il fallait sélectionner un mot aléatoire parmi ceux-ci, et allouer le mot à trouver dynamiquement en fonction de la taille (longueur) du mot sélectionné, ce qui donnait grossomodo :
char *mot_trouve = malloc (taille_mot_selectionne * sizeof(*mot_trouve));
Or le "taille_mot_selectionne" était différent à chaque fois que je lançais le pendu. Il fallait donc recourir à malloc().
Voilà un exemple parmi tant d'autres. C'est en programmant que vous découvrirez son utilité.

De manière générale, quand on ne connaît pas à l'avance la taille d'un tableau (par exemple, celle-ci variant selon ce que souhaite l'utilisateur), on a recours à l'allocation dynamique..

Lorsque vous utilisez malloc(), un pointeur vous est retourné sur une zone mémoire non initialisée (il peut donc y avoir tout et n'importe quoi). Si vous voulez que cette zone soit initialisée à 0 (= NULL), préférez alors l'utilisation de calloc(), dont voici le prototype :

Citer
void *calloc(size_t nombre_elements, size_t taille_element);

On a donc l'équivalence suivante :

int * ptr = calloc (5, sizeof(*ptr));
est équivalent à :

int *ptr = malloc (5 * sizeof(*ptr));
int i ;
for (i = 0; i < 5; i++)
*(ptr+i) = NULL;

On peut également allouer dynamiquement un tableau à plusieurs dimensions ! L'allocation dynamique permet d'ailleurs dans ce cas, d'avoir un tableau irrégulier : chaque indice de la première dimension n'a pas forcément le même nombre d'éléments. Cependant, nous n'allons pas le faire.

Voici comment on peut s'y prendre :

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

#define L 5
#define C 4

int main () {
int **tab2D = NULL;
        tab2D = calloc (L * sizeof(*tab2D)); //  = sizeof(int*)
if (tab2D == NULL)
return -1;
int i = 0;
        /* Si on avait utilisé malloc() au début, il aurait fallu initialiser chaque *(tab2D+i) à NULL pour ensuite tester la valeur NULL du pointeur */
for (i = 0; i < L; i++) {
*(tab2D+i) = malloc (C * sizeof(**tab2D)); // = sizeof(int)
if (tab2D+i == NULL)
return -1;
}

for (i = 0; i < L; i++) {
free (*(tab2D+i));
}
free (tab2D);

return 0;
}
On alloue la "première dimension" en renseignant le nombre d'index que l'on désire. C'est donc un tableau de pointeurs sur entiers (int *).
Ensuite, pour chaque index, on alloue la deuxième dimension, c'est-à-dire, un tableau d'entiers (int).
Notre pointeur de base tab2D est donc un pointeur sur un tableau de pointeurs, dont chacun pointe sur un tableau d'entiers.
tab2D est donc de type pointeur sur pointeur d'entiers (int **).

Ensuite, il suffit de libérer chaque tableau alloué, et le tour est joué !

Notez cette fois que vos données ne seront pas forcément alignées en mémoire, comme elles le sont avec un tableau statique !
Tout dépend ce que malloc() retourne pour chaque deuxième dimension allouée.

On voit bien ci-dessous qu'il y a bien un tableau de pointeurs à part, et que les données ne sont pas tout à fait consécutives en mémoire (dépendant de ce que malloc() nous donne comme adresse). Par conséquent, on ne peut pas utiliser les méthodes utilisées pour les tableaux statiques.

Citer
Adresse tab[0] = 003E3C18
Adresse tab[1] = 003E3C1C
Adresse tab[2] = 003E3C20
Adresse tab[3] = 003E3C24
Adresse tab[4] = 003E3C28
Adresse tab[0][0] = 003E2430
Adresse tab[0][1] = 003E2434
Adresse tab[0][2] = 003E2438
Adresse tab[0][3] = 003E243C
Adresse tab[0][4] = 003E2440
Adresse tab[0][5] = 003E2444
Adresse tab[1][0] = 003E2450
Adresse tab[1][1] = 003E2454
Adresse tab[1][2] = 003E2458
Adresse tab[1][3] = 003E245C
Adresse tab[1][4] = 003E2460
Adresse tab[1][5] = 003E2464
Adresse tab[2][0] = 003E2470
Adresse tab[2][1] = 003E2474
Adresse tab[2][2] = 003E2478
Adresse tab[2][3] = 003E247C
Adresse tab[2][4] = 003E2480
Adresse tab[2][5] = 003E2484
Adresse tab[3][0] = 003E2490
Adresse tab[3][1] = 003E2494
Adresse tab[3][2] = 003E2498
Adresse tab[3][3] = 003E249C
Adresse tab[3][4] = 003E24A0
Adresse tab[3][5] = 003E24A4
Adresse tab[4][0] = 003E24B0
Adresse tab[4][1] = 003E24B4
Adresse tab[4][2] = 003E24B8
Adresse tab[4][3] = 003E24BC
Adresse tab[4][4] = 003E24C0
Adresse tab[4][5] = 003E24C4

Note : On remarque que chaque tableau d'entiers commence à une adresse multiple de 16 octets (4 bits de poids faible nuls). Ceci n'est pas forcément vrai sur toutes les machines ^^.

Schématiquement, cela donne ceci :

(https://forum.security-x.fr/proxy.php?request=http%3A%2F%2Fsecurity-x.fr%2Fimg%2Fpublic%2Ftableau_de_pointeurs.png&hash=1113a1bd56aa3eb9ae1ca1f5a1c5ecad0a7da641)

Pour passer un tableau unidimensionnel à une fonction, on applique la même technique que pour un tableau statique.
En revanche, pour une matrice dynamique, on peut cette fois adapter la solution qui posait problème pour un tableau statique.

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

#define L 5
#define C 6

void zero (int **tab, int lignes, int col) {
int i, j;
for (i=0; i<lignes; i++) {
for (j=0; j<col; j++) {
tab[i][j] = 0;
}
}
}

void afficherMatrice (int **tab, int lignes, int col) {
int i, j;
for (i=0; i<lignes; i++) {
for (j=0; j<col; j++) {
printf ("tab[%i][%i] = %i\n", i , j, *(*(tab+i)+j)); // égal à tab[i][j]
}
}
}

int main () {
int **tab2D = malloc(L * sizeof(**tab2D));
if (tab2D == NULL)
return -1;

int i, j;
for (i = 0; i < L; i++) {
*(tab2D+i) = malloc(C * sizeof(*tab2D));
if (tab2D+i == NULL)
return -1;
};
for (i = 0; i < L; i++) {
for (j = 0; j < C; j++) {
tab2D[i][j] = i+j;
}
}
afficherMatrice(tab2D, L, C);
zero(tab2D, L, C);
afficherMatrice(tab2D, L, C);
for (i = 0; i < L; i++) {
free (*(tab2D+i));
}
free (tab2D);
}

Note :
*(tab+i) = adresse du premier élément du tableau pointé par tab + i (contenu du pointeur situé à tab+i).
(*(tab+i)+j) = adresse du premier élément du tableau pointé par tab +i, + j. Ajouter une étoile devant permet d'accéder à la valeur.

Cette fois, on peut utiliser cette technique, car il n'y a pas un seul tableau en continu dans la mémoire comme pour une matrice statique, mais il y a un tableau de pointeurs (première dimension), dont chaque élément pointe sur un tableau d'entiers alloué, qui représente la deuxième dimension : en fait, l'échantillons de valeurs pour tel index de la première dimension (voir schéma plus haut).
Les "dimensions" sont une abstraction pour le développeur, pour faciliter son travail.

Pour résumer les différences entre un tableau statique et un tableau dynamique :

- Pour un tableau statique à n dimensions, et quelque soit n, il n'y qu'un bloc contiguë de données en mémoire. Il n'y pas de variable qui pointe sur ce contenu. Les variables de types tab ou tab[n] pour un tableau à deux dimensions sont uniquement des "étiquettes" gérées par le compilateur.
Il n'y a que les données du tableau en mémoire.
- Pour un tableau dynamique à une dimension, on a un pointeur qui pointe sur le tableau en mémoire (bloc contiguë de données). Pour un tableau à deux dimensions, on crée un tableau de pointeurs, donc chacun pointe sur un tableau d'entiers (enfin de type **tab), et ainsi de suite. Par exemple, pour un tableau à trois dimensions, on aura cette fois un tableau de pointeurs, dont chacun pointe sur un tableau de pointeurs, dont chacun pointe sur un tableau d'entiers :) En cascade quoi.
Il y a un pointeur (voir un tableau ou des tableaux en cascade selon le nombre de dimensions) qui pointe(nt) sur les données en mémoire non contiguës (quand la dimension > 1). Seules les données de chaque tableau d'entiers sont contiguës.
Titre: Re : Allocation dynamique
Posté par: igor51 le juillet 26, 2012, 20:14:15
Up !