Pointeurs (suite)

Rappel de l'organisation de la mémoire

  • Qu'est ce qu'il y a dans la zone des données ?

Les variables globales et statiques.

  • Qu'est ce qu'il y a dans la pile ?

Les variables locales.

Allocation mémoire

On peut allouer des octets sur le tas avec la fonction malloc. C'est un peu comme si on achetait de la mémoire. On indique le nombre d'octets, par exemple 4 :

malloc(4);

malloc(4) renvoie :

  • soit un pointeur vers la zone allouée de 4 octets (i.e. l'adresse mémoire du début de la zone allouée)
  • soit NULL en cas d'échec
        int* p = malloc(4);

  • Que contient *p ?
Un entier.
  • Où est stocker *p avec le malloc ci-dessus ?

Dans le tas.
  • Que contient p ?
Une adresse mémoire.
  • Où est stocker p avec le malloc ci-dessus ?

Dans la pile. On peut imaginer :

int main()
{
    int* p = malloc(4);
    ...
}

p est une variable locale comme les autres, sauf qu'elle contient une adresse mémoire.

Amélioration de l'appel

En fait on écrit plutôt

int* p = malloc(sizeof(int));

Encore mieux :

int *p = malloc(sizeof(*p));
  • Pourquoi est-ce mieux ?

Car si on change le type de p par exemple :

struct point *p = malloc(sizeof(*p));

ça fonctionne toujours bien !

Accès à la valeur pointée

    int* p = malloc(sizeof(*p));
    print("%d\n", *p);
  • Que pensez-vous du programme suivant ?
    int* p = malloc(4);
    print("%d\n", *p);

Ca fonctionne, même si c'est maladroit de laisser un 4 volant comme ça.
  • Que pensez-vous du programme suivant ?
    int* p;
    print("%d\n", *p);

C'est le mal. L'adresse mémoire p vaut une valeur non connue. On va donc lire *p alors que la zone mémoire n'a pas été allouée. D'abord, tu achètes, ensuite tu utilises.
  • Que pensez-vous du programme suivant ?
    int* p = 1452;
    print("%d\n", *p);
C'est le mal. L'adresse mémoire 1452 n'est peut-être pas allouée. Donc pareil, on ne peut pas forcément y lire.
  • Que pensez-vous du programme suivant ?
    int* p = malloc(3);
    print("%d\n", *p);

Outre qu'il ne faut pas écrire 3 comme ça, ça ne va pas. On achète 3 octets mais il en faut 4. Là, le dernier octet n'a pas été acheté.
  • Que pensez-vous du programme suivant ?
    int* p = malloc(10);
    print("%d\n", *p);

Outre qu'il ne faut pas écrire 10 comme ça, ça fonctionne. On peut lire les 4 premiers octets et l'interpréter comme un entier *p.

Pour les struct

On écrit p->x au lieu de (*p).x.

Bonne utilisation de malloc

En fait, malloc peut échouer s'il n'y a plus assez de mémoire. Dans ce cas, malloc renvoie NULL. Il faut faire :

int *p;
if(p = malloc(sizeof(int)))
{
    printf("Out of memory!\n");
    exit(EXIT_FAILURE);
}

Vous pouvez par exemple écrire :

void* xmalloc(size_t nbytes) {
    void* p = malloc(nbytes);
    if(!p)
    {
        printf("Out of memory!\n");
        exit(EXIT_FAILURE);
    }
    return p;
}

Bon, c'est un peu brutal pour un utilisateurrice. Il peut le vivre comme ça :

void* xmalloc(size_t nbytes) {
    void* p = malloc(nbytes);
    if(!p)
    {
        printf("Pas de mémoire. Et j'ai codé rapidement mon programme. Donc tu perds toutes tes données, dommage pour toi. Relance le programme et refais tout ce que tu as fait ! Bonne chance !\n");
        exit(EXIT_FAILURE);
    }
    return p;
}

On peut imaginer des solutions plus agréables pour l'utilisateur. On débute une action... mais une erreur mémoire ne quitte pas le programme. On annule juste le début de l'action et on revient à l'état d'avant.

Désallocation avec free

    free(p);

Désalloue la mémoire allouée par malloc (ou ses copines realloc, calloc, aligned_alloc). C'est comme vendre de la mémoire car on n'en a plus besoin. Par exemple :

    int *p = malloc(sizeof(*p));
    *p = 5;
    free(p);
  • Que pensez-vous du programme suivant ?
    int *p = malloc(sizeof(*p));
    *p = 5;
    free(p);
    free(p);
Ne revends pas quelque chose que tu as déjà vendu.
  • Que pensez-vous du programme suivant ?
    int *p = 4321;
    free(p);

Ne vends pas quelque chose qui n'est pas à toi. (de toute façon, int *p = 4321 c'est le mal).
  • Que pensez-vous du programme suivant ?
void f() {
    int *p = xmalloc(sizeof(*p));
}

Un appel à f achète 4 octets, mais c'est une zone mémoire à laquelle on ne pourra plus accéder.
  • Que pensez-vous du programme suivant ?
int* f() {
    return xmalloc(sizeof(int));
}

Un appel à f achète 4 octets puis renvoie le pointeur vers ces 4 octets. Pas de soucis car on garde l'accès à ces 4 octets. Attention, à ne pas oublier de libérer la mémoire plus tard !

Applications : liste chaînée

  • Ecrire les opérations pour le type abstrait d'une pile
  • Implémenter la pile avec une liste chaînée

Applications directes

  • Implémenter une pile avec une liste chaînée
  • Implémenter le parcours de Graham pour calculer l'enveloppe convexe d'un ensemble de points du plan
    • Etudier l'algorithme
    • Utiliser l'implémentation de la pile
    • Utiliser pointeur sur une fonction pour trier les points