LdB Seance 2

De Ensiwiki
Aller à : navigation, rechercher
AttentionCette page est maintenue uniquement par les enseignants. Afin de ne pas perturber le déroulement des cours, elle n'a pas vocation à être modifiée par les élèves. Mais si vous avez des modifications à proposer, merci d'en discuter ou d'envoyer un e-mail aux auteurs de la page (cf. historique)

Laptop.png  Première Année  CDROM.png  Informatique 

Introduction

Le but de cette séance est d'apprendre à manipuler des pointeurs et à gérer la mémoire en C.

On peut récupérer toutes les sources utilisées dans cette séances dans cette archive Zip.

On rappelle qu'on compile les programmes C avec la commande suivante :

gcc -o BIN -Wall -Wextra -m32 -g -std=c99 SOURCES

Manipulation de pointeurs (pointeurs.c)

Déclarations de pointeurs et opérateurs associés

On commence par détailler la fonction main :

int i = 5;
int *ptr = &i;
*ptr = 10;
printf("Adresse de i : 0x%08X, valeur de i : %i\n", (unsigned)ptr, i);

Points à noter :

  • on peut déclarer des variables de type pointeur : ici, on manipule un pointeur vers un entier, dont le type s'écrit int * ;
  • l'opérateur & permet de récupérer l'adresse d'une variable ;
  • l'opérateur * permet d'accéder à la valeur pointée par une variable de type pointeur (c'est l'équivalent du .all en Ada) ;
  • le format %08X du printf permet d'afficher un entier en hexadécimal, sur 8 chiffre au minimum, en complétant les chiffres manquants par des 0 si besoin ;
  • le transtypage explicite (cast en anglais) de ptr vers un naturel évite un avertissement à la compilation.

Passage de paramètres par copie

On observe ensuite le code de la fonction echange_faux :

void echange_faux(int a, int b)
{
    int t = a; a = b; b = t;
}

On comprend que le but de cette fonction est d'échanger le contenu des paramètres a et b. Mais son implantation est fausse, car les paramètres sont toujours passés par copie en C : cette fonction n'a en fait aucun effet.

On doit plutôt écrire :

void echange(int *a, int *b)
{
    int t = *a; *a = *b; *b = t;
}

Cette fonction s'utilise en passant en paramètre les adresses des variables dont on veut échanger la valeur :

int j = 20;
echange(&i, &j);
printf("i = %i, j = %i\n", i, j);

Parcours de tableaux

Une chaîne de caractères est simplement un tableau de caractères, et un tableau est représenté en C par l'adresse mémoire de son premier élément :

char chaine[] = "azerty";
for (char *p = chaine; *p != '\0'; p++) {
    printf("%c", *p);
}
printf("\n");

Points à noter :

  • on peut déclarer un tableau et l'initialiser en même temps : dans ce cas, on ne précise pas la taille du tableau entre les crochets ;
  • le pointeur p est initialisé pour pointer sur le premier caractère de la chaîne (char *p = chaine) ;
  • à la place de *p != '\0', on pourrait écrire simplement *p car '\0' vaut 0, mais ça serait moins lisible ;
  • on peut utiliser des opérations arithmétiques sur les pointeurs (on parle d'arithmétique des pointeurs).

De la même façon, on peut parcourir un tableau d'entiers à l'aide d'un pointeur :

int tab[] = {1, 2, 3, 4, 5, -1};
for (int *p = tab; *p != -1; p++) {
    printf("Adresse : 0x%08X, valeur : %i\n", (unsigned)p, *p);
}

Points à noter :

  • on décide arbitrairement de terminer le tableau par -1 : en général, on manipulera plutôt explicitement sa taille ;
  • l'opération p++ a pour effet d'augmenter l'adresse contenue dans p de 4 octets, c'est à dire de la taille d'un entier.

Pointeurs de structures

Il existe une syntaxe particulière pour manipuler des pointeurs sur les structures :

struct ma_struct_t {
    int i;
    char c;
};

...

struct ma_struct_t s = {-4, 'a'};
struct ma_struct_t *p = &s;
(*p).i = 4; p->c = 'A';
printf("%i %c\n", p->i, s.c);

Points à noter :

  • on peut initialiser les champs d'un élément de type structure lors de la déclaration (attention, on doit respecter l'ordre des champs, on ne peut pas les nommer comme en Ada) ;
  • struct ma_struct_t *p est un pointeur sur un élément de type structure ;
  • les parenthèses sont obligatoires dans l'expression (*p).i = 4, ce qui rend le code lourd à écrire : c'est l'intérêt de la syntaxe allégée mais équivalente utilisée dans p->c = 'A'.

Allocation mémoire dynamique (alloc.c)

Fonctions d'allocation et de libération de la mémoire

On peut allouer et libérer dynamiquement de la mémoire dans une zone appelée le tas (heap en anglais) en utilisant les fonctions suivantes (définies dans stdlib.h) :

void *malloc(size_t size);
void *calloc(size_t count, size_t size);
void free(void *ptr);

Points à noter :

  • size_t est un type interne à la bibliothèque C équivalent à unsigned ;
  • malloc prend en paramètre le nombre d'octets que l'on souhaite allouer et renvoie un pointeur sur le début de la zone ;
  • le type void * représente les pointeurs de type « générique » : on ne les manipule que rarement directement, mais on peut les transtyper vers n'importe-quel type de pointeurs (e.g. char *, int *, etc.) ;
  • calloc est similaire à malloc mais est souvent utilisée pour allouer des tableaux : elle prend en paramètre le nombre d'éléments à allouer (count) et la taille en octets d'un élément (size), et alloue donc count * size octets ;
  • en plus d'allouer, calloc initialise aussi la zone mémoire avec des 0, ce que ne garantit pas malloc ;
  • free libère une zone mémoire précédemment allouée : on lui passe un pointeur vers le début de la zone.

Erreurs fréquentes

Une des plus fréquente source d'erreurs en C est la mauvaise manipulation des pointeurs :

char *chaine = malloc(7);
strcpy(chaine, "azerty");
printf("%s\n", chaine);
free(chaine);
// printf("%s\n", chaine);
char *c = malloc(7);
// printf("%s\n", c);

Points à noter :

  • le premier printf est commenté car il est faux d'accéder à une zone mémoire après qu'elle ait été libérée : l'effet est imprévisible ;
  • le deuxième printf est aussi faux car on ne doit pas lire dans une zone mémoire avant d'y avoir écrit des valeurs (malloc ne garantit pas que la zone contient des 0, à la différence de calloc).

Pour éviter ce genre d'erreurs, on recommande fortement l'utilisation du logiciel Valgrind (installé sur telesun), que l'on lance sur le binaire après compilation :

valgrind --leak-check=full ./alloc

Si on exécute la commande ci-dessus après avoir compilé le programme en décommentant les 2 printfs, Valgrind affiche une suite d'erreurs du type Invalid read avec des numéros de lignes qui permettent de localiser la source du problème.

Recopie de zones mémoire

La fonction memcpy permet de recopier très rapidement le contenu d'une zone mémoire dans une autre :

const int taille = 5;
int *tab = calloc(taille, sizeof(int));
int *copie =  malloc(taille * sizeof(int));
memcpy(copie, tab, taille * sizeof(int));
for (int i = 0; i < taille; i++) {
    printf("%i ", copie[i]);
}
printf("\n");

Points à noter :

  • const devant la déclaration d'une variable interdit qu'on la modifie plus tard dans le programme ;
  • l'opérateur sizeof renvoie le nombre d'octets occupé par une variable du type qu'on lui passe en paramètre ;
  • cet opérateur est très important pour écrire du code portable : on travaille ici en 32 bits, donc les entiers occupent 4 octets chacun, mais sur une machine 64 bits, ils prendraient 8 octets ;
  • memcpy est définie dans string.h comme void *memcpy(void *restrict s1, const void *restrict s2, size_t n)
  • on peut ignorer le mot clé restrict qui ne nous intéresse pas dans ce cours ;
  • cette fonction recopie les n premiers octets de la zone pointée par s2 dans la zone pointée par s1 ;
  • elle renvoie l'adresse de s1 sous la forme d'un pointeur générique ;
  • cette fonction ne fonctionne que si les zones pointées par s1 et s2 ne se recouvrent pas (sinon, il faut utiliser memmove) ;
  • il n'y a aucune vérification effectuée, et notamment pas que s1 est suffisamment grande !

Utilisation des assertions

Lorsqu'on alloue dynamiquement de la mémoire, il faut toujours vérifier que le pointeur récupéré est valide, c'est à dire qu'il est différent du pointeur NULL (constante définie dans stdio.h) :

while (1) {
    int *boom = malloc(1 << 30);
    assert(boom != NULL);
}

Points à noter :

  • while (1) est une boucle infinie (puisque 1 est toujours différent de 0) ;
  • l'opérateur << effectue un décalage à gauche du nombre de bit précisé : ici, on calcule donc 2^{30}, c'est à dire 1 GiO ;
  • allouer 1 GiO en boucle va épuiser très rapidement la mémoire disponible : lorsque c'est le cas, malloc renverra NULL pour signifier que l'allocation n'a pas pu être réalisée ;
  • assert est une macro (dans le cadre de ce cours, on considérera que c'est la même chose qu'une fonction) qui vérifie que l'expression booléenne passée en paramètre est vraie : dans le cas contraire, le programme est arrêté immédiatement avec un message d'erreur approprié ;
  • les assertions permettent d'implanter simplement un contrôle des erreurs primitif, de façon similaire (mais beaucoup moins sophistiqué) aux exceptions en Ada.

Implantation de listes chaînées (listes.c)

On va travailler dans cet exercice sur des listes simplement chaînées.

Type des cellules

On définit le type cellule à l'aide d'une structure comme en Ada :

struct cellule_t {
    int val;
    struct cellule_t *suiv;
};

Affichage d'une liste chaînée

On affiche la valeur de chaque élément de la liste, en partant du premier :

void afficher(struct cellule_t *l)
{
    for (; l != NULL; l = l->suiv) {
        printf("%i -> ", l->val);
    }
    printf("FIN\n");
}

Points à noter :

  • on ne définit pas de type liste particulier : on manipule directement un pointeur vers la première cellule ;
  • dans la fonction afficher, la liste n'est pas modifiée.

Insertion en tête de liste

Pour insérer une valeur en tête de la liste, on alloue une nouvelle cellule qu'on relie à la liste existante :

void inserer_tete(struct cellule_t **l, int v)
{
    struct cellule_t *cell = malloc(sizeof(struct cellule_t));
    assert(cell != NULL);
    cell->val = v; cell->suiv = *l;
    *l = cell;
}

Points à noter :

  • comme on va modifier la liste dans la fonction inserer_tete, on doit passer un pointeur vers la liste ;
  • un pointeur sur la liste est en fait un pointeur vers un pointeur vers la première cellule ;
  • dans le code, *l est la valeur du pointeur vers la première cellule , c'est à dire l'adresse de la liste.

Insertion en queue de liste

Pour insérer une valeur en queue de liste, on doit parcourir celle-ci pour trouver la dernière cellule :

void inserer_queue(struct cellule_t **l, int v)
{
    struct cellule_t sent = {-1, *l};
    struct cellule_t *queue;
    for (queue = &sent; queue->suiv != NULL; queue = queue->suiv);
    queue->suiv = malloc(sizeof(struct cellule_t));
    assert(queue->suiv != NULL);
    queue->suiv->val = v; queue->suiv->suiv = NULL;
    *l = sent.suiv;
}

Points à noter :

  • le cas de la liste vide peut être traité simplement en utilisant une sentinelle en tête de liste ;
  • en C, on n'a pas besoin d'allouer dynamiquement la sentinelle comme en Ada, on peut la déclarer directement comme une variable locale de la fonction : struct cellule_t sent ;
  • on récupère l'adresse de cette sentinelle grâce à l'opérateur & ;
  • à la fin de la fonction, les variables locales sont automatiquement libérée, on n'a donc pas besoin de désallouer la sentinelle.