Séance 6 — Pointeurs de fonctions et généricité

Adresse d’une fonction, types, tables de dispatch, rappels, qsort, conteneurs génériques

Séance 6 de Programmation C avancée : adresse d’une fonction, types, tables de dispatch, rappels, qsort, conteneurs génériques.

Auteur

Dr. El Hadji Bassirou TOURÉ · DMI/FST/UCAD

Navigation conceptuelle

Amont. Séance 3 : segments, pointeurs, void * ; Séance 4 : structures ; Séance 5 : Vecteur, listes, propriété des blocs, valgrind.

Aval. Structures de données et algorithmes (Java) : interfaces, Comparator, types génériques vérifiés par le compilateur. Cette séance clôt le cours ; sa dernière section en fait la synthèse.

Objectifs

Relever l’adresse d’une fonction (%p, gdb, nm) et la situer dans le segment de code.
Lire et écrire un type de pointeur de fonction, avec et sans typedef.
Appeler une fonction par un pointeur, et remplacer un switch par une table de dispatch.
Écrire une fonction de rappel, et un comparateur correct pour qsort et bsearch.
Programmer un échange, un tri, un tableau dynamique et une liste génériques, à partir de void *, d’une taille et de fonctions.
Dire ce que le compilateur ne vérifie plus dans du code générique, et reconnaître les comportements indéfinis qui en découlent.

Les programmes de ce document

Tous les programmes ont été compilés et exécutés sur la même machine : x86-64, Linux 6.18, gcc 13.3.0 avec les options -std=c17 -Wall -Wextra -O0 -g, glibc 2.39, gdb 15.1, valgrind 3.22.0 ; -fsanitize=address s’y ajoute pour AddressSanitizer. L’aléa des adresses est désactivé (setarch -R, environnement vide), si bien que les adresses affichées se répètent d’une exécution à l’autre ; sans cette précaution, elles changent à chaque lancement, et seuls les écarts restent. Chaque programme est lancé par ./nom depuis son dossier ; les sorties reproduites sont celles de ces exécutions ; dans les rapports, les lignes retirées sont remplacées par « ... » et le numéro du processus par PID. Les octets des grilles mémoire ont été relevés sous gdb. Dans les grilles, les adresses de la pile et du tas sont simplifiées (0x10, 0x80, …) en gardant la disposition réelle, et les adresses de code sont celles que donne nm ; l’adresse réelle est donnée dans le texte.

Une fonction en mémoire

Jusqu’ici, les pointeurs désignaient des données : une variable de la pile, un élément de tableau, un bloc du tas. Une fonction occupe elle aussi de la mémoire : son code compilé, une suite d’octets d’instructions, est rangé dans le segment de code du processus (la section .text de l’exécutable). Son nom désigne l’adresse de la première de ces instructions.

L’adresse d’une fonction

Le programme suivant affiche l’adresse de la fonction avec_tva (qui ajoute la TVA de 18 % à un prix en FCFA), celle de main, et, pour comparaison, celle d’une variable locale.

int avec_tva(int prix)
{
    return prix + prix * 18 / 100;
}
int main(void)
{
    int x = 0;
    printf("avec_tva  : %p\n", (void *)avec_tva);
    printf("&avec_tva : %p\n", (void *)&avec_tva);
    printf("main      : %p\n", (void *)main);
    printf("&x        : %p\n", (void *)&x);
    printf("sizeof    : %zu\n", sizeof &avec_tva);
    return 0;
}

Sortie :

avec_tva  : 0x555555555169
&avec_tva : 0x555555555169
main      : 0x55555555519d
&x        : 0x7fffffffece4
sizeof    : 8

avec_tva et &avec_tva donnent la même valeur : dans une expression, le nom d’une fonction est converti en un pointeur vers elle, sauf sous & et sizeof (C17 6.3.2.1 §4), comme le nom d’un tableau est converti en l’adresse de son premier élément. Les deux fonctions sont voisines, en 0x555555555169 et 0x55555555519d ; la variable x, elle, est dans la pile, vers 0x7fffffffe.... Un pointeur de fonction mesure 8 octets, comme un pointeur de donnée.

Le format %p attend un void *, d’où le cast. Or C17 ne définit la conversion d’un pointeur de fonction qu’en un autre pointeur de fonction (6.3.2.3 §8) : sa conversion en void * n’est pas garantie par la norme. POSIX l’exige (la fonction dlsym rend un void * qui peut désigner une fonction), et gcc l’accepte sans rien dire avec les options du cours ; l’option -Wpedantic, qui signale ce qui sort de la norme, la relève :

Compilateur :

s1_adresse.c:9:32: warning: ISO C forbids conversion of function pointer to object pointer type [-Wpedantic]
s1_adresse.c:10:32: warning: ISO C forbids conversion of function pointer to object pointer type [-Wpedantic]
s1_adresse.c:11:32: warning: ISO C forbids conversion of function pointer to object pointer type [-Wpedantic]

Le code d’une fonction, sous gdb

gdb montre l’adresse, et aussi les octets qui s’y trouvent. Le symbole avec_tva est d’abord interrogé avant le lancement, puis à l’arrêt au début de main :

Sortie de gdb :

(gdb) print avec_tva
$1 = {int (int)} 0x1169 <avec_tva>
(gdb) break main
Breakpoint 1 at 0x11a9: file s1_adresse.c, line 7.
(gdb) run
Breakpoint 1, main () at s1_adresse.c:7
7 {
(gdb) print avec_tva
$2 = {int (int)} 0x555555555169 <avec_tva>
(gdb) x/8xb avec_tva
0x555555555169 <avec_tva>: 0xf3 0x0f 0x1e 0xfa 0x55 0x48 0x89 0xe5
(gdb) info symbol avec_tva
avec_tva in section .text of ./s1_adresse
(gdb) x/2i avec_tva
   0x555555555169 <avec_tva>: endbr64
   0x55555555516d <avec_tva+4>: push   %rbp

Sortie de nm :

0000000000001169 T avec_tva
000000000000119d T main

Avant run, gdb donne 0x1169, la valeur que donne aussi nm : c’est le décalage de avec_tva dans l’exécutable. Un exécutable compilé par défaut sous Ubuntu est indépendant de la position (PIE) : au lancement, le chargeur le place à une adresse de base, ici 0x555555554000, et chaque adresse de code vaut cette base plus le décalage, $\texttt{0x555555554000}+\texttt{0x1169}=\texttt{0x555555555169}$. Sans setarch -R, la base est tirée au hasard à chaque exécution, et seul le décalage se retrouve d’une fois à l’autre.

x/8xb affiche les 8 premiers octets du code de avec_tva, et x/2i les désassemble : f3 0f 1e fa est l’instruction endbr64, que gcc place au début des fonctions pour la protection des sauts indirects, et 55 est push %rbp, le début du stack frame. info symbol confirme que l’adresse appartient à la section .text. Cette zone est projetée en lecture et en exécution, sans écriture : comme pour une chaîne littérale (Séance 3), une écriture y est un comportement indéfini ; ici SIGSEGV.

Exemple pas à pas : un pointeur de fonction

Pointeur de fonction

Un pointeur de fonction est une variable qui contient l’adresse du code d’une fonction. Son type indique les types des paramètres et du résultat : int (*f)(int) déclare un pointeur vers une fonction qui reçoit un int et rend un int. Il s’affecte, se compare, se range dans un tableau ou une structure, se passe en paramètre ; f(x) appelle la fonction qu’il désigne.

int avec_tva(int prix)
{
    return prix + prix * 18 / 100;
}
int remise(int prix)
{
    return prix - prix / 10;
}
int main(void)
{
    int (*f)(int) = avec_tva;
    int p = f(2500);
    f = remise;
    p = f(p);
    printf("%d\n", p);
    return 0;
}

Après la ligne 12

Après la ligne 13

Après la ligne 14

Après la ligne 15

Sous gdb, f est en 0x7fffffffec68 et p en 0x7fffffffec64, dans le stack frame de main ; la grille les place en 0x18 et 0x14. Les deux lignes du bas sont le début du code des deux fonctions, à leurs adresses de nm : avec_tva en 0x1149 et remise en 0x117d (à l’exécution, 0x555555555149 et 0x55555555517d). Les deux commencent par les mêmes octets, endbr64 puis push %rbp.

La ligne 12 range dans f l’adresse du code de avec_tva : 8 octets, comme n’importe quel pointeur. À la ligne 13, f(2500) est un appel indirect : le processeur lit l’adresse contenue dans f (cases orange) et saute à ce code, qui calcule $2500+2500\times18/100=2950$. La ligne 14 ne modifie que les 8 octets de f, qui désigne maintenant remise ; aucun octet de code ne change. La ligne 15 exécute la même instruction d’appel, mais l’adresse lue est différente : c’est remise qui s’exécute, et rend $2950-295=2655$.

Sortie :

Appel par un pointeur invalide

Un pointeur de fonction NULL ou non initialisé ne désigne aucun code : l’appeler est un comportement indéfini (C17, annexe J.2), qui se termine le plus souvent par SIGSEGV. Appeler une fonction par un pointeur dont le type ne correspond pas au sien est aussi un comportement indéfini (6.3.2.3 §8, 6.5.2.2 §9, section Section 7).

Lecture et écriture des types

Le type d’un pointeur de fonction s’écrit autour du nom déclaré, comme celui d’un tableau. Les parenthèses de (*f) sont indispensables : l’opérateur d’appel () lie plus fort que *, si bien que int *f(int) déclare une fonction qui rend un int *, et non un pointeur.

déclaration	lecture
int f(int);	`f` : fonction (`int`) rendant `int`
int *f(int);	`f` : fonction (`int`) rendant `int *`
int (*f)(int);	`f` : pointeur vers fonction (`int`) rendant `int`
int (*t[4])(int, int);	`t` : tableau de 4 pointeurs vers fonction (`int`, `int`) rendant `int`
int (p)(int *, int);	`p` : pointeur vers fonction (`int `, `int`) rendant `int `
int ((q)(char))(int, int);	`q` : pointeur vers fonction (`char`) rendant un pointeur vers
	fonction (`int`, `int`) rendant `int`

Sans le nom, la même écriture donne le type lui-même, utile dans un cast ou un prototype : int (*)(int) est le type de f, int (*)(const void *, const void *) celui du comparateur de qsort. Toutes ces déclarations se compilent avec les options du cours.

Lecture d’une déclaration

Règle de droite à gauche

Partir du nom déclaré ; lire à droite tant qu’il y a des (…) (« fonction (…) rendant ») ou des [n] (« tableau de $n$ ») ; puis à gauche, les * (« pointeur vers ») ; une parenthèse fermante arrête la lecture vers la droite, une parenthèse ouvrante celle vers la gauche : sortir de la parenthèse et recommencer ; finir par le type écrit tout à gauche.

Ce trajet, qui alterne la droite et la gauche en s’éloignant du nom, est appelé règle de droite à gauche. Appliquée à la déclaration de signal dans <signal.h> :

void (*signal(int, void (*)(int)))(int);

signal, à droite (int, void (*)(int)) : fonction recevant un int et un pointeur vers fonction (int) rendant void ;
à gauche, * : rendant un pointeur ;
la parenthèse ouvrante arrête la lecture vers la gauche ; en sortant, à droite (int) : vers une fonction (int) ;
à gauche, void : rendant void.

signal reçoit un numéro de signal et le gestionnaire à installer, et rend l’ancien gestionnaire : le paramètre et le résultat ont le même type, « pointeur vers fonction (int) rendant void ».

Nom du type : `typedef`

typedef se lit comme une déclaration de variable : le nom déclaré devient un nom de type. On nomme ainsi le type pointeur une fois, et les déclarations qui l’utilisent redeviennent lisibles :

typedef int (*Operation)(int, int);
Operation op = plus;
Operation (*q)(char);
Operation choisir(char c);

typedef void (*Gestionnaire)(int);
Gestionnaire signal(int sig, Gestionnaire g);
typedef int Fonction(int, int);
Fonction *op2 = plus;

Operation (*q)(char) remplace int (*(*q)(char))(int, int), et la déclaration de signal tient en une ligne. La seconde forme, typedef int Fonction(int, int);, nomme le type fonction lui-même : un pointeur se déclare alors Fonction *op2, et l’étoile reste visible, ce que certains préfèrent pour ne pas cacher qu’il s’agit d’un pointeur. L’exercice 1 (section Section 8) applique ces règles.

Appel indirect et table de dispatch

`f`, `*f` et `**f` : un même appel indirect

int avec_tva(int prix)
{
    return prix + prix * 18 / 100;
}
int main(void)
{
    int (*f)(int) = avec_tva;
    int a = avec_tva(1000);
    int b = f(1000);
    int c = (*f)(1000);
    int d = (**f)(1000);
    printf("%d %d %d %d\n", a, b, c, d);
    printf("%d\n", f == &avec_tva);
    return 0;
}

Sortie :

1180 1180 1180 1180
1

Les quatre appels rendent 1180 : f(1000), (*f)(1000) et même (**f)(1000) sont équivalents. *f désigne la fonction, mais un désignateur de fonction est aussitôt reconverti en pointeur ; l’opérateur d’appel s’applique, dans tous les cas, à un pointeur de fonction (C17 6.5.2.2 §1). La comparaison f == &avec_tva vaut 1 : deux pointeurs de fonction se comparent comme des pointeurs de données. Le code machine produit par gcc montre la différence entre les deux sortes d’appel :

Sortie de objdump -d :

1189: lea    -0x47(%rip),%rax        # 1149 <avec_tva>
1199: call   1149 <avec_tva>
11a1: mov    -0x8(%rbp),%rax
11aa: call   *%rax
11af: mov    -0x8(%rbp),%rax
11b8: call   *%rax
11bd: mov    -0x8(%rbp),%rax
11c6: call   *%rax
11f0: lea    -0xae(%rip),%rax        # 1149 <avec_tva>

L’appel direct avec_tva(1000) est call 1149 : l’adresse de la fonction est inscrite dans l’instruction, à la compilation (ici en décalage dans l’exécutable). L’appel par f charge d’abord le pointeur depuis la pile, mov -0x8(%rbp),%rax, puis exécute call *%rax : le processeur saute à l’adresse contenue dans le registre. C’est un appel indirect : la fonction appelée n’est connue qu’à l’exécution. La première instruction, lea -0x47(%rip),%rax, calcule l’adresse de avec_tva relativement à l’instruction courante, ce qui permet au programme de fonctionner à n’importe quelle adresse de base.

Exemple pas à pas : une table de dispatch

Puisqu’un pointeur de fonction est une donnée, des pointeurs de même type se rangent dans un tableau. Les quatre opérations du mini-calculateur ont le même type, int (int, int) :

/* operations.h -- les quatre operations du mini-calculateur et leur type */
typedef int (*Operation)(int, int);
int plus(int a, int b)
{
    return a + b;
}
int moins(int a, int b)
{
    return a - b;
}
int fois(int a, int b)
{
    return a * b;
}
int divise(int a, int b)
{
    return a / b;
}

Table de dispatch

Une table de dispatch est un tableau de pointeurs de fonctions de même type, indexé par un code (un indice, un symbole, un état) : t[k](a, b) appelle la fonction associée au code k. Elle remplace une suite de if ou un switch, et s’étend en ajoutant une case, sans modifier le code qui appelle.

Operation op[4] = {plus, moins, fois, divise};
int acc = 1200;
acc = op[2](acc, 3);
acc = op[0](acc, 400);
acc = op[3](acc, 8);
printf("%d\n", acc);

Après la ligne 5

Après la ligne 7

Après la ligne 8

Après la ligne 9

Sous gdb, op est en 0x7fffffffec40 et acc juste avant, en 0x7fffffffec3c ; la grille les place en 0x18 et 0x14. La ligne 5 remplit quatre cases de 8 octets avec les adresses du code de plus, moins, fois et divise, montrées en valeurs de nm (0x1169, 0x1181, 0x1197, 0x11ae ; à l’exécution, 0x555555555169, …). À la ligne 7, op[2] est lu à l’adresse $\texttt{op}+2\times8$, et l’appel indirect exécute fois : $1200\times3=3600$. Les lignes 8 et 9 choisissent plus puis divise par leur seul indice : $3600+400=4000$, puis $4000/8=500$. Le code de main ne contient aucun test : c’est l’indice qui choisit la fonction.

Sortie :

Un menu de commandes

Dans un programme réel, la clé n’est pas toujours un indice. La table suivante associe à chaque symbole d’opération sa fonction ; trouver la parcourt et rend l’adresse de la commande, ou NULL pour un symbole inconnu.

typedef struct {
    char symbole;
    Operation f;
} Commande;
static const Commande menu[] = {
    {'+', plus},
    {'-', moins},
    {'*', fois},
    {'/', divise},
};
#define NCMD (sizeof menu / sizeof menu[0])
const Commande *trouver(char c)
{
    for (size_t i = 0; i < NCMD; i++)
        if (menu[i].symbole == c)
            return &menu[i];
    return NULL;    /* symbole inconnu */
}
int main(void)
{
    const char op[4] = {'*', '+', '%', '/'};
    const int val[4] = {4, 350, 2, 5};
    int acc = 250;
    for (int i = 0; i < 4; i++) {
        const Commande *k = trouver(op[i]);
        if (k != NULL)
            acc = k->f(acc, val[i]);
        printf("%c%d -> %d\n", op[i], val[i], acc);
    }
    return 0;
}

Sortie :

*4 -> 1000
+350 -> 1350
/5 -> 270

Le symbole % n’est pas dans la table : trouver rend NULL, l’appel est évité et acc garde sa valeur, 1350. Ajouter une commande, par exemple le reste de la division, revient à ajouter une fonction et une ligne à menu : ni trouver ni main ne changent. C’est la propriété recherchée dans les interpréteurs de commandes, les menus et les gestionnaires d’événements. La division par zéro n’est pas traitée ici : une commande /0 serait un comportement indéfini, à refuser avant l’appel.

Un automate par table

Un automate passe d’un état à l’autre selon les caractères lus. Chaque état devient une fonction qui lit un caractère et rend l’état suivant ; l’état courant est un indice dans une table de ces fonctions.

typedef int (*Etat)(char c, int *mots);
int dehors(char c, int *mots)
{
    if (c == ' ')
        return 0;           /* reste dehors */
    (*mots)++;              /* debut d'un mot */
    return 1;
}
int dedans(char c, int *mots)
{
    (void)mots;
    return c == ' ' ? 0 : 1;
}
int main(void)
{
    Etat automate[2] = {dehors, dedans};
    const char *phrase = " Thies  Mbour Kaolack ";
    int e = 0;
    int mots = 0;
    for (const char *p = phrase; *p != '\0'; p++)
        e = automate[e](*p, &mots);
    printf("%d mots\n", mots);
    return 0;
}

Sortie :

3 mots

L’automate compte les mots d’une phrase dont les mots sont séparés par une ou plusieurs espaces. Dans l’état 0 (dehors), une espace laisse l’automate dehors ; une lettre marque le début d’un mot, incrémente le compteur et fait passer à l’état 1 (dedans). Dans l’état 1, une lettre garde l’automate dedans, une espace le fait sortir. Les espaces doublées et les espaces en tête et en fin ne créent aucun mot : « Thies », « Mbour », « Kaolack », trois mots. La boucle de main ne connaît pas les règles : elles sont dans les fonctions d’état.

Le `switch` et sa table de sauts

Le compilateur emploie lui-même une table pour certains switch. Quand les valeurs des cas sont voisines, il range dans .rodata une table de sauts (jump table) indexée par la valeur testée.

int frais(int zone)
{
    switch (zone) {
    case 0:
        return 500;
    case 1:
        return 1000;
    case 2:
        return 1500;
    case 3:
        return 2500;
    case 4:
        return 3000;
    default:
        return -1;
    }
}
int main(void)
{
    printf("%d\n", frais(3));
    return 0;
}

Sortie de objdump -d :

1154: cmpl   $0x4,-0x4(%rbp)
1158: ja     11a1 <frais+0x58>
115a: mov    -0x4(%rbp),%eax
115d: lea    0x0(,%rax,4),%rdx
1165: lea    0xe98(%rip),%rax        # 2004
116c: mov    (%rdx,%rax,1),%eax
116f: cltq
1171: lea    0xe8c(%rip),%rdx        # 2004
1178: add    %rdx,%rax
117b: notrack jmp *%rax
117e: mov    $0x1f4,%eax
1193: mov    $0x9c4,%eax
11a1: mov    $0xffffffff,%eax

Sortie de objdump -s -j .rodata :

 2000 01000200 7af1ffff 81f1ffff 88f1ffff  ....z...........
 2010 8ff1ffff 96f1ffff 25640a00           ........%d..

cmpl $0x4 puis ja envoient vers le cas default toute valeur supérieure à 4 (la comparaison non signée traite aussi les négatives). La table commence en 0x2004 : lea 0x0(,%rax,4),%rdx multiplie la valeur par 4, mov (%rdx,%rax,1),%eax lit l’entrée de 4 octets, et add l’ajoute à l’adresse de la table : les entrées sont des décalages relatifs, ce qui garde le code indépendant de la position. Pour le cas 0, les octets 7a f1 ff ff valent 0xfffff17a, soit $-$0xe86 ; $\texttt{0x2004}-\texttt{0xe86}=\texttt{0x117e}$, l’adresse du mov $0x1f4,%eax qui rend 500. notrack jmp *%rax est le saut indirect. Une table de dispatch fait la même chose au niveau du programme, avec des fonctions à la place des branches.

Fonctions de rappel

Fonction passée en paramètre

Un paramètre peut être un pointeur de fonction. La fonction qui le reçoit applique alors un traitement qu’elle ne connaît pas, choisi par son appelant : c’est le principe de la fonction de rappel.

Fonction de rappel (callback)

Une fonction de rappel est une fonction passée en paramètre à une autre, qui l’appelle à son tour au moment voulu. L’appelant fournit le traitement ; la fonction appelée fournit le parcours, l’ordre ou l’événement.

void appliquer(int *t, size_t n, int (*f)(int))
{
    for (size_t i = 0; i < n; i++)
        t[i] = f(t[i]);
}
size_t filtrer(const int *t, size_t n, int *dest,
               int (*garde)(int))
{
    size_t k = 0;
    for (size_t i = 0; i < n; i++)
        if (garde(t[i]))
            dest[k++] = t[i];
    return k;
}
int avec_tva(int prix)
{
    return prix + prix * 18 / 100;
}
int cher(int prix)
{
    return prix >= 2000;
}
int main(void)
{
    int prix[5] = {1500, 700, 2500, 350, 4000};
    int choisis[5];
    appliquer(prix, 5, avec_tva);
    size_t k = filtrer(prix, 5, choisis, cher);
    for (size_t i = 0; i < k; i++)
        printf("%d ", choisis[i]);
    printf("(%zu sur 5)\n", k);
    return 0;
}

Sortie :

2950 4720 (2 sur 5)

appliquer remplace chaque élément par f(t[i]) ; filtrer copie dans dest les éléments pour lesquels garde rend une valeur non nulle, et en rend le nombre. Aucune des deux ne connaît la TVA ni le seuil de 2000 FCFA : avec_tva et cher, les fonctions de rappel, les apportent. Les mêmes appliquer et filtrer serviraient à convertir des prix en euros ou à garder les prix pairs.

Le flux d’un rappel

Après appliquer(prix, 5, avec_tva), prix contient 1770, 826, 2950, 413 et 4720. Le schéma suit l’appel de filtrer : main l’appelle une fois ; filtrer, écrite sans connaître cher, la rappelle pour chaque élément, et cher répond 1 pour 2950 et 4720. Chaque rappel est un appel indirect : filtrer empile l’adresse de retour, et cher crée son propre stack frame, sous celui de filtrer. Le contrôle va donc de main vers la bibliothèque, puis revient dans le code de l’utilisateur, d’où le nom de rappel.

Un contexte en `void *`

Une fonction de rappel ne dispose que de ses paramètres. Pour qu’elle accumule un résultat, ou consulte un seuil, la fonction qui la rappelle transmet un pointeur de contexte, qu’elle ne lit pas elle-même.

typedef struct {
    int seuil;
    int nombre;
    long total;
} Bilan;
void pour_chaque(const int *t, size_t n,
                 void (*f)(int, void *), void *ctx)
{
    for (size_t i = 0; i < n; i++)
        f(t[i], ctx);
}
void compter(int x, void *ctx)
{
    Bilan *b = ctx;     /* au bon type */
    if (x >= b->seuil) {
        b->nombre++;
        b->total += x;
    }
}
int main(void)
{
    int v[5] = {12000, 3500, 27500, 800, 15000};
    Bilan b = {10000, 0, 0};
    pour_chaque(v, 5, compter, &b);
    printf("%d ventes, %ld\n", b.nombre, b.total);
    return 0;
}

Sortie :

3 ventes, 54500

pour_chaque reçoit ctx sous forme de void * et le transmet tel quel à chaque appel. compter sait que ce contexte est un Bilan : elle le convertit, compare chaque vente au seuil et accumule. Trois ventes atteignent 10 000 FCFA, pour $12000+27500+15000=54500$ FCFA. Ce modèle — une fonction, et un void * qui l’accompagne — est celui de qsort_r (glibc), de pthread_create et de la plupart des bibliothèques à rappels ; il évite les variables globales.

`qsort` et `bsearch`

Le contrat du comparateur

La bibliothèque standard fournit un tri et une recherche dichotomique génériques (C17 7.22.5) :

void qsort(void *base, size_t n, size_t taille,
           int (*cmp)(const void *, const void *));
void *bsearch(const void *cle, const void *base, size_t n, size_t taille,
              int (*cmp)(const void *, const void *));

qsort trie les n éléments de taille octets qui commencent en base. Il ne connaît pas leur type : il déplace des blocs d’octets, et confie l’ordre au comparateur.

Comparateur

Un comparateur reçoit les adresses de deux éléments et rend un entier négatif, nul ou positif selon que le premier doit précéder le second, lui est équivalent, ou doit le suivre. Ses réponses doivent être cohérentes (un ordre total) ; il ne modifie pas les éléments, d’où const void *.

La norme n’impose ni l’algorithme, ni l’ordre final de deux éléments équivalents (le tri n’est pas garanti stable). Un comparateur qui répond de façon incohérente rend l’appel de qsort indéfini (C17 7.22.5 §4).

Tri des étudiants par moyenne puis par nom

typedef struct {
    char nom[12];
    double moyenne;
} Etudiant;
int par_moyenne(const void *a, const void *b)
{
    const Etudiant *x = a;
    const Etudiant *y = b;
    if (x->moyenne != y->moyenne)
        return x->moyenne < y->moyenne ? 1 : -1;
    return strcmp(x->nom, y->nom);  /* puis nom */
}
int main(void)
{
    Etudiant promo[5] = {
        {"Moussa", 12.25}, {"Awa", 14.50},
        {"Fatou", 14.50}, {"Amadou", 16.00},
        {"Binta", 12.25},
    };
    qsort(promo, 5, sizeof promo[0], par_moyenne);
    for (int i = 0; i < 5; i++) {
        const Etudiant *e = &promo[i];
        printf("%-7s %5.2f\n", e->nom, e->moyenne);
    }
    return 0;
}

Sortie :

Amadou  16.00
Awa     14.50
Fatou   14.50
Binta   12.25
Moussa  12.25

Les paramètres const void * se convertissent sans cast en const Etudiant * ; garder const respecte le contrat. Le premier critère est la moyenne, décroissante : si x a la plus petite moyenne, il doit venir après, d’où 1. À moyenne égale, strcmp départage par ordre alphabétique : Awa avant Fatou à 14,50, Binta avant Moussa à 12,25. La comparaison x->moyenne != y->moyenne sur des double est exacte ici, car 12,25 et 14,50 sont représentables en binaire (Séance 2) ; pour des moyennes calculées, deux valeurs « égales » peuvent différer au dernier bit.

Les appels au comparateur

Un comparateur qui affiche ses paramètres montre ce que fait qsort :

static int appels = 0;
int cmp_trace(const void *a, const void *b)
{
    int x = *(const int *)a;
    int y = *(const int *)b;
    appels++;
    printf("(%d,%d) ", x, y);
    return (x > y) - (x < y);
}
int main(void)
{
    int t[5] = {42, 17, 8, 23, 4};
    qsort(t, 5, sizeof t[0], cmp_trace);
    printf("\n%d appels :", appels);
    for (int i = 0; i < 5; i++)
        printf(" %d", t[i]);
    printf("\n");
    return 0;
}

Sortie :

(42,17) (23,4) (8,4) (8,23) (17,4) (17,8) (17,23) (42,23) 
8 appels : 4 8 17 23 42

La glibc 2.39 trie par fusion : elle coupe le tableau en $\lfloor n/2\rfloor$ et $n-\lfloor n/2\rfloor$ éléments, trie chaque partie de la même façon, puis fusionne les deux parties triées en comparant leurs têtes. Pour [42 17 8 23 4] : [42 17] se trie par (42,17) ; [8 23 4] se coupe en [8] et [23 4], qui donne (23,4), puis la fusion de [8] et [4 23] compare (8,4) et (8,23). La fusion finale de [17 42] et [4 8 23] compare 17 à 4, 8 et 23, puis 42 à 23 ; 42 reste seul. Huit appels pour cinq éléments. Dans la glibc 2.39 (stdlib/qsort.c), le tampon de fusion est pris dans la pile jusqu’à 1024 octets, alloué par malloc au-delà ; les éléments de plus de 32 octets sont triés indirectement, par un tableau de pointeurs ; le repli sur un tri par tas n’a lieu que si malloc échoue. Les versions 2.37 et 2.38 utilisaient un introsort. Une autre bibliothèque, ou une autre version, ferait d’autres appels : un programme ne doit dépendre que du contrat, jamais de l’ordre des appels.

Deux pièges

int cmp_faux(const void *a, const void *b)
{
    return *(const int *)a - *(const int *)b;
}
int cmp_juste(const void *a, const void *b)
{
    int x = *(const int *)a;
    int y = *(const int *)b;
    return (x > y) - (x < y);   /* -1, 0 ou 1 */
}
void afficher(const int *t, int n)
{
    for (int i = 0; i < n; i++)
        printf("%d ", t[i]);
    printf("\n");
}
int main(void)
{
    int t[4] = {2000000000, -2000000000, 5, -7};
    int u[4] = {2000000000, -2000000000, 5, -7};
    qsort(t, 4, sizeof t[0], cmp_faux);
    qsort(u, 4, sizeof u[0], cmp_juste);
    afficher(t, 4);
    afficher(u, 4);
    return 0;
}

Sortie :

-7 5 2000000000 -2000000000 
-2000000000 -7 5 2000000000

cmp_faux rend la différence des deux valeurs. Elle a le bon signe tant que la différence tient dans un int ; mais $2\,000\,000\,000-(-2\,000\,000\,000)=4\,000\,000\,000$ dépasse INT_MAX. Le débordement d’un entier signé est un comportement indéfini (Séance 2) ; ici le résultat repart des négatifs, la comparaison est inversée, et le tableau sort dans le désordre. cmp_juste compare au lieu de soustraire : (x > y) - (x < y) vaut $-1$, 0 ou 1, sans calcul qui puisse déborder.

int cmp_tronque(const void *a, const void *b)
{
    double x = *(const double *)a;
    double y = *(const double *)b;
    return (int)(x - y);
}
int main(void)
{
    double m[4] = {12.75, 9.5, 12.25, 12.5};
    qsort(m, 4, sizeof m[0], cmp_tronque);
    for (int i = 0; i < 4; i++)
        printf("%.2f ", m[i]);
    printf("\n");
    return 0;
}

Sortie :

9.50 12.75 12.25 12.50

cmp_tronque soustrait deux double et convertit le résultat en int, ce qui tronque vers zéro : $12{,}75-12{,}25=0{,}5$ devient 0, et deux moyennes différentes passent pour équivalentes. 12,75 reste avant 12,25. La règle est la même : comparer avec < et >, ne pas soustraire.

`bsearch` dans un catalogue

typedef struct {
    int code;
    const char *nom;
    int prix;           /* FCFA */
} Produit;
int par_code(const void *a, const void *b)
{
    int x = ((const Produit *)a)->code;
    int y = ((const Produit *)b)->code;
    return (x > y) - (x < y);
}
int cle_code(const void *cle, const void *e)
{
    int x = *(const int *)cle;
    int y = ((const Produit *)e)->code;
    return (x > y) - (x < y);
}
int main(void)
{
    Produit cat[3] = {
        {310, "sucre 1 kg", 700},
        {120, "riz 25 kg", 15500},
        {208, "huile 1 L", 1300},
    };
    qsort(cat, 3, sizeof cat[0], par_code);
    int cles[2] = {208, 300};
    for (int i = 0; i < 2; i++) {
        Produit *p = bsearch(&cles[i], cat, 3,
                             sizeof cat[0], cle_code);
        printf("%d : %s\n", cles[i],
               p != NULL ? p->nom : "absent");
    }
    return 0;
}

Sortie :

208 : huile 1 L
300 : absent

bsearch cherche par dichotomie dans un tableau trié selon le même ordre que son comparateur : qsort trie d’abord le catalogue par code. Le comparateur de bsearch reçoit toujours la clé en premier et un élément du tableau en second ; ils peuvent être de types différents : ici un int et un Produit. bsearch rend l’adresse de l’élément trouvé (p - cat en donne l’indice), ou NULL si la clé est absente, comme 300. Un tableau non trié, ou trié selon un autre ordre, donne un résultat faux sans message.

Généricité

Les structures de la Séance 5 ne rangeaient que des int. Les écrire pour des double, des chaînes ou des Article obligerait à recopier le code pour chaque type. qsort montre l’autre voie.

Fonction générique

Une fonction générique traite des éléments de type quelconque à partir de trois informations : leur adresse, en void * ; leur taille en octets ; et des fonctions qui, elles, connaissent le type (comparer, afficher, libérer). Elle copie les éléments par memcpy et calcule leurs adresses en octets, par (char *)base + i * taille.

L’arithmétique sur void * n’est pas définie en C (un void n’a pas de taille) ; la conversion en char * donne une arithmétique en octets. Le code qui dépend du type se réduit à quelques fonctions courtes, passées en paramètre.

Exemple pas à pas : un échange générique

typedef struct {
    int code;
    int prix;
} Article;
void echanger(void *a, void *b, size_t taille)
{
    unsigned char tmp[taille];
    memcpy(tmp, a, taille);
    memcpy(a, b, taille);
    memcpy(b, tmp, taille);
}
int main(void)
{
    Article x = {12, 1300};
    Article y = {7, 650};
    echanger(&x, &y, sizeof(Article));
    printf("%d %d\n", x.code, y.code);
    return 0;
}

Ligne 18 : l’appel (ligne 9)

Après la ligne 10

Après la ligne 11

Après la ligne 12

Sous gdb, x est en 0x7fffffffec58 et y 8 octets plus loin, dans le stack frame de main ; le stack frame de echanger est plus bas : a en 0x7fffffffec08, b et taille juste en dessous, et le tampon tmp, un tableau de longueur variable (Séance 3), en 0x7fffffffebe0. La grille place tmp en 0x10 et x, y en 0x88 et 0x90.

echanger reçoit deux adresses et un nombre d’octets, 8 : elle ignore qu’il s’agit d’Article. La ligne 9 réserve 8 octets dans la pile pour tmp. Les trois memcpy déplacent des octets sans les interpréter : ceux de x vers tmp, ceux de y vers x, ceux de tmp vers y. On reconnaît 0c 00 00 00 (12) et 14 05 00 00 (1300) qui passent de x à y. Au retour, le stack frame de echanger est rendu ; x vaut {7, 650} et y {12, 1300}. Le même code échange deux double, deux pointeurs ou deux structures de 200 octets.

Sortie :

7 12

Un tri générique

Le tri par insertion de l’algorithmique s’écrit une fois pour tout type d’élément, avec la signature de qsort :

typedef int (*Comparateur)(const void *, const void *);
void tri_insertion(void *base, size_t n,
                   size_t taille, Comparateur cmp)
{
    char *p = base;     /* adresses en octets */
    for (size_t i = 1; i < n; i++)
        for (char *b = p + i * taille;
             b > p && cmp(b - taille, b) > 0;
             b -= taille)
            echanger(b - taille, b, taille);
}
int cmp_int(const void *a, const void *b)
{
    int x = *(const int *)a;
    int y = *(const int *)b;
    return (x > y) - (x < y);
}
int par_nom(const void *a, const void *b)
{
    const char *const *x = a; /* char * */
    const char *const *y = b;
    return strcmp(*x, *y);
}
int main(void)
{
    int t[4] = {42, 17, 8, 23};
    const char *v[3] = {"Matam", "Kolda",
                        "Bakel"};
    tri_insertion(t, 4, sizeof *t, cmp_int);
    tri_insertion(v, 3, sizeof *v, par_nom);
    for (int i = 0; i < 4; i++)
        printf("%d ", t[i]);
    printf("| %s %s %s\n", v[0], v[1], v[2]);
    return 0;
}

Sortie :

8 17 23 42 | Bakel Kolda Matam

p est un char * : p + i * taille est l’adresse de l’élément i, et b - taille celle de l’élément précédent. Tant que l’élément précédent doit venir après, les deux sont échangés et b recule d’un élément. Pour le tableau de chaînes, chaque élément est un const char * : le comparateur reçoit donc l’adresse d’un pointeur, un const char *const * déguisé en const void *, et compare les chaînes désignées. Passer directement strcmp comme comparateur serait une erreur, que montre la section Section 7.

Exemple pas à pas : le `Vecteur` générique

Le Vecteur de la Séance 5 devient générique en remplaçant int * par void * et en gardant la taille d’un élément :

typedef struct {
    void *donnees;      /* bloc du tas */
    size_t taille;      /* elements ranges */
    size_t capacite;    /* places du bloc */
    size_t taille_elem; /* octets par element */
} VecteurG;
void vg_init(VecteurG *v, size_t te, size_t cap)
{
    v->donnees = malloc(cap * te);
    v->taille = 0;
    v->capacite = v->donnees != NULL ? cap : 0;
    v->taille_elem = te;
}
void *vg_elem(const VecteurG *v, size_t i)
{
    char *base = v->donnees;
    return base + i * v->taille_elem;
}
int vg_ajouter(VecteurG *v, const void *x)
{
    if (v->taille == v->capacite) {
        size_t cap = v->capacite == 0 ? 1
                     : 2 * v->capacite;
        size_t octets = cap * v->taille_elem;
        void *t = realloc(v->donnees, octets);
        if (t == NULL)
            return 0;
        v->donnees = t;
        v->capacite = cap;
    }
    void *dest = vg_elem(v, v->taille);
    memcpy(dest, x, v->taille_elem);
    v->taille++;
    return 1;
}

vg_elem calcule l’adresse de l’élément i en octets ; vg_ajouter garde la règle du doublement et copie les taille_elem octets reçus à l’adresse de la première place libre.

typedef struct {
    int code;
    int prix;
} Article;
int main(void)
{
    VecteurG v;
    vg_init(&v, sizeof(Article), 2);
    vg_ajouter(&v, &(Article){12, 1300});
    vg_ajouter(&v, &(Article){7, 650});
    vg_ajouter(&v, &(Article){31, 4800});
    Article *a = vg_elem(&v, 2);
    printf("%zu %d\n", v.capacite, a->prix);
    vg_liberer(&v, NULL);
    return 0;
}

Après la ligne 10

Après la ligne 12

Après la ligne 13

Après la ligne 14

Sous gdb, v est en 0x7fffffffec40 (pile), et le bloc en 0x5555555592a0 (tas) ; la grille les place en 0x10 et 0x80, et l’en-tête de la glibc en 0x78. La ligne 10 demande $2\times8=16$ octets : un bloc de 32 octets (en-tête 0x21), dont 24 utiles. Les lignes 11 et 12 copient deux Article de 8 octets en $\texttt{0x80}+0\times8$ et $\texttt{0x80}+1\times8$ : le bloc est plein. À la ligne 13, realloc demande $4\times8=32$ octets ; le bloc est le dernier du tas, et la glibc l’agrandit en place : même adresse, en-tête 0x31 (48 octets). La quatrième place n’est pas initialisée. La ligne 14 obtient 0x90, l’adresse du troisième élément, en void *, et la convertit en Article * : le type de l’élément n’apparaît qu’à cette conversion.

Sortie :

4 4800

Des éléments qui possèdent un bloc

Un élément peut posséder un bloc du tas, par exemple une chaîne copiée. Libérer le seul bloc du vecteur laisserait ces blocs sans propriétaire : il faut d’abord libérer ce que possède chaque élément, et seul l’appelant sait comment. vg_liberer reçoit donc une fonction de libération, appelée sur l’adresse de chaque élément :

void vg_liberer(VecteurG *v, void (*lib)(void *))
{
    if (lib != NULL)
        for (size_t i = 0; i < v->taille; i++)
            lib(vg_elem(v, i));
    free(v->donnees);
    *v = (VecteurG){NULL, 0, 0, v->taille_elem};
}

void liberer_chaine(void *e)
{
    free(*(char **)e);  /* un char * */
}
int main(void)
{
    const char *s[3] = {"Fatou", "Khadim", "Awa"};
    VecteurG noms;
    vg_init(&noms, sizeof(char *), 1);
    for (int i = 0; i < 3; i++) {
        char *copie = malloc(strlen(s[i]) + 1);
        if (copie == NULL)
            break;
        strcpy(copie, s[i]);
        vg_ajouter(&noms, &copie);
    }
    for (size_t i = 0; i < noms.taille; i++) {
        char **e = vg_elem(&noms, i);
        printf("%s ", *e);
    }
    printf("\n");
    vg_liberer(&noms, liberer_chaine);
    return 0;
}

Sortie :

Fatou Khadim Awa

Sortie d’erreur sous valgrind :

All heap blocks were freed -- no leaks are possible

Chaque élément de noms est un char * : vg_ajouter(&noms, &copie) copie les 8 octets du pointeur copie, et le vecteur devient propriétaire de la chaîne (Séance 5). vg_liberer passe à liberer_chaine l’adresse de l’élément, c’est-à-dire un char ** : la fonction lit le pointeur rangé, puis libère la chaîne. valgrind confirme que les trois chaînes et le bloc du vecteur ont été rendus. Pour un vecteur d’Article, qui ne possèdent rien, la fonction de libération est NULL.

Une liste générique

Une liste générique garde dans chaque nœud un void * vers sa donnée :

typedef struct NoeudG {
    void *donnee;           /* possedee */
    struct NoeudG *suivant;
} NoeudG;
void liste_ajouter(NoeudG **pt, void *donnee)
{
    NoeudG *n = malloc(sizeof *n);
    if (n == NULL)
        return;
    n->donnee = donnee;
    n->suivant = *pt;
    *pt = n;
}
void parcourir(const NoeudG *p, void (*f)(void *))
{
    for (; p != NULL; p = p->suivant)
        f(p->donnee);
}
void liste_liberer(NoeudG **pt,
                   void (*lib)(void *))
{
    NoeudG *p = *pt;
    while (p != NULL) {
        NoeudG *s = p->suivant;
        if (lib != NULL)
            lib(p->donnee); /* la donnee d'abord */
        free(p);
        p = s;
    }
    *pt = NULL;
}
typedef struct {
    char ville[12];
    int clients;
} Agence;
Agence *agence(const char *v, int c)
{
    Agence *a = malloc(sizeof *a);
    if (a == NULL)
        return NULL;
    strcpy(a->ville, v);
    a->clients = c;
    return a;
}
void afficher(void *d)
{
    const Agence *a = d;
    printf("%s (%d) ", a->ville, a->clients);
}
int main(void)
{
    NoeudG *l = NULL;
    liste_ajouter(&l, agence("Podor", 120));
    liste_ajouter(&l, agence("Matam", 85));
    liste_ajouter(&l, agence("Kedougou", 64));
    parcourir(l, afficher);
    printf("\n");
    liste_liberer(&l, free);
    return 0;
}

Sortie :

Kedougou (64) Matam (85) Podor (120)

Sortie d’erreur sous valgrind :

All heap blocks were freed -- no leaks are possible

liste_ajouter insère en tête (Séance 5, pointeur de pointeur) ; parcourir applique une fonction de rappel à chaque donnée ; liste_liberer appelle lib sur chaque donnée avant de libérer le nœud qui la désigne, et lit le suivant avant le free. Ici les Agence sont allouées par agence et ne possèdent aucun autre bloc : free convient comme fonction de libération. Si la liste ne possédait pas ses données (des adresses de variables locales, par exemple), on passerait NULL.

Limites

La perte du typage

Dans du code générique, le compilateur ne voit que des void * et des tailles : il ne peut plus vérifier que la taille, le comparateur ou la conversion correspondent au type des éléments.

void echanger(void *a, void *b, size_t taille)
{
    unsigned char tmp[taille];
    memcpy(tmp, a, taille);
    memcpy(a, b, taille);
    memcpy(b, tmp, taille);
}
int main(void)
{
    int x = 5;
    int y = 9;
    echanger(&x, &y, sizeof(double));
    printf("%d %d\n", x, y);
    return 0;
}

Sortie d’erreur :

*** stack smashing detected ***: terminated

Fin du processus : signal SIGABRT (Aborted)

Sortie d’erreur avec AddressSanitizer :

==PID==ERROR: AddressSanitizer: stack-buffer-overflow on address 0x7ffff5400034
READ of size 8 at 0x7ffff5400034 thread T0
    #0 0x7ffff78fb42d in memcpy sanitizer_common_interceptors_memintrinsics.inc:115
    #1 0x5555555553ad in echanger s7_typage.c:6
...
Address 0x7ffff5400034 is located in stack of thread T0 at offset 52 in frame
    #0 0x55555555542e in main s7_typage.c:11
...
SUMMARY: AddressSanitizer: stack-buffer-overflow sanitizer_common_interceptors_memintrinsics.inc:115 in memcpy

sizeof(double) vaut 8, alors que x et y sont des int de 4 octets : memcpy lit et écrit 4 octets de trop, autour de chaque variable. gcc ne signale rien : les types void * et size_t sont respectés. À l’exécution, c’est un comportement indéfini ; ici l’écriture atteint le canari que gcc place dans la pile pour détecter les débordements, et la glibc arrête le processus (SIGABRT). AddressSanitizer nomme l’erreur à sa première lecture : 8 octets lus par memcpy depuis la ligne 6, dans une variable de 4 octets du stack frame de main.

Un appel par un type incompatible

C17 6.3.2.3 §8 et 6.5.2.2 §9

Un pointeur vers une fonction d’un type peut être converti en un pointeur vers une fonction d’un autre type, puis reconverti : le résultat est égal au pointeur d’origine. Si un pointeur converti sert à appeler une fonction dont le type n’est pas compatible avec le type pointé, le comportement est indéfini. De même, un appel par une expression dont le type n’est pas compatible avec celui de la fonction définie est un comportement indéfini (6.5.2.2 §9).

typedef int (*Cmp)(const void *, const void *);
double moyenne(double a, double b)
{
    return (a + b) / 2;
}
int main(void)
{
    int (*f)(int, int) = (int (*)(int, int))moyenne;
    printf("%d\n", f(12, 16));   /* indefini */
    const char *v[3] = {"Thies", "Dakar", "Louga"};
    qsort(v, 3, sizeof v[0], (Cmp)strcmp);
    printf("%s %s %s\n", v[0], v[1], v[2]);
    return 0;
}

Compilateur :

s7_incompatible.c:11:26: warning: cast between incompatible function types from 'double (*)(double,  double)' to 'int (*)(int,  int)' [-Wcast-function-type]

Sortie :

1431654793
Thies Dakar Louga

moyenne reçoit deux double. Appelée par un pointeur de type int (*)(int, int), elle reçoit les deux int dans les registres %edi et %esi, alors qu’elle lit ses paramètres dans %xmm0 et %xmm1 (convention d’appel System V) ; elle rend son résultat dans %xmm0, et l’appelant lit %eax. La valeur affichée, 1431654793 dans cette exécution, soit 0x55555189, est sans rapport avec 14 : ce sont les 32 bits bas de l’adresse de moyenne (0x555555555189), restés dans %eax ; un autre compilateur, ou une autre option, donnerait autre chose. gcc signale le cast (-Wcast-function-type, inclus dans -Wextra).

Le cast de strcmp en comparateur, lui, passe sans avertissement : gcc considère tous les types pointeurs comme équivalents pour ce contrôle. Or qsort passe au comparateur les adresses des éléments, des char ** ; strcmp les lit comme des chaînes et compare les octets des adresses, à commencer par celui de poids faible ; les trois littéraux sont rangés dans l’ordre du source, à des adresses croissantes, et l’ordre initial est conservé : le tableau reste dans le désordre alphabétique. C’est aussi un comportement indéfini (const char * et const void * ne sont pas des types compatibles), même quand il paraît fonctionner. Le comparateur correct est par_nom, avec const char *const *.

Exercices corrigés

Les trois exercices reprennent les raisonnements de la séance : lire et écrire des types de pointeurs de fonctions ; suivre les appels d’un comparateur pendant un tri ; lire un tableau dynamique générique dans un dump.

Exercice 1 : lecture et écriture de déclarations

char *f(const char *);
char (*g)(const char *);
double (*t[3])(double);
int (*(*h)(int))(int, int);
typedef int (*Operation)(int, int);

Lire f et g.
Lire t, puis donner le type de t[2].
Lire h.
Déclarer p, pointeur vers fonction (const void *, const void *) rendant int ; puis menu, tableau de 4 pointeurs vers fonction (void) rendant void.
Réécrire la déclaration de h avec Operation.
Si h désigne une fonction qui rend plus quel que soit son argument, que vaut h(0)(2, 3) ?

Correction

La méthode : partir du nom, lire à droite les () et les [], puis à gauche les *, sortir de chaque parenthèse et recommencer ; pour écrire, faire le trajet inverse, en partant du nom et en entourant de parenthèses chaque * qui doit s’appliquer avant un () ou un [].

(a) f : à droite (const char *), « fonction (const char *) », puis à gauche * et char : fonction (const char *) rendant char *. Il n’y a pas de parenthèse autour de *f : f n’est pas un pointeur. g : la parenthèse (*g) fait lire * d’abord : pointeur, puis à droite (const char *) : vers fonction (const char *), puis char : rendant char.

(b) t : à droite [3], tableau de 3 ; à gauche *, pointeurs ; on sort : à droite (double), vers fonction (double) ; à gauche double : rendant double. t[2] est un élément : double (*)(double), et t[2](9.0) appelle la fonction rangée dans la troisième case.

(c) h : (*h) : pointeur ; à droite (int) : vers fonction (int) ; à gauche * : rendant un pointeur ; on sort : à droite (int, int) : vers fonction (int, int) ; à gauche int : rendant int. En une phrase : h est un pointeur vers une fonction qui reçoit un int et rend un pointeur vers une fonction de deux int rendant int.

(d) Le nom, puis « pointeur » : (*p) ; « vers fonction (const void *, const void *) » à droite ; « rendant int » à gauche : int (*p)(const void *, const void *);, le type du comparateur de qsort. Pour menu : « tableau de 4 » menu[4], « pointeurs » (*menu[4]), « vers fonction (void) rendant void » : void (*menu[4])(void);. Sans les parenthèses, void *menu[4](void) déclarerait un tableau de fonctions, ce qui n’existe pas en C.

(e) Operation remplace « pointeur vers fonction (int, int) rendant int », la partie extérieure : Operation (*h)(int);.

(f) h(0) appelle la fonction désignée par h avec 0, et rend plus ; h(0)(2, 3) appelle plus avec 2 et 3 : 5. Les deux appels se lisent de gauche à droite, comme t[i][j].

Erreur fréquente. Oublier les parenthèses de (*p) : int *p(const void *, const void *); déclare une fonction qui rend un int *, et l’affectation p = cmp_int est refusée. Autre erreur : lire h de gauche à droite, « int pointeur pointeur », sans tenir compte des parenthèses.

Exercice 2 : la trace d’un `qsort`

On trie int t[6] = {31, 12, 27, 5, 19, 8}; par qsort(t, 6, sizeof t[0], cmp_trace);, avec le comparateur cmp_trace de la section Section 5, qui affiche (x,y) à chaque appel. La bibliothèque est la glibc 2.39, qui trie par fusion (moitié gauche de $\lfloor n/2\rfloor$ éléments).

Découper le tableau : les deux moitiés, puis leurs parties, jusqu’aux tableaux d’un élément.
Donner les appels (x,y), dans l’ordre, et l’état de chaque partie après sa fusion.
Combien d’appels au comparateur ? Que devient le tableau ?
Le tri par insertion de la section Section 6, avec le même comparateur, fait 14 appels. Expliquer ce nombre.
On remplace cmp_trace par un comparateur qui rend x - y. Les appels et le résultat changent-ils pour ce tableau ? Pourquoi ce comparateur reste-t-il à proscrire ?

Correction

La méthode : dessiner l’arbre des découpages ; trier les feuilles, puis fusionner de bas en haut ; pendant une fusion, comparer les têtes des deux parties, sortir la plus petite, et s’arrêter de comparer dès qu’une partie est vide (le reste de l’autre est recopié sans comparaison).

(a) $n=6$ : [31 12 27] et [5 19 8]. Chacune, $n=3$ : [31] et [12 27] ; [5] et [19 8]. [12 27] et [19 8] se coupent en tableaux d’un élément.

(b) Les fusions, dans l’ordre où la glibc les exécute :

fusion	appels	résultat
`[12]` et `[27]`	`(12,27)`	`[12 27]`
`[31]` et `[12 27]`	`(31,12) (31,27)`	`[12 27 31]`
`[19]` et `[8]`	`(19,8)`	`[8 19]`
`[5]` et `[8 19]`	`(5,8)`	`[5 8 19]`
`[12 27 31]` et `[5 8 19]`	`(12,5) (12,8) (12,19) (27,19)`	`[5 8 12 19 27 31]`

Dans la dernière fusion, 5, 8, puis 12, puis 19 sortent ; la partie de droite est alors vide, et 27 et 31 sont recopiés sans comparaison. De même, dans la fusion de [5] et [8 19], 5 sort et 8, 19 suivent sans comparaison.

(c) $1+2+1+1+4=9$ appels ; le tableau devient 5 8 12 19 27 31. L’exécution affiche (12,27) (31,12) (31,27) (19,8) (5,8) (12,5) (12,8) (12,19) (27,19).

(d) L’insertion prend chaque élément, de gauche à droite, et le compare à ceux qui le précèdent jusqu’à trouver sa place : 12 face à 31 (1 comparaison) ; 27 face à 31 puis 12 (2) ; 5 face à 31, 27, 12, et il arrive en tête (3) ; 19 face à 31, 27, 12 (3) ; 8 face à 31, 27, 19, 12, 5 (5). Soit $1+2+3+3+5=14$. Au pire, l’insertion fait $n(n-1)/2$ comparaisons ; la fusion en fait au plus de l’ordre de $n\log_2 n$, d’où l’écart, qui grandit avec $n$.

(e) Pour ce tableau, x - y a toujours le signe de la comparaison (les différences sont petites) : les mêmes 9 appels, le même résultat, ce que confirme l’exécution. Le comparateur reste faux : pour des valeurs dont la différence dépasse INT_MAX, le débordement est un comportement indéfini et l’ordre est perdu (section Section 5).

Erreur fréquente. Compter une comparaison pour chaque élément recopié à la fin d’une fusion : dès qu’une partie est vide, le reste de l’autre est recopié sans appel. Autre erreur : supposer que qsort est un tri rapide (quicksort) ; la norme ne l’impose pas, et la glibc 2.39 trie par fusion.

Exercice 3 : un tableau générique dans un dump

Un VecteurG v a été créé par vg_init(&v, sizeof(Releve), 2), où Releve est struct { short annee; char region[6]; }, puis a reçu trois vg_ajouter. La structure est recopiée en 0x00 ; son bloc, précédé des 8 octets de l’en-tête de la glibc, en 0x40 (adresses abrégées : donnees y est écrit 0x40).

Addr	+0	+1	+2	+3	+4	+5	+6	+7
`0x00`	`40`	`00`	`00`	`00`	`00`	`00`	`00`	`00`
`0x08`	`03`	`00`	`00`	`00`	`00`	`00`	`00`	`00`
`0x10`	`04`	`00`	`00`	`00`	`00`	`00`	`00`	`00`
`0x18`	`08`	`00`	`00`	`00`	`00`	`00`	`00`	`00`

Addr	+0	+1	+2	+3	+4	+5	+6	+7
`0x38`	`31`	`00`	`00`	`00`	`00`	`00`	`00`	`00`
`0x40`	`e3`	`07`	`54`	`68`	`69`	`65`	`73`	`00`
`0x48`	`e5`	`07`	`4c`	`6f`	`75`	`67`	`61`	`00`
`0x50`	`e8`	`07`	`4d`	`62`	`6f`	`75`	`72`	`00`
`0x58`	`41`	`fd`	`01`	`00`	`00`	`00`	`00`	`00`

Donner v.donnees, v.taille, v.capacite et v.taille_elem. Vérifier sizeof(Releve).
Lire l’en-tête : taille du bloc, octets utiles, nombre de places.
Lire les trois éléments.
Que rend vg_elem(&v, 2) ? Et vg_elem(&v, 3) ? Que contiennent les octets 0x58 à 0x5f ?
On ajoute un quatrième élément, puis un cinquième. Où chacun est-il copié, et avec quel appel à realloc ?
Que vaut v après vg_liberer(&v, NULL) ?

Correction

La méthode : (1) découper la structure en quatre champs de 8 octets, en little-endian ; (2) lire l’en-tête 8 octets avant les données ; (3) découper les données en éléments de taille_elem octets, l’élément $i$ commençant en $\texttt{donnees}+i\times\texttt{taille\_elem}$ ; (4) dans chaque élément, appliquer la disposition de la structure.

(a) Ligne 0x00 : donnees $=$ 0x40. Ligne 0x08 : taille $=$ 3. Ligne 0x10 : capacite $=$ 4. Ligne 0x18 : taille_elem $=$ 8. Releve mesure bien 8 octets : un short (2 octets, alignement 2) puis 6 char, sans padding. La capacité initiale était 2 : le troisième ajout a trouvé le bloc plein et l’a doublée.

(b) En 0x38 : 0x31 ; sans le bit 0, un bloc de 48 octets, en-tête compris : 40 octets utiles, soit 5 places de 8, dont 4 sont à v (32 octets demandés par le realloc du troisième ajout).

(c) Élément 0, en 0x40 : e3 07 $=$ 0x07e3 $=$ 2019, puis 54 68 69 65 73 00, « Thies » et son terminateur. Élément 1, en 0x48 : e5 07 $=$ 2021, « Louga ». Élément 2, en 0x50 : e8 07 $=$ 2024, « Mbour ». vg_ajouter a copié ces 8 octets tels quels, sans connaître la structure.

(d) $\texttt{0x40}+2\times8=\texttt{0x50}$, l’adresse du troisième élément, rendue en void *. vg_elem(&v, 3) rend 0x58 : une adresse calculée sans contrôle, celle de la quatrième place, qui ne contient aucun élément (taille vaut 3). Ses octets, 41 fd 01 00 …, sont ce qui restait à cet endroit du tas ; ils n’ont pas de sens pour le programme. vg_elem ne vérifie pas l’indice : c’est à l’appelant de respecter i < taille.

(e) Le quatrième élément trouve taille (3) $<$ capacite (4) : il est copié en 0x58, sans realloc, et taille passe à 4. Le cinquième trouve le bloc plein : realloc reçoit $2\times4\times8=64$ octets, la capacité passe à 8, puis l’élément est copié à $\texttt{donnees}+4\times8$ dans le bloc obtenu, qui peut avoir changé d’adresse.

(f) vg_liberer n’appelle aucune fonction (lib vaut NULL), libère le bloc, puis remet la structure à {NULL, 0, 0, 8} : taille_elem est conservée, ce que confirme l’exécution.

Addr	+0	+1	+2	+3	+4	+5	+6	+7
`0x00`	`40`	`00`	`00`	`00`	`00`	`00`	`00`	`00`
`0x08`	`03`	`00`	`00`	`00`	`00`	`00`	`00`	`00`
`0x10`	`04`	`00`	`00`	`00`	`00`	`00`	`00`	`00`
`0x18`	`08`	`00`	`00`	`00`	`00`	`00`	`00`	`00`

Addr	+0	+1	+2	+3	+4	+5	+6	+7
`0x38`	`31`	`00`	`00`	`00`	`00`	`00`	`00`	`00`
`0x40`	`e3`	`07`	`54`	`68`	`69`	`65`	`73`	`00`
`0x48`	`e5`	`07`	`4c`	`6f`	`75`	`67`	`61`	`00`
`0x50`	`e8`	`07`	`4d`	`62`	`6f`	`75`	`72`	`00`
`0x58`	`41`	`fd`	`01`	`00`	`00`	`00`	`00`	`00`

Dans les dumps corrigés, donnees est en orange, taille en bleu, capacite en violet, taille_elem et l’en-tête en gris ; dans chaque élément, l’année est en bleu et la région en vert ; la place libre est en jaune.

Erreur fréquente. Compter les éléments avec la capacité, ou avec la taille du bloc (5 places de 8) : seule taille dit combien d’éléments sont rangés. Autre erreur : lire e3 07 comme 0xe307 ; la machine est little-endian, l’octet de poids faible vient en premier.

À retenir

Le nom d’une fonction désigne l’adresse de son code, dans le segment de code (.text) ; un pointeur de fonction est une donnée de 8 octets qui garde cette adresse. Dans un exécutable PIE, adresse $=$ base $+$ décalage (nm).
Un type de pointeur de fonction se lit à partir du nom, à droite puis à gauche : int (*f)(int) ; les parenthèses autour de *f sont indispensables. typedef nomme le type et rend lisibles les déclarations imbriquées.
f(x) par un pointeur est un appel indirect (call *%rax) ; une table de dispatch remplace une suite de tests, et s’étend sans modifier le code qui appelle. gcc produit une table de sauts pour un switch dense.
Une fonction de rappel transmet un traitement à du code écrit sans le connaître ; un void *ctx lui apporte un contexte.
Un comparateur rend un signe, en comparant ((x > y) - (x < y)), jamais en soustrayant ; bsearch exige un tableau trié selon le même ordre, et son comparateur reçoit la clé en premier.
La généricité du C tient en trois éléments : void *, une taille en octets, des fonctions qui connaissent le type ; les adresses se calculent en char *, les copies par memcpy. Un conteneur générique reçoit aussi la fonction qui libère ce que possèdent ses éléments.
Le compilateur ne vérifie plus ni les tailles ni les types ; appeler une fonction par un pointeur de type incompatible est un comportement indéfini (C17 6.3.2.3 §8, 6.5.2.2 §9).

Synthèse du cours

Le cours a lu chaque programme comme des octets rangés à des adresses, et chaque séance a ajouté un niveau de lecture.

séance	ce qui se voit en mémoire
1. Syntaxe C complète (fondamentaux)	types, opérateurs, contrôle, fonctions, compilation, comportement indéfini
2. Représentation numérique	entiers non signés et en complément à deux, débordements, IEEE 754
3. Organisation de la mémoire	mot machine, adresses, endianness, pointeurs, tableaux, chaînes, pile et tas
4. Structures et unions	champs, alignement, padding, unions, champs de bits
5. Allocation dynamique et structures chaînées	propriété, tableau dynamique, listes, piles, files, erreurs du tas, intérieur de `malloc`
6. Pointeurs de fonctions et généricité	segment de code, appel indirect, rappels, `qsort`, conteneurs génériques

La méthode est restée la même : lire un dump, dessiner la pile et le tas, relever les octets avec show_bytes ou gdb ; compiler avec -std=c17 -Wall -Wextra -O0 -g et lire chaque avertissement ; observer avec gdb, nm et objdump ; vérifier avec valgrind et AddressSanitizer ; distinguer ce que la norme garantit de ce qu’une plateforme fait un jour donné. Le cours de structures de données et d’algorithmes repart de là, en Java.

Références

R. E. Bryant, D. R. O’Hallaron — Computer Systems: A Programmer’s Perspective, 3^e éd., Pearson, 2016 (§ 3.6.8 : switch et tables de sauts ; § 3.7 : procédures et call ; § 7.12 : code indépendant de la position).
B. W. Kernighan, D. M. Ritchie — The C Programming Language, 2^e éd., Prentice Hall, 1988 (§ 5.11 : pointeurs de fonctions ; § 5.12 : déclarations complexes).
K. N. King — C Programming: A Modern Approach, 2^e éd., Norton, 2008 (§ 17.7 : pointeurs de fonctions, qsort ; § 18.4 : déclarateurs complexes).
R. C. Seacord — Effective C, 2^e éd., No Starch Press, 2024 (chap. 2 : types, pointeurs de fonctions ; chap. 5 : instructions de contrôle, switch).
ISO/IEC 9899:2018 (C17) : 6.3.2.1 §4 (désignateur de fonction), 6.3.2.3 §8 (conversion de pointeurs de fonctions), 6.5.2.2 (appel de fonction), 6.7.6.3 (déclarateurs de fonctions), 7.22.5 (qsort, bsearch).

Une fonction en mémoire

L’adresse d’une fonction

Le code d’une fonction, sous gdb

Exemple pas à pas : un pointeur de fonction

Lecture et écriture des types

Lecture d’une déclaration

Nom du type : typedef

Appel indirect et table de dispatch

f, *f et **f : un même appel indirect

Exemple pas à pas : une table de dispatch

Un menu de commandes

Un automate par table

Le switch et sa table de sauts

Fonctions de rappel

Fonction passée en paramètre

Le flux d’un rappel

Un contexte en void *

qsort et bsearch

Le contrat du comparateur

Tri des étudiants par moyenne puis par nom

Les appels au comparateur

Deux pièges

bsearch dans un catalogue

Généricité

Exemple pas à pas : un échange générique

Un tri générique

Exemple pas à pas : le Vecteur générique

Des éléments qui possèdent un bloc

Une liste générique

Limites

La perte du typage

Un appel par un type incompatible

Exercices corrigés

Exercice 1 : lecture et écriture de déclarations

Exercice 2 : la trace d’un qsort

Exercice 3 : un tableau générique dans un dump

À retenir

Synthèse du cours

Références

Pour cette séance

Nom du type : `typedef`

`f`, `*f` et `**f` : un même appel indirect

Le `switch` et sa table de sauts

Un contexte en `void *`

`qsort` et `bsearch`

`bsearch` dans un catalogue

Exemple pas à pas : le `Vecteur` générique

Exercice 2 : la trace d’un `qsort`