La généricité en langage C

Romuald Perrot

Ce tutoriel vous présente comment intégrer la généricité dans vos projets en C.

Votre avis et vos suggestions sur ce tutoriel m'intéressent ! Alors après votre lecture, n'hésitez pas : Commentez

- Titre : La généricité en langage C

- Auteur : Romuald Perrot

- Parution : 8 août 2006

- Mise à jour : 29 septembre 2006

- Licence : Copyright ® 2006 . Aucune reproduction, même partielle, ne peut être faite de ce site et de l'ensemble de son contenu : textes, documents, images, etc. sans l'autorisation expresse de l'auteur. Sinon vous encourez selon la loi jusqu'à trois ans de prison et jusqu'à 300 000 € de dommages et intérêts.

Sommaire

- I. Introduction

- II. Le pointeur générique

- II-A. Premiers pas avec le pointeur générique

- II-B. Les limites du pointeur générique

- III. Parcours de tableaux génériques

- IV. Remerciements

I - Introduction

La généricité en C, comme dans d'autres langages, permet d'effectuer des actions, sur un ensemble de données de manière générique, c'est-à-dire quelque soit son type. On peut donc, à l'instar des patrons de fonctions du C++, réaliser des traitements qui pourront s'appliquer sur des types entiers comme des types réels, pourvu que le type qui sera utilisé lors de l'appel de fonction supporte les opérations utilisées par la fonction générique.

II - Le pointeur générique

Le langage C dispose d'un pointeur particulier appelé pointeur générique qui est un pointeur compatible avec tous les autres pointeurs, c'est-à-dire que ce pointeur est à même de pointer vers n'importe quel type d'objet. Ce pointeur est le pointeur void *. Il faut faire attention car ce n'est pas un pointeur vers un objet de type void mais bien un type à part entière. D'ailleurs au passage, un pointeur vers un type void n'a pas de sens puisque le type void n'est pas un type qui doit contenir quelque chose, il est là pour indiquer une absence de type.

II-A - Premiers pas avec le pointeur générique

Vous avez sûrement déjà rencontré le pointeur générique, notamment lors d'allocations mémoire. En effet, la fonction malloc a pour signature :

void * malloc( size_t size)

La fonction renvoie un pointeur générique. Ceci est tout à fait normal puisque la fonction ne sait pas quel doit être le type de retour, ce qui lui importe, c'est la taille à allouer. Ne connaissant pas la taille du type à allouer, elle doit donc renvoyer un pointeur vers n'importe quel type d'objet, il s'agit donc du pointeur générique. Comme le pointeur est générique, il doit pouvoir être affecté sans problème. De plus, on doit pouvoir lui affecter un pointeur sur un type donné. L'exemple suivant montre l'utilisation possible d'un pointeur générique pour afficher l'adresse d'une variable :

#include <stdio.h>
#include <stdlib.h>
int main ( void )
{
void * ptr = NULL;
int a = 2;
ptr = &a;
printf("%p\n",ptr);
return EXIT_SUCCESS;
}

Ici, le pointeur générique remplace donc un pointeur sur un entier.

II-B - Les limites du pointeur générique

Supposons que nous voulions une fonction qui échange deux éléments quels qu'en soient leurs types (il faut au moins que les deux élements soient du même type). A première vue, nous pourrions penser à une fonction utilisant des pointeurs génériques comme ceci :

void swap( void * a , void * b)
{
void * tmp;
tmp = a;
a = b;
b = tmp;
}

Supposons que nous effectuons le petit test suivant :

int a = 3;
int b = 2;
swap( &a, &b );
printf( "a = %d , b = %d" , a , b );

Nous aurions en sortie ceci :

a = 3 , b = 2

Ceci est tout à fait prévisible et nous avons été un peu vite en besogne pour l'écriture de notre fonction d'échange. En effet, il faut toujours avoir à l'esprit que la langage C effectue ce qu'on appelle du passage par copie. Ceci signifie donc que les arguments que l'on passe à une fonction sont copiés. Ainsi, pour notre fonction, ce ne sont pas les variables a et b que nous échangeons mais leur copie. Si vous avez déjà effectué une fonction qui doit échanger deux entiers, vous avez sûrement procédé ainsi :

void swap_int( int * a, int * b)
{
int tmp;
tmp = *a;
*a = *b;
*b = tmp;
}

Pourquoi ne pas faire la même chose avec notre fonction d'échange générique ? Et bien parce que nous ne le pouvons pas ! En effet, si nous échangeons vulgairement le type int par le type void, nous allons nous retrouver avec cette écriture :

void tmp = *a;

Or comme nous l'avons dit plus tôt, le type void ne permet pas de stocker quoi que se soit. De plus, l'opération de déréférencement de a provoquerait aussi une erreur. En effet, il n'est pas possible de déréférencer un pointeur générique. Ceci s'explique aussi par le fait que le pointeur générique ne sait pas vers quel type de variable son contenu pointe. Par conséquent, le déréférencer voudrait dire que l'on aurait une variable dont l'espace de stockage ne serait pas défini. Pour résoudre nos problèmes (passage par valeur et déréférencement impossible), il faut ruser et passer par un niveau de pointeur supérieur. Ainsi notre fonction d'échange correcte est celle ci :

void swap( void * d1 , void * d2 )
{
void * tmp;
tmp = *(void **)d1;
*(void **)d1 = *(void **)d2;
*(void **)d2 = tmp;
}

La fonction réalise un échange de pointeurs, d1 pointe vers ce qui était pointé par d2 et d2 pointe vers ce qui était pointé par d1. Cependant, cela ne résoud toujours pas notre problème. En effet nous n'échangeons que des pointeurs et pas le contenu des variables. Afin d'échanger correctement le contenu des variables, il faut concrètement copier l'espace mémoire qui se situe aux adresses données. Or comme les pointeurs génériques ne connaissent pas la taille occupée en mémoire des objets vers lesquels il pointe, il faut explicitement passer cette taille en paramètre de notre fonction d'échange. Finalement notre fonction d'échange générique est la suivante:

int swap (void *const a, void *const b, size_t size)
{
void *const temp = malloc(size);

if ( temp == NULL )
return EXIT_FAILURE;

memcpy(temp, a, size);
memcpy(a, b, size);
memcpy(b, temp, size);

free(temp);

return EXIT_SUCCESS;
}

Cette fonction va renvoyer la constante EXIT_SUCCESS si l'échange a pu avoir lieu, sinon, elle va renvoyer EXIT_FAILURE.

Il existe aussi un autre problème liée au pointeur générique, en effet, comme il est générique, il ne connaît pas l'espace mémoire des objets vers lesquels il pointe. Ceci entraîne donc un déréférencement impossible mais aussi des calculs d'adresses impossibles. Il ne sera donc pas possible d'effectuer des opérations de ce genre :

void * ptr;
/* ... On initialise ptr ... */
printf("%p", ptr + 1);

On ne peut pas le faire encore une fois parce que le pointeur générique ne connaît rien de ce vers quoi il pointe, y compris l'espace mémoire de la variable vers laquelle il pointe.

III - Parcours de tableaux génériques

On effectue souvent des parcours de tableaux de tous types, on peut donc se demander s'il n'est pas possible de réaliser une fonction qui puisse effectuer un parcours de tableau de manière générique. Comme toute fonction de parcours sur un tableau dynamique, nous devons passer à la fonction le nombre d'éléments à parcourir. Nous devons en plus de ce nombre passer la taille des éléments constituant le tableau. Nous avons vu que le pointeur générique ne permettait pas d'obtenir cette information, il faut donc la demander. Notre fonction aura donc pour signature :

void parcours( void * data , size_t nb_elt , size_t size);

Intuitivement, nous pourrions faire ceci :

void parcours( void * data , size_t nb_elt , size_t size )
{
size_t i;
for( i = 0 ; i < nb_elt ; ++i )
{
printf("%p\n", data + (i * size) );
}
}

Mais nous avons vu que le calcul d'adresse ne pouvait pas être effectué sur un pointeur générique, il faut donc passer par un autre pointeur. IL faut donc un pointeur sur une variable dont l'espace de stockage soit le byte, c'est à dire la plus petite unité adressable par un programme en langage C. Ce type est tout naturellement le type char. On pourra donc effectuer un transtypage du pointeur générique vers un pointeur de caractère, ainsi nous pourrons effectuer des calculs d'adresse, et donc se déplacer de i*size bytes pour pouvoir pointer vers la i-ème case du tableau que l'on veut parcourir. Ainsi notre fonction devient alors :

void parcours( void * data , size_t nb_elt , size_t size )
{
size_t i;
for( i = 0 ; i < nb_elt ; ++i )
{
printf("%p\n", ((char *)data) + (i * size) );
}
}

Afin de rendre plus lisible le code, il est préférable d'effectuer la conversion de type dès le début de la fonction.

void parcours( void * vdata , size_t nb_elt , size_t size )
{
size_t i;
char * data = vdata;
for( i = 0 ; i < nb_elt ; ++i )
{
printf("%p\n", data + (i * size) );
}
}

Ainsi on gagne en visibilité et le calcul d'adresse apparaît comme plus naturel. On notera également qu'à l'instar de ce qui est effectué avec la fonction malloc, il n'est pas nécessaire d'effectuer un transtypage explicite. Nous avons donc une fonction de parcours qui peut être utilisée sur n'importe quel type de tableau.

Pour augmenter la généricité, nous pouvons passer en paramètre de la fonction, un pointeur de fonction qui puisse réaliser des opérations sur le tableau. C'est exactement ce qui est fait avec la fonction qsort de la bibliothèque standard du C. Pour rappel sa signature est la suivante :

void qsort(void *base, size_t nmemb, size_t size,
int (*compar)(const void *, const void *));

L'exemple suivant montre comment utiliser un pointeur de fonction pour afficher les éléments d'un tableau :

#include <stdlib.h>
#include <stdio.h>
void affd(const void *pva)
{
const double *pa = pva;
printf("%f\n",*pa);
}

void affi(const void *pva)
{
const int *pa = pva;
printf("%d\n",*pa);
}

void parcours( void * pvdata , size_t nb_elt , size_t size , void (*fct)(const void*))
{
size_t i;
char *data = pvdata;
for( i = 0 ; i < nb_elt ; ++i )
{
fct(data+i*size);
}
}

int main( void )
{
int tabi[5] = {1,2,3,4,5};
double tabd[5] = {1.23,2.34,3.45,4.56,5.67};

parcours(tabi, sizeof(tabi)/sizeof(*tabi), sizeof(*tabi), affi);
parcours(tabd, sizeof(tabd)/sizeof(*tabd), sizeof(*tabd), affd);

return EXIT_SUCCESS;
}

Ainsi, avec la même fonction, nous pouvons afficher un tableau d'entiers comme un tableau de réels. On peut faire bien plus qu'afficher des variables de types atomiques, il suffit simplement de définir une fonction qui effectue l'affichage d'un objet et la passer en paramètre à la fonction parcours.

IV - Remerciements

Je tiens à remercier Miles, nico-pyright(c), fearyourself, pour les corrections et aides apportées à cet article.