La programmation générique en C

Bonjour à toutes et à tous,

Il y a peu a été publié sur Zeste de Savoir mon premier tutoriel ! J’espère que ce n’est que le premier d’une longue série, puisque je travaille en ce moment à l’écriture d’un énorme cours sur les paradigmes de programmation, qui je l’espère verra le jour dans le courant de l’année à venir.

Mais, pour l’heure, j’aimerais présenter un complément d’information au tutoriel et parler plus en détail de la programmation générique en C.

Contexte

Dans le cours, je présente les arbres binaires de recherche, une structure de données récursives visant à améliorer les performances des listes. Afin de mettre en application la théorie présentée, j’ai choisi de réaliser une implémentation en C, implémentation que vous pouvez retrouver sur mon GitHub. Pourquoi en C, me demanderez-vous. Eh bien, il y a deux raisons majeures à mon choix :

  • La première, très subjective, je dois bien l’avouer, est le langage avec lequel je me sens le plus à l’aise. Je l’utilise depuis déjà bien des années et je commence à en connaître un rayon à son propos. De ce fait, j’étais sûr de ne pas écrire de bêtises et de présenter un code propre et bien pensé pour ma première publication sur Zeste de Savoir.
  • Utiliser un langage de bas niveau me paraissait judicieux dans le sens où il m’a permis d’évoquer dans le cours pas mal de détails techniques (allocations mémoire, programmation générique, gestion des types…) que certains langages de plus haut niveau auraient rendus transparents.

Peu importe le langage utilisé pour réaliser cette bibliothèque, les structures de données se doivent d’être programmées de manière générique.

Qu’est-ce que cela signifie, quelles implications cela a-t-il pour un langage comme C, quels outils utiliser sont autant de questions que je vais tâcher de traiter dans ce billet ! 🙂

Programmation « générique »

Entrons dans le vif du sujet si vous le voulez bien. Qu’appelle-t-on exactement la programmation générique ? D’après notre très cher ami Wikipedia,

En programmation, la généricité (ou programmation générique), consiste à définir des algorithmes identiques opérant sur des données de types différents.

Rapportée au cadre des arbres binaires de recherche, cela signifie que les fonctions créées pour manipuler la structure de données doit fonctionner quelque soit le type de données stockées. Dans la plupart des langages modernes, ce genre de problématique a été étudié et des mécanismes sont prévus spécialement pour ça : les templates en C++, les génériques en Java, les modules paramétrés en OCaml, etc…

Prenons un petit exemple avec C++, si vous le voulez bien. Il existe en C++ une classe dans la bibliothèque standard appelée vector, utilisée pour décrire les tableaux dynamiques. Ainsi, pour déclarer un  vector d’entiers, par exemple, on peut écrire

std::vector<int> tab;

La mention <int>, apposée au type, spécifie que vector est en réalité un template de classe, que l’on va utiliser dans ce cas précis avec des entiers, mais que l’on peut utiliser de la même manière avec n’importe quel type, d’où la notion de programmation générique.

Malheureusement, en C, ce n’est pas aussi simple que ça. Il existe des mécanismes permettant de mettre en œuvre une forme de programmation générique, mais vous allez vite vous rendre compte que ça demande bien plus de rigueur et de compréhension du bas niveau que les templates de C++.

Les armes de C

A la place d’un mécanisme spécialement conçu pour la programmation générique, C dispose de plusieurs outils qui, une fois bien compris et bien utilisés, peuvent produire du code générique. Je vais tâcher de vous présenter ces outils, en utilisant en guise d’exemple la bibliothèque d’arbres binaires de recherche que j’ai écrite.

Les pointeurs void*

C est un langage typé statiquement, ce qui signifie que le type de toutes les variables doit être connu au moment de la compilation. C’est vrai pour les variables, mais également pour les pointeurs : bien que tous les pointeurs désignent une adresse mémoire, un pointeur sur entier (int*) sera différent d’un pointeur sur un nombre à virgule flottante (float*), puisque le type du pointeur définit le type de la variable sur laquelle le pointeur pointe. Ainsi, le bout de code suivant produira un warning.

int i = 2;
float* p = &i; //< Initialization from incompatible pointer type

Plutôt embêtant, si on veut faire de la programmation générique. Cependant, il existe en C un type de pointeur qui échappe à cette règle : le type (void*). En bon français, on parle de pointeur générique (coïncidence ?), mais, pour faire court, on peut tout aussi bien parler de pointeur sur n’importe quoi. Lorsque l’on déclare un (void*), on peut y stocker l’adresse de n’importe quoi. La contrepartie, c’est que comme le compilateur n’a pas la moindre idée du type de la donnée pointée, il est impossible de déréférencer un (void*) sans le caster.

Vous vous en doutez bien, les pointeurs (void*) vont être la panacée de la programmation générique en C. Et, si vous jetez un œil à mon implémentation des arbres binaires de recherche, ça ne loupe pas :

typedef struct _bst_node {
  void* data; /**< The node's data */
struct _bst_node* left; /**< The node's left sub-tree */
struct _bst_node* right; /**< The node's right sub-tree */
} bst_node;

Le membre data de la structure est un (void*), ce qui va nous permettre de le faire pointer sur n’importe quel type de données !

L’allocation dynamique

Bon, on a trouvé une solution pour stocker des pointeurs génériques, mais il va également falloir s’occuper de la gestion de la mémoire en elle-même. Et je vais aborder ce point en commençant par la principale problématique qui se pose ici. Comment va-t-on gérer l’espace alors que tout ce que l’on sait sur la donnée est un pointeur générique ?

La première chose que l’on peut remarquer, c’est que le compilateur va être incapable de faire ça lui-même : comme il ne sait pas ce qui se cache derrière un pointeur (void*), l’allocation automatique ne fonctionnera pas. Nous allons donc utiliser l’allocation dynamique et la fameuse fonction (malloc()). Pour gérer la taille des espaces demandés à (malloc()), il faut prévoir un mécanisme pour que l’utilisateur du code générique le renseigne. Appliqué à nos arbres binaires de recherche, voici ce que cela donne :

typedef struct {
  size_t data_size; /**< Size of an element */
bst_node* root; /**< Root of the bst */
orderFun compare; /**< Binary relation of the tree dataset */
freeFun free; /**< Dynamic deallocation of tree data */
} bst;

Le membre (data_size) contient la taille d’un élément, d’où son type (size_t). Et, pour être sûr qu’il soit correctement initialisé, j’ai également écrit une fonction de création qui demande en argument ladite taille et vérifie sa cohérence.

bst* bst_new(size_t data_size, orderFun compare, freeFun free_fun) {
  assert(data_size > 0);
// ...
}

Une fois la taille des données correctement réglée, on peut s’en servir comme bon nous semble avec (malloc()). Ensuite, une fois la mémoire allouée, on peut copier la donnée peu importe son type avec (memcpy()). Un exemple avec la fonction me permettant de créer un nouveau nœud et d’y copier la donnée dont l’adresse est fournie en paramètre :

static bst_node* bst_create_node(int data_size, void* element) {
  bst_node* node = malloc(sizeof(bst_node)); // Allocating a node
if(!node) { // Checking allocation
perror("malloc");
exit(EXIT_FAILURE);
}
node->data = malloc(data_size); // Allocating data
if(!(node->data)) {
perror("malloc");
exit(EXIT_FAILURE);
}
  memcpy(node->data, element, data_size); // Setting data
node->left = NULL;
node->right = NULL;

return node;
}

Une petite remarque : vérifiez toujours le résultat d’une allocation manuelle. En effet, d’après la documentation de la fonction (malloc()), si l’allocation échoue pour une raison ou pour une autre (la cause la plus courante étant la saturation de la RAM), l’allocation manuelle renverra (NULL). Si vous ne testez pas la valeur de retour, vous risquez de manipuler un pointeur incohérent, et je peux vous garantir qu’en général, il ne se passe pas bien longtemps avant que le programme ne plante pour de bon. Donc un petit test, et si quelque chose s’était mal passé, on coupe tout avec un message d’erreur qui va bien.

Les pointeurs de fonction

Nous sommes désormais en mesure d’utiliser des pointeurs génériques et en plus de cela gérer correctement la mémoire peu importe le type de données fourni. Cependant, il va nous rester un dernier obstacle à surmonter : comment manipuler les données stockées si on ne connaît pas leur type ?

Une nouvelle fois, la réponse est simple : on ne le fait pas nous-même, on demande à l’utilisateur. En revanche, il va être de notre responsabilité de « préparer le terrain » pour cette opération. Reprenons nos arbres binaires, si vous le voulez bien. Si vous avez lu l’article, vous aurez compris que pour fonctionner, l’arbre doit être capable de déterminer si un élément est plus grand qu’un autre. Mais, comme on ne connaît pas a priori la structure de la donnée, on ne sait pas comment les comparer. La solution consiste à demander à l’utilisateur une fonction pour faire la comparaison.

Pour ce faire, nous allons utiliser un outil de C rarement abordé dans les cours que j’ai pu lire : les pointeurs de fonction. Un pointeur de fonction est un type très particulier puisque, comme son nom l’indique, il ne pointe pas sur une variable, mais sur une fonction. Au final, quand on y réfléchit, tous les pointeurs sont en fait une adresse mémoire, peu importe sur quoi ils pointent : les pointeurs « classiques » sur un espace mémoire réservé aux variables, les pointeurs de fonction sur un espace mémoire réservé au code. Malgré tout, je vais me permettre d’attirer votre attention sur un point de détail : dans le cas des pointeurs classiques, on connaît le type de la variable pointée ((int*) pointe sur un entier, (float*) sur un nombre à virgule flottante. D’où ma question : existe-t-il en C un « type » réservé aux fonctions ?

En réalité, c’est un peu plus compliqué que cela. Quand on veut définir un pointeur sur une fonction, on doit en donner la signature. Pour rappel, la signature d’une fonction désigne le type de la valeur de retour et le type de ses arguments. Ainsi, pour en revenir aux arbres binaires, la structure doit contenir un pointeur sur une fonction renvoyant un entier et prenant en argument deux (void*) : la fonction doit retourner un nombre positif si le premier argument est plus grand et un nombre négatif si c’est le deuxième. Encore une fois, comme on ne connaît pas le type des données, on se contente de fournir un pointeur générique, et il sera à la charge de l’utilisateur de caster ce pointeur dans le type de son choix. Du pointe de vue de la syntaxe, voici ce que ça donne :

typedef int (*orderFun)(void *, void *);

Ici, on utilise un (typedef) pour définir un type (orderFun) désignant un pointeur sur une fonction renvoyant un entier et prenant en argument deux (void*). Ensuite, dans la définition de la structure, on écrit la chose suivante :

typedef struct {
size_t data_size; /**< Size of an element */
bst_node* root; /**< Root of the bst */
orderFun compare; /**< Binary relation of the tree dataset */
freeFun free; /**< Dynamic deallocation of tree data */
} bst;

Enfin, pour affecter une valeur à ce pointeur, on doit donner le nom d’une fonction respectant la signature du pointeur, sans mettre de parenthèses. Pourquoi ? Parce que mettre des parenthèses signifie que l’on réalise un appel à la fonction, alors qu’ici, on ne veut que son adresse.

Conclusion

Voilà, ça sera tout pour ce rapide tour d’horizon des outils que propose C pour mettre en œuvre des programmes génériques. Si vous voulez en savoir plus, n’hésitez pas à lire le cours que j’ai écrit pour Zeste de Savoir si ce n’est pas déjà fait, car il vous permettra de voir une application des techniques que j’ai présentées ici. N’hésitez pas également pour aller plus loin à récupérer ma bibliothèque sur GitHub et à réaliser quelques exemples d’utilisation des arbres binaires pour manipuler une bibliothèque générique.

Enfin, si vous voulez vraiment maîtriser le sujet, rien de mieux que la pratique, et pour cela, quelques exercices. Pourquoi ne pas recréer vous même quelques bibliothèques génériques ? Les structures de données se prêtent merveilleusement bien à la programmation générique ! Listes chaînées,  listes doublement chaînées, piles, files, et arbres en tous genres sont tous censés être des structures de données génériques.

Surtout, n’hésitez pas à publier vos résultats dans les commentaires afin de partager vos travaux. Bien sûr, si vous avez des questions quant à ce que je viens de présenter, je vous invite à poser vos questions, je serai très heureux d’y répondre !

Allez à très bientôt, en espérant que je publie plus fréquemment en 2016 qu’en 2015 ! 😀

3 réponses sur “La programmation générique en C”

  1. Sinon, il y a toujours la possibilité de faire de la métaprogrammation à coup de macro. Ça permet de se passer du pointeur sur void, mais ça rend le debug un peu plus… tricky.

Laisser un commentaire

Votre adresse de messagerie ne sera pas publiée. Les champs obligatoires sont indiqués avec *