CM #8: Pointeurs

Ce chapitre aborde l’implémentation en C des paramètre modifiables. Le langage C donne accès aux adresses de stockage des variables (pointeurs) et fournit un type dédié qui permet de définir des variables de type adresse comme type de base. Avant d’aborder les pointeurs et afin de mieux comprendre leur nécessité, la notion de schéma d’exécution sera abordée qui est une simplification de ce qui se passe en mémoire lors du déroulement d’un programme (et plus particulièrement lors des appels de fonctions).

Schéma d’exécution

On présente tout d’abord un modèle simplifié (il sera complété au semestre 6 dans le cours de Programmation Avancée) puis on expose la problématique liée à la nature des paramètres.

Modèle mémoire

On rappelle que la mémoire d’un ordinateur est un vecteur de mots de n-bits (où n dépend de l’architecture matérielle, les plus courantes sont 32b et 64b). La plus petite entité que l’on peut stocker en mémoire est l’octet (voir le chapitre 3 sur les types de base) qui correspond à une case de la mémoire. Chaque case est accessible via une adresse (unique) habituellement notée en hexadécimale. Ainsi pour une architecture 32 bits, le début de la mémoire est:

`0x0000`
`0x0004`
`0x0008`
`0x000c`
`0x0010`
`...`

où la première case a pour adresse 0x0000, la seconde 0x0001… la cinquième 0x0004… Comme indiqué dans le chapitre 3 (variables), chaque variable déclarée occupe une certaine place mémoire définie par son type et l’identificateur permet d’accéder à la variable en mémoire sans avoir à mémoriser son adresse.

int x = 0;
char chaine[] = "ima2a";
char c = 'a';
bool b = false

Par exemple, les instructions ci-dessus impliquent qu’une partie de la mémoire va être réservée comme suit:

`...`
`0x1000`
`0x1004`
`0x1008`
`...`

les cases vertes permettent de stocker x (de type int donc codé sur 4 octets), les cases oranges stockent chaine (5 + 1 caractères donc 6 octets), la case bleue stocke c (1 char donc 1 octet) et la case rouge stocke b (1 bool est stocké sur un octet en C).

Remarque

L'adresse de départ 0x1000 est purement arbitraire, elle dépend d'un grand nombre de paramètres (architecture, état du système...) et ne peut pas être définie à l'avance.

En C, lorsqu’une fonction est appelée sont alloués (stockés en mémoire) ses paramètres effectifs (voir chapitre 5 sur les actions / fonctions), sa valeur de retour et ses variables locales. Ses instructions sont exécutées jusqu’au premier return rencontré. La valeur retournée est copiée dans la variable de la fonction appelante et la mémoire utilisée par la fonction est ensuite libérée (pour maximiser la place mémoire disponible). La fonction dummy décrite ci-dessous:

int dummy(int paramA, int paramB)
{
    double f;
    int s;
    // [... instructions ...]
    return s;
}

implique l’utilisation de la mémoire suivante:

`...`
`0x1000`
`0x1004`
`0x1008`
`0x100c`
`0x1010`
`0x1014`
`...`

qui correspond au fait que les cases:

vertes stockent paramA
oranges stockent paramB
bleues marine stockent la valeur de retour de dummy
bleues stockent f
rouges stockent s

Exemple simple

Soit l’algorithme ci-dessous

int ajoute_un(int a)
{
    return a+1;
}

int main()
{
    int x = 12;
    int y = ajoute_un(x);

    return 0;
}

Le schéma d’exécution de ce programme est le suivant (en supposant que main n’est pas de paramètres) en s’aidant du schéma ci-après:

le lancement du programme implique l’appel à la fonction main qui réserve 12 octets (4 octets pour le code de retour, 4 pour x et 4 pour y). On rappelle que 12 vaut C en hexadécimal et tient sur un octet (d’où le 000C qui correspond au x).
l’appel dans le main de la fonction ajoute_un implique qu’un espace mémoire est réservé pour les variables de la fonction ajoute_un. On choisit (arbitrairement) de stocker à partir de l’adresse 0x2000. Il y a 8 octets réservés: les 4 premiers pour a qui vaut 12 (000C en hexadécimal sur 4 octets) et les 4 suivants pour le code de retour de la fonction.
Lorsque le return est rencontré le code de retour est copié dans la zone mémoire prévue à cet effet (adresse 0x2004). La valeur est 13 (000D en hexadécimal).
La valeur du code retour est copiée dans la variable de la fonction appelante ici y (adresse 0x1008) et la zone mémoire utilisée par ajoute_un est libérée.
Le return du main est rencontré et 0 est copié dans la zone mémoire prévue pour contenir le code de retour…

Ce fonctionnement du passage de paramètres pour les fonctions (où sont passées les valeurs effectives des paramètres) est appelé passage par valeurs qui est le mode de passages des paramètres du langage C.

Passage par valeur / passage par adresse

Le passage par valeurs pose problème dès lors que l’on a plusieurs variables que l’on veut retourner ou une (ou plusieurs variables) que l’on veut modifier. Si l’on reformule l’exemple précédent avec des procédures, on obtient le programme suivant:

void incr(int a)
{
    a = a+1;
}

int main()
{
    int y = 12;
    incr(y);

    return 0;
}

Pour que le programme en C fonctionne comme attendu, il faudrait que les paramètres effectifs passés à la fonction appelée ne soient pas les valeurs mais leurs adresses. Ce mécanisme existe dans certains langages (par exemple Pascal) mais pas en C (cf passage par valeurs). Ceci dit, le langage C propose une solution à ce problème en ayant un type de base adresse que l’on peut passer aux fonctions. Ces adresses permettent d’accéder aux données que l’on souhaite modifier.

Les adresses et le `C`

Le langage C permet la manipulation d’adresses via deux opérateurs et des opérations que l’on peut effectuer sur des adresses.

Opérateur d’adresse

L’opérateur d’adresse & permet d’obtenir l’adresse d’un objet en mémoire. Bien entendu, cet opérateur ne fonctionne que sur des l-values. Voici quelques exemples:

int i       = 5;
float f     = 5.0f;
char c[10]  = "toto";

printf("%p\n", &i);         // affiche l'adresse de i
printf("%p\n", &f);         // affiche l'adresse de f
printf("%p\n", &(c[3]));    // affiche l'adresse de la 4ième case de c
printf("%p\n", &(i+1));     // ERREUR ! (i+1) n'est pas une l-value

Type pointeur

Pour manipuler les adresses, le langage C fournit un type dédié appelé pointeur qui permet de stocker des adresses. Les pointeurs intègrent également le type des adresses qu’ils stockent afin de différencier les adresses de variables entières, réelles… Ainsi on déclare des pointeurs de la manière suivante:

int *p_i;           // déclaration d'un pointeur d'entier
double r;
double *p_r = &r;   // déclaration et init d'un pointeur de double

Si on représente l’utilisation mémoire à la suite de ces trois instructions, on aura:

où les cases vertes stockent p_i, les cases bleues r et les cases oranges p_r. Il est important de remarquer que la place occupée en mémoire par un pointeur est indépendante du type pointé i.e. un pointeur sur un char prend la même place qu’un pointeur sur un double puisqu’ils stockent tous les deux une adresse (la place occupée ne dépend que de l’architecture matérielle).

Le type de pointeur est important puisqu’il permet d’imposer que les adresses qu’ils stockent sont bien du type du pointeur. Par exemple:

int main ()
{
    float f;
    int * p_i;
    p_i = &f;

    return 0;
}

que l’on compile:

jdequidt@weppes:~$ clang -Wall -o 012_pointeur_type.c
012_pointeur_type.c:5:6: warning: incompatible pointer types
assigning to 'int *' from 'float *'
      [-Wincompatible-pointer-types]
        p_i = &f;
            ^ ~~
1 warning generated.
jdequidt@weppes:~$

Il est possible de contourner ce mécanisme mais il implique de bien maîtriser la représentation de la mémoire car il est source d’un grand nombre d’erreurs de segmentations. Ce mécanisme sera vu ultérieurement.

Opérateur de déréférencement

L’opérateur de déréférencement * permet d’accéder au contenu stocké à une adresse mémoire valide.

int x = 10;
int * p_x = &x; // décl. et init. de pointeur d'entier
printf("%d\n", *p_x); // --> Affiche 10
*p_x = 4; // x vaut désormais 4

Opérations sur les pointeurs

Un certain nombre d’opérations sont possibles avec les pointeurs. Notamment le test d’égalité ou de différence, ainsi que les opérations arithmétiques et logiques (attention à leur utilisation). Voici quelques exemples d’utilisation:

#include <stdio.h>

int main ()
{
    char  c[] = "hello world !";
    char *p1  = &(c[0]);
    char *p2  = &(c[1]);

    printf ("%p %p\n", p1, p2);

    if (p1 == p2) printf ("Les pointeurs sont égaux\n");

    if (p1 != p2) printf ("Les pointeurs sont différents\n");

    printf ("%c %c\n", *p1, *p2);

    p1 = p1 + 1;

    printf ("%p %p\n", p1, p2);

    if (p1 == p2) printf ("Les pointeurs sont égaux\n");

    printf ("%c %c\n", *p1, *p2);

    return 0;
}

Les opérations de comparaison sont évidentes, celle qui nécessite un peu plus d’explication est la ligne p1 = p1 + 1. p1 pointe initialement sur la première case du tableau de caractère, on l’incrémente ensuite pour qu’il pointe sur l’élément qui suit (c’est à dire la deuxième case du tableau). On vérifie en compilant et en exécutant le programme.

jdequidt@weppes:~$ clang -Wall -o 013_pointeurs_operations.c
jdequidt@weppes:~$ ./a.out
0xd596 0xd597
Les pointeurs sont différents
h e
0xd597 0xd597
Les pointeurs sont égaux
e e
jdequidt@weppes:~$

Arithmétique des pointeurs

Incrémenter des pointeurs est possible avec des tableaux puisque l'on est sûr que les cases sont toutes adjacentes en mémoire. Ça n'est absolument pas garanti avec d'autres variables. Par exemple, dans l'instruction double f,g; rien ne garanti que g soit adjacent à f en mémoire et par conséquent l'instruction suivante: `double * pf = &f; pf = pf+1` ne garantit pas que pf va pointer sur g. Il en va de même pour les autres opérations sur les pointeurs, elles ne s'utilisent qu'en étant très vigilant.

Incrémenter des pointeurs

Modifier le programme précédent pour travailler avec des tableaux d'entiers. De combien est incrémenté p1 après l'instruction p1+1. Est ce que cela vous semble cohérent au vu des types manipulés ?

Utilisation des pointeurs

Exemples classiques

A l’aide des pointeurs, il est possible d’écrire en C le code de l’algorithme de la section précédente puisque l’on va pouvoir passer les adresses des variables qui nous intéressent:

void incr(int * p_b)
{
    *p_b = *p_b + 1;
}

int main()
{
    int y = 12;
    incr(&y);

    return 0;
}

Si l’on détaille le schéma d’exécution de ce programme, on obtient les étapes suivantes:

le lancement du programme implique l’appel à la fonction main qui réserve 8 octets (4 pour le code de retour, 4 pour y).
l’appel dans le main de l’action incr entraîne la réservation d’une zone mémoire de 4 octets (uniquement 4 octets pour p_b vu qu’il s’agit d’une action, il n’y a pas de code de retour). En appelant p_b les paramètres effectifs (i.e. adresse de y) sont stockés dans les paramètres formels.
L’instruction *p_b = *p_b + 1; implique la modification de la donnée stockée à l’adresse p_b (ici fixé à 0x1004).
L’action est terminée et son contexte est détruit. Mais x a bien été modifié via l’étape précédente.
Le return du main est rencontré et 0 est copié dans la zone mémoire prévue pour contenir le code de retour…

Les pointeurs sont également utilisés pour des opérations de permutation de valeurs. Par exemple:

void permuter (int *a, int *b)
{
    int temp = *a;
    *a       = *b;
    *b       = temp;
}

int main ()
{
    int a = 1, b = 3;
    permuter (&a, &b);
    printf ("%d %d\n", a, b);

    return 0;
}

Dès qu’un sous-programme implique plusieurs résultats, on utilise les pointeurs, comme pour la division euclidienne par exemple (calcul du quotient et du reste)

void div_entier(int a, int b, int *p_q, int *p_r)
{
    *p_q = a / b;
    *p_r = a % b;
}

int main()
{
    int x = 127, y = 9, q, r;
    div_entier(x, y, &q, &r);

    return 0;
}

Arithmétique des pointeurs

La fonction appelée div_entier utiliser des pointeurs. La fonction appelante doit fournir des pointeurs valides (ici adresse des variables q et r)!

Un autre exemple très courant est scanf. En effet lorsque l’on utilise scanf on passe l’adresse de la variable qui va recevoir ce qui est tapé au clavier d’où ce qui avait été écrit au chapitre 4.

Validité des pointeurs

Les erreurs de manipulation des variables pointeurs ont des conséquences plus graves que sur des variables de type de base: une entier non-initialisé qui est utilisé dans un calcul va engendrer un résultat faux tandis qu’un pointeur non-initialisé peut corrompre des parties de la mémoire ou générer des erreurs de segmentations. Par conséquent il est important que les pointeurs que l’on manipule soient initialisés.

Il existe une valeur particulière du pointeur qui est NULL (ou 0) qui est très souvent utilisé pour représenter des valeurs non-définies. Elle ne correspond à aucune case mémoire et donc son dé-référencement est impossible ! Un pointeur NULL est souvent renvoyé lorsqu’une comme valeur d’erreur dans une fonction qui manipule des adresses. Par exemple, il est possible d’utiliser cette valeur dans des tests:

void div_entier(int a, int b, int * p_q, int * p_r)
{
    if (NULL != p_q)
        *p_q = a / b;
    if (NULL != p_r)
        *p_r = a % b;
}

De manière générale, l’opérateur * ne peut être utilisé que sur des pointeurs valides à savoir:

des pointeurs vers une variable globale
des pointeurs vers une variable locale existante

Par extension, les pointeurs invalides sont:

les pointeurs NULL (ou 0)
les pointeurs non-initialisés
les pointeurs hors des tableaux
les pointeurs vers une variable locale détruite

L’exemple ci-dessous illustrer les cas de pointeurs valides ou invalides:

const int TAILLE_MAX = 50;

int * dummy(int a)
{
    int b = 5;
    int * c = &b; // PTR valide
    int * d; // PTR invalide
    int * e = NULL; // PTR invalide

    e = &(TAILLE_MAX); // e, PTR valide

    return c; // PTR invalide
}

int main()
{
    int x = 5;
    dummy(x);

    int tab[TAILLE_MAX];
    int * ptr = &(tab[0]); // PTR valide
    ptr = &(tab[2 * TAILLE_MAX]); // ptr devient invalide !

    return 0;
}

Cas des tableaux

Comme vous l’avez (ou pas) constaté dans le chapitre sur les tris, les tableaux étaient modifiés sans utiliser le pointeur. Ceci s’explique par le fait que les tableaux sont potentiellement volumineux en mémoire et que la copie mémoire est une opération coûteuse que l’on cherche à minimiser. Par conséquent, contrairement aux types de base, les paramètres de type tableaux ont leur adresse passée en paramètre. L’adresse d’un tableau étant la première case du tableau ce qui fait que l’adresse du tableau est égal à un pointeur sur la première case. De manière générale dans une expression (hormis sizeof, & et initialisation) tout tableau unidimensionnel est remplacé par un pointeur (non l-value) vers son premier élément.

Tableau et pointeur

Un tableau n'est pas un pointeur !

Ce mécanisme permet de se déplacer facilement dans un tableau puisque si p pointe sur une case du tableau p+i pointe sur la ième case après et p-i sur la ième case avant. Bien entendu les incréments de type ++ et -- fonctionnent. De même, les valeurs des pointeurs permettent de déterminer la distance entre les cases pointées.

Au final l’opérateur [] que l’on utilise pour accéder à une case particulière du tableau est une aide puisqu’en fait le compilateur va transformer cela en adresse dé-référencée. Par exemple int tab[5]; int c = t[2];, t[2] est en fait remplacé par *(t+2). Ceci explique pourquoi l’écriture 2[t] est valide puisqu’elle est remplacée par *(2+t).

Ci-dessous figurent des exemples de parcours de tableaux avec pointeurs (tableau d’entiers puis de caractères):

#include <stdio.h>

const int N = 50;

void imprime (int t[N])
{
    for (int *p_i = t; p_i < &t[N]; p_i++)
    {
        printf ("%d ", *p_i);
    }
    printf ("\n");
}

void imprime_char (char t[])
{
    char *ptr = t;
    while (*t != '\0')
    {
        printf ("%c", *ptr);
        ptr++;
    }
    printf ("\n");
}

int main ()
{
    int  tab[N];
    char tab2[] = "Hello World !";
    imprime (tab);
    imprime_char (tab2);

    return 0;
}

En ce qui concerne les tableaux de caractères, il existe des fonctions utiles déjà présentes dans la bibliothèque standard. Elles nécessitent l’inclusion de string.h et on trouve par exemple:

strlen: pour la longueur d’une chaîne de caractères
strcmp: pour la comparaison de deux chaînes de caractères
strcat: pour la concaténation de chaînes
strtok: pour chercher un motif dans une chaîne
…

En résumé

Les pointeurs sont utilisés pour:

passer l’adresse de variables
retourner plusieurs valeurs
parcourir des tableaux (voir TP)
gérer dynamiquement de la mémoire (semestre 6)
implémenter des structures de données complexes (listes chaînées, arbres…)
passer des fonctions en paramètres