Comment écrire des structures de données génériques et sûres en type en C

 (danielchasehooper.com)
3 points par GN⁺ 2025-07-01 | 2 commentaires | Partager sur WhatsApp
  • Cet article explique une nouvelle méthode pour créer des structures de données génériques et sûres en type en C
  • Il présente, à travers l’exemple d’une liste chaînée, une technique qui associe des informations de type à la structure de données à l’aide d’une union
  • Il compare les différences avec les modèles génériques C existants (macros, pointeurs void, Flexible Array Member) ainsi que les inconvénients de chaque approche
  • Le contrôle de type à la compilation permet d’empêcher à l’avance l’utilisation de types incorrects
  • Cette nouvelle technique fournit une interface de fonctions et de structures de données claire et cohérente, comme foo_list

Introduction

  • Présentation d’une méthode pour créer en C des structures de données génériques avec sécurité de type
  • Cette technique relie, à la compilation, les informations de type à la structure de données grâce à une union
  • Elle peut s’appliquer à toutes sortes de structures de données, comme les maps, tableaux, arbres binaires, etc., et l’explication s’appuie sur l’implémentation d’une liste chaînée simple
  • Comme beaucoup de développeurs pensent que les génériques sont impossibles en C, l’article propose une explication simple, étape par étape

Les génériques traditionnels basés sur les macros

  • La méthode traditionnelle pour implémenter des structures de données génériques en C consiste à générer les noms de structures, de fonctions et les types à l’aide de macros
  • L’approche est étendue en incluant plusieurs fois l’en-tête de la structure de données pour différents types

Exemples :

  • Utilisation de macros (par ex. CONCAT, NODE_TYPE, PREPEND_FUNC) pour générer les noms de structures et de fonctions adaptés au type
  • Des fonctions et structures distinctes sont générées pour chaque type : int, Foo, etc. obtiennent chacun leur propre définition de structure de données

Inconvénients :

  • Il est difficile de repérer où sont définis les types et les fonctions (comme ils sont générés par macros, leur traçage est compliqué)
  • Les fonctionnalités d’autocomplétion sont difficiles à exploiter
  • La génération de plusieurs versions d’une même fonction augmente la taille du binaire et le temps de build
  • Les noms de fonctions nécessitent un préfixe de type (par ex. Foo_list_prepend)

Génériques, étape 1 : l’approche par pointeur void

  • Le type de données de la structure est rendu indépendant du type en utilisant void *
  • Le champ data de la liste chaînée est déclaré comme void *
  • Comme aucun contrôle de type n’est possible, des erreurs de type peuvent survenir à l’exécution, avec une faible sécurité à la compilation
  • Utilisation inefficace de la mémoire et du cache : les nœuds et les données sont alloués séparément, ce qui ajoute un surcoût inutile et augmente les cache misses

Génériques, étape 2 : stockage inline (Flexible Array Member)

  • Utilisation d’un Flexible Array Member pour stocker directement les données dans le nœud au lieu d’un pointeur
  • Une seule allocation par nœud suffit, et dans le cache les données sont placées à proximité du pointeur next
  • Cette approche nécessite de transmettre des informations de taille, par exemple avec memcpy, mais améliore les performances grâce à une disposition mémoire cohérente
  • La fonction list_alloc_front permet d’initialiser directement la structure sans memcpy

Génériques, étape 3 : implémenter le contrôle de type

  • On ajoute des informations de type à la structure de données à la compilation en déclarant un pointeur de type paramétré dans le membre payload d’une union
  • Exemple : #define List(type) union { ListNode *head; type *payload; }
  • Cela permet d’obtenir le type de la liste via __typeof__(foo_list.payload)
  • Dans la macro list_prepend, un transtypage du type de fonction permet de ne compiler que si le type est correct
  • En cas d’utilisation d’un mauvais type, une erreur est produite à la compilation

Exemple d’erreur :

  • Si on ajoute un int à foo_list, le compilateur affiche un message d’erreur du type 'incompatible integer to pointer conversion'

Prise en charge des compilateurs sans typeof

  • Jusqu’à C23, __typeof__ n’était pas standard, donc certains compilateurs (par ex. d’anciennes versions de MSVC) ne le prennent pas en charge
  • Il est possible d’obtenir un effet proche par des méthodes de contournement, comme l’utilisation du membre payload dans une struct

Passage de paramètres et typedef

  • Même si deux List(Foo) ont la même forme, le compilateur les considère comme des types différents
  • En utilisant typedef, le passage de paramètres et les affectations deviennent plus fluides

Exemples :

  • typedef List(Foo) ListFoo;
  • Les variables ListFoo peuvent ensuite être déclarées et utilisées comme paramètres de fonction

Conclusion et extension à diverses structures de données

  • Cette technique peut aussi s’appliquer à des structures nécessitant plusieurs paramètres de type, comme les hash maps
  • Grâce à la union, il est possible de garantir séparément la sécurité de type des clés et des valeurs
  • Pour des exemples plus détaillés et l’implémentation des macros, voir le gist de code associé

Conclusion

  • Cette nouvelle approche surmonte les limites des méthodes existantes (lisibilité, efficacité de build, maintenabilité) et fournit un schéma de nommage cohérent des fonctions ainsi qu’une sécurité de type
  • Elle facilite la prise en charge de plusieurs structures de données et de paramètres de type multiples
  • Le contrôle de type à la compilation permet d’assurer à la fois la sûreté et l’efficacité dans l’usage des structures de données génériques

Remerciements

  • Cet article a été finalisé grâce aux retours et aux encouragements de Martin Fouilleul

À lire aussi

2 commentaires

 
click 2025-07-01

On peut se demander s’il ne suffit pas simplement d’utiliser Zig, non ?
 
GN⁺ 2025-07-01
Commentaires sur Hacker News

  • Dans le code de l’étape 2, l’usage de uint64_t data[]; est critiqué : il ne convient pas aux types dont les contraintes d’alignement sont supérieures à celles de uint64_t, et il est inutilement gaspilleur pour les types plus petits ; le problème est encore plus visible, par exemple, avec un ABI ilp32 sur architecture 64 bits. Pour le code de l’étape 3, il est indiqué qu’il faudrait écrire int main() { List(Foo) foo_list = {NULL}; ainsi. Sans typeof, on ne peut pas renvoyer la valeur de retour, et dans le code de remplacement, des erreurs liées à const peuvent survenir, problème mis en évidence par la symétrie de l’opérateur ==. Si on enlève payload, il n’y a plus d’information de taille, donc ce n’est pas sûr ; par exemple, ajouter un int32_t à List(int64_t) peut sembler acceptable, mais on ne peut pas déterminer la taille réelle de int32_t. Il faudrait des améliorations pour rendre cela plus sûr. L’auteur estime qu’il existe deux grandes limites à l’usage des generics en C : d’abord, l’approche par délégation via vtable limite les fonctionnalités, car une structure ne peut pas inclure de macros ; ensuite, avec une délégation vers une vtable externe, il faut déclarer à l’avance tous les types qui seront utilisés. La meilleure méthode serait de ne déclarer que des fonctions statiques dans un en-tête contenant les déclarations typedef, mais GCC et Clang n’émettent pas l’avertissement sur les static non définies au même moment. Enfin, il prend comme exemple la conception de fonctions recevant différentes structures de buffer pour souligner qu’il faut aussi gérer toutes les versions const

    • À propos du problème de délégation vers une vtable externe, quelqu’un raconte avoir déjà dû aller jusqu’à créer un compilateur pour le résoudre dans un ancien projet. Au lancement du projet Apache Clownfish, ils ont commencé par parser des fichiers .h, puis ont fini par créer leur propre format, les en-têtes Clownfish (.cfh). Il montre un exemple de code appelant la méthode Clone d’un objet réel, et explique qu’il fallait générer en masse ce type de code lourd pour fournir des bindings de langages dynamiques avec des fonctionnalités orientées objet. L’objectif de Clownfish était de fournir un modèle objet au plus petit dénominateur commun, et les types des langages liés étaient également générés depuis les .cfh. Il ajoute que, face à cette complexité, la plupart des gens finissent par renoncer à la sûreté de type et passer par des cast void*. https://github.com/apache/lucy-clownfish

    • À propos de int main(), il est rappelé qu’en C, int main() signifie que le nombre d’arguments est indéterminé. Il faut déclarer int main(void) pour signifier qu’il n’y a pas d’arguments. Un point que beaucoup de développeurs C++ oublient souvent, souligne le commentaire

    • Quelqu’un dit qu’il s’attendrait à ce qu’une union puisse réellement s’unifier, c’est-à-dire qu’un type puisse se déclarer lui-même comme faisant partie de la union d’un autre type

    • Il est signalé qu’au moment du malloc, à cause du padding interne, la taille calculée peut être inférieure à la taille réelle ; par exemple, avec malloc(sizeof(*node) + data_size);, cela peut être risqué

  • Un commentaire conteste le contenu de l’astuce n°0, expliquant l’avoir utilisée pour créer tout un dialecte de C. Il partage par exemple une implémentation de tas binaire générique : https://github.com/gritzko/librdx/blob/master/abc/HEAPx.h. La syntaxe est un peu lourde, mais au final on obtient une structure C ordinaire, avec de gros avantages en optimisation et en prévisibilité. Selon lui, les autres implémentations rendent inévitables void*, le dimensionnement mémoire à l’exécution et les définitions par macros

    • L’auteur répond que le tas binaire et la liste chaînée n’ont pas le même objectif. Un tas binaire doit lire les données au moment du stockage, donc l’approche diffère, et les choix peuvent être différents lorsqu’on écrit un tas binaire générique. Il précise l’avoir aussi mentionné dans une note de bas de page du billet

    • Quelqu’un donne plusieurs raisons de préférer une implémentation dans le header. En débogage, il est plus facile de suivre le code et d’exploiter les informations de type qu’avec des fonctions macro. Le compilateur peut appliquer des optimisations monomorphisées pour chaque instance, sans coût d’exécution ni contrainte de taille variable. On peut placer des structures génériques sur la pile. Les deux problèmes mentionnés par l’auteur peuvent être contournés : on peut facilement changer les noms avec des macros sur les noms de fonctions, et utiliser des weak symbols pour fusionner automatiquement les doubles définitions à l’édition de liens. Les conteneurs génériques de types pointeurs ont un autre problème, mais il peut être résolu avec des typedef, etc. Selon lui, les structures de données intrusives restent pratiques en C, même si elles sont difficiles à déboguer

    • L’expression « le compilateur l’avale comme un donut » a beaucoup fait rire quelqu’un

  • Lors d’une conversion de type de fonction, on suppose par exemple que la représentation interne de Foo* et void* est identique, mais ce n’est pas garanti par le C standard. En l’absence de compatibilité de type (« compatible »), de tels casts peuvent conduire à un comportement indéfini. Le compilateur peut aussi en être affecté dans son analyse d’aliasing, selon le commentaire (avec lien de référence) https://news.ycombinator.com/item?id=44421185

    • Il est répondu que c’est mentionné dans une note de bas de page du billet, et que le cast n’est pas le cœur de la sûreté de type. Il est recommandé de lire l’article en entier

  • Quelqu’un demande : « Pourquoi faire autant de contorsions pour avoir des generics en C ? Pourquoi ne pas simplement utiliser C++ ? »

    • Une réponse partage l’expérience selon laquelle, pour des raisons d’exigences de sûreté et autres contraintes, il est souvent impossible de migrer immédiatement vers C++ dans des projets legacy. Les nouveaux projets peuvent fixer des standards et adopter C++, mais les projets existants devront parfois rester en C encore un moment. Le commentaire souhaiterait un peu plus de compréhension contextuelle derrière le simple « utilisez juste C++ »

    • En pratique, dans les environnements qui utilisent C, passer à C++ peut être plus complexe et causer davantage de problèmes

    • À l’inverse, un autre avis estime qu’avec un peu d’effort on peut obtenir le même résultat en C, sans devoir aller jusqu’à C++

  • Quelqu’un présente une approche réellement utilisée dans le noyau Linux : inclure une struct list_head contenant les informations de liste dans une structure spécifique à chaque type. Lien de référence : https://kernelnewbies.org/FAQ/LinkedLists

    • Une remarque ajoute que les noms de macros LIST_HEAD_INIT et INIT_LIST_HEAD du noyau Linux ne paraissent pas très intuitifs

  • Dans le code de la section « typeof on old compilers », (list)->payload = (item); n’est en réalité pas un no-op : cela écrase la tête de liste avec item, fait remarquer un commentaire. Si c’était bien le comportement recherché, il faudrait l’envelopper dans if(0)

    • Le même commentaire note que, dans l’exemple, la union a été remplacée par une struct, ce qui paraît également gaspilleur. Il vaudrait mieux, selon lui, le traiter dans un if(0)

  • Quelqu’un montre qu’en D, une structure de liste générique de ce genre est bien plus simple, et compare le préprocesseur C à l’action d’enfoncer un clou avec un marteau sur son propre ongle, alors qu’un nail gun serait bien plus rapide et propre, pour souligner l’inconfort des macros C

    • Il lui est répondu que le billet concerne C, et que dans certains projets il faut absolument utiliser C

  • L’idée d’utiliser union et typeof() est jugée intéressante. De son côté, quelqu’un dit qu’avec les structures de données intrusives, il finit malgré tout par avoir besoin d’un wrapper composé de grosses macros, et se demande si une telle implémentation est aussi possible avec union et typeof. Il partage en exemple du code de wrapper pour table de hachage et sa documentation : https://github.com/FRRouting/frr/blob/master/lib/typesafe.h#L823-L971 https://docs.frrouting.org/projects/dev-guide/en/latest/lists.html

  • Quelqu’un indique utiliser déjà cette technique dans une bibliothèque expérimentale : https://github.com/uecker/noplate/blob/main/src/list.h

    • Il demande des idées pour des structures intrusives, c’est-à-dire pour inclure une structure de nœud dans les données afin qu’un objet puisse appartenir simultanément à plusieurs conteneurs

  • Le point clé semble être l’utilisation du type des pointeurs de fonction pour garantir la sûreté de type, au lieu du type de handle souvent employé. Il est ajouté que la norme C23 a amélioré les problèmes de compatibilité de type, avec partage du document standard et de l’état du support dans GCC/Clang récents : https://www.open-std.org/jtc1/sc22/wg14/www/docs/n3037.pdf

    • L’auteur répond que l’idée centrale est de lier l’information de type au type de données générique à l’aide d’une union, et que le cast de fonction n’est qu’une possibilité parmi d’autres. Il précise en avoir discuté en détail dans les notes de bas de page et dans la section « typeof on old compilers »