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

(danielchasehooper.com)

3 points par GN⁺ 2025-07-01 | 2 commentaires | Partager sur WhatsApp

Même en C, on peut créer des structures de données génériques sûres en types en combinant des macros, void *, des flexible array members et des union. L’exemple montre une implémentation pas à pas avec une liste chaînée.
La méthode consistant à inclure plusieurs fois un en-tête par type est sûre, mais le code généré par macros peut rendre le suivi des définitions et l’autocomplétion difficiles, tout en augmentant la taille du binaire et le temps de compilation.
Une liste basée sur void * est polyvalente, mais n’empêche pas les erreurs de type, et si le nœud et les données sont alloués séparément, cela peut entraîner deux allocations par nœud ainsi que des défauts de cache.
En stockant les données dans le nœud via un flexible array member et en enveloppant List(type) dans une union, on peut attacher des informations de type à la compilation sans coût à l’exécution.
La macro list_prepend utilise l’opérateur ternaire pour faire correspondre le type de la valeur transmise avec celui de payload et provoquer une erreur de compilation en cas d’incompatibilité, tandis que __typeof__() peut servir à typer le pointeur de retour.

Point de départ d’une implémentation générique en C

L’objectif est de pouvoir déclarer en C des listes typées comme List(int) ou List(Foo), et de faire en sorte qu’un type incorrect ne compile pas.
Dans l’exemple, on peut insérer une valeur de type Foo dans List(Foo), mais du code comme list_prepend(&foo_list, 7) ne compile pas si le type ne correspond pas.
À l’intérieur de list_for(item, &foo_list), item peut être manipulé comme un Foo *.

Niveau 0 : la méthode de l’en-tête générique

Une première approche consiste à écrire la structure de données dans un en-tête, puis à exécuter plusieurs #include en changeant à chaque fois la macro de type T.
list.h génère à partir de T des types et fonctions comme FooListNode ou Foo_list_prepend via des macros.
Cette approche est générique et sûre en types, mais son ergonomie laisse à désirer.
- Les types et fonctions étant définis par macros, il peut être difficile de retrouver l’emplacement des définitions.
- L’autocomplétion peut mal fonctionner.
- Une copie de la même fonction est produite pour chaque type, ce qui augmente la taille du binaire et le temps de compilation.
- Au lieu d’un unique list_prepend(), il faut utiliser des fonctions préfixées par type comme Foo_list_prepend() ou int_list_prepend().
Cette méthode peut toutefois être plus adaptée aux fonctions génériques qui nécessitent une génération de code spécifique à chaque type.

Niveau 1 : liste basée sur `void *`

Si ListNode contient un void *data, il peut stocker des données de types variés.
list_prepend(ListNode **head, void *data) se contente de stocker tel quel le pointeur vers les données, ce qui rend l’implémentation simple.
Le problème est que cette structure n’est pas sûre en types.
Si le nœud et les données sont alloués séparément, le coût mémoire et les performances se dégradent aussi.
- Deux allocations sont nécessaires par nœud.
- Le pointeur data consomme lui-même de la mémoire supplémentaire.
- Lors du parcours de la liste, l’accès au nœud suivant et l’accès aux données peuvent chacun provoquer des défauts de cache.
Le code d’exemple utilise malloc par habitude, mais en pratique l’auteur recommande d’utiliser une Arena et renvoie vers cette vidéo et cet article.

Niveau 2 : stocker les données dans le nœud

À la place de void *data, on peut utiliser un Flexible Array Member pour stocker les données directement dans le nœud.
struct ListNode contient alors ListNode *next et char data[], et l’allocation réserve en une seule fois sizeof(* node) + data_size.
list_prepend reçoit les données et leur taille, puis les copie dans node->data avec memcpy.
Cette approche place next et les données réelles à proximité en mémoire, ce qui réduit les surcoûts d’allocation et les problèmes de cache du modèle void *.
En contrepartie, l’appelant doit fournir data_size.
Si l’on veut éviter memcpy, list_alloc_front peut renvoyer un pointeur vers la zone de données du nœud pour que l’appelant initialise lui-même cette mémoire.
Les questions d’alignement du membre data, de padding et de calcul de taille constituent un sujet à part entière et ne sont pas détaillées dans l’exemple.

Niveau 3 : attacher des informations de type avec `union`

La technique clé consiste à définir List(type) comme une union contenant à la fois la tête réelle de la liste et un pointeur servant d’information de type.

#define List(type) union { \
    ListNode *head; \
    type *payload; \
}

payload n’est pas utilisé à l’exécution et sert uniquement à fournir une information de type à la compilation.
Comme il s’agit d’une union, payload ne consomme pas de mémoire supplémentaire.
On peut ainsi créer des listes typées comme List(Foo) foo_list ou List(int) int_list.

Vérifier les types avec l’opérateur ternaire

La macro list_prepend appelle une fonction interne _list_prepend en utilisant l’opérateur ternaire pour faire correspondre le type de item avec celui de (list)->payload.

#define list_prepend(list, item) \
    _list_prepend(&((list)->head), \
                  (1 ? (item) : (list)->payload), \
                  sizeof(*(list)->payload))

Si les deux types candidats de l’opérateur ternaire ne correspondent pas, le compilateur signale une erreur d’incompatibilité de type.
Par exemple, si l’on passe un Bar * à List(Foo), Clang signalera une incompatibilité entre les types de pointeurs Foo * et Bar *.
La même macro transmet aussi automatiquement la taille du type stocké via sizeof(*(list)->payload).
Le vrai travail est effectué par une fonction interne générique du type _list_prepend(ListNode **head, void *data, size_t data_size).

Utiliser `typeof()` pour le type de retour

Lorsqu’une fonction générique doit renvoyer un pointeur vers les données internes, __typeof__() permet de caster une valeur de retour en void * vers le type de payload.

#define list_alloc_front(list) \
    (__typeof__((list)->payload))_list_alloc_front(&(list)->head, sizeof(*(list)->payload))

__typeof__() est pris en charge par Clang, GCC et MSVC 19.39 ou version ultérieure.
Avant son inclusion dans la norme C23, __typeof__() était une extension optionnelle.
Sur les compilateurs ne prenant pas en charge __typeof__(), comme MSVC avant la version 19.39, la vérification de type via l’opérateur ternaire reste possible.
Un retour sûr en types peut aussi être obtenu via une approche d’allocation utilisant payload, mais les détails de mise en œuvre sont omis ici.

Ancienne méthode et précautions de définition

L’ancienne approche appelait _list_prepend après transtypage vers un type de pointeur de fonction incluant __typeof__((list)->payload).
Appeler un pointeur de fonction après transtypage relève techniquement d’un comportement non défini, même si dans la pratique cela ne pose pas de problème sur les compilateurs et plateformes modernes.
L’approche actuelle ne caste plus de pointeur de fonction et provoque les erreurs via la correspondance de types dans l’opérateur ternaire.

Le problème quand on passe `List(Foo)` en argument

Le compilateur C peut ne pas considérer deux définitions List(Foo) ayant pourtant la même structure comme étant du même type.

List(Foo) a;
List(Foo) b = a; // error

Même si l’on définit une fonction comme void my_function(List(Foo) list) puis qu’on appelle my_function(a), on peut obtenir une erreur de types incompatibles.
La solution consiste à donner un nom au type avec typedef.

typedef List(Foo) ListFoo;

ListFoo a;
ListFoo b = a; // ok

void my_function(ListFoo list);
my_function(a); // ok

Pour les variables locales, on peut continuer à utiliser une forme comme List(Foo) local_foo_list.
Avec GCC 15 et Clang vers la fin 2025, un changement de règle devrait faire en sorte que des types structurellement identiques portant le même nom de tag soient considérés comme le même type.

Application à d’autres structures de données que les listes

La même technique peut s’appliquer non seulement aux listes, mais aussi à d’autres structures de données comme les maps, tableaux ou arbres binaires.
Elle peut également être étendue aux structures nécessitant plusieurs types associés.
Par exemple, une table de hachage peut regrouper dans une même union sa structure interne, le type de clé et le type de valeur.

#define Map(key_type, value_type) union { \
    MapInternal map; \
    key_type *key; \
    value_type *value; \
}

stb_ds.h est lui aussi un exemple de structure de données générique sûre en types, mais comme ses tableaux et maps utilisent des tableaux C, certaines erreurs de type ne sont détectées qu’au moment de l’affectation au tableau, et non lors du passage de la valeur.

2 commentaires

click 2025-07-01

On peut se demander s’il ne suffit pas simplement d’utiliser Zig, non ?

GN⁺ 2025-07-01

Avis sur Hacker News

Dans le code de niveau 2, uint64_t data[]; est incorrect pour les types dont les exigences d’alignement sont supérieures à celles de uint64_t, et c’est du gaspillage pour les types plus petits. C’est le cas, par exemple, de l’ABI ilp32 sur les architectures 64 bits
Le code de niveau 3 devrait être int main() { List(Foo) foo_list = {NULL};
Comme il n’y a pas typeof, le contournement ne peut rien renvoyer, et comme == est symétrique, ce contournement laisse aussi passer des erreurs liées à const
On ne peut pas non plus omettre payload en toute sécurité, car il est nécessaire pour connaître la bonne taille. Il devrait être possible d’ajouter un int32_t à un List(int64_t), mais on ne peut pas connaître le sizeof de cet int32_t. Il manque encore pas mal d’éléments pour que ce code fonctionne correctement
Les génériques en C aujourd’hui ont deux grandes limites. Premièrement, l’approche consistant à déléguer à une vtable est limitée, car une struct ne peut pas contenir de macros, seulement des fonctions. Deuxièmement, pour éviter l’overhead, il faut déléguer à une vtable externe, ce qui impose de faire une déclaration anticipée de tous les types qui utiliseront la vtable
Le mieux que j’aie trouvé jusqu’ici consistait à déclarer, sans les définir, des fonctions static dans un en-tête d’anticipation qui déclare les typedefs. En pratique, le moment où un avertissement « undefined static » apparaît quand on n’inclut pas l’en-tête d’un type donné dans une unité de traduction diffère entre GCC et Clang
On peut par exemple penser à une fonction qui accepte struct SizedBuffer {void *p; size_t len;}; ou struct BoundedBuffer {void *begin; void *end;};, venus d’en-têtes différents, ainsi que leurs versions const respectives
- À cause de ce problème qui oblige à déclarer à l’avance tous les types susceptibles d’utiliser la vtable pour déléguer à une vtable externe, le projet Apache Clownfish auquel j’ai participé autrefois avait même créé un compilateur pour cela
  Au début, il analysait les fichiers .h, mais nous avons fini par juger préférable de créer un petit langage d’en-têtes, les .cfh « Clownfish Header »
  Pour appeler la version CharBuf de la méthode Clone définie dans la classe parente Obj, il générait ce genre de code
  
  typedef cfish_CharBuf*
  (*CFISH_CharBuf_Clone_t)(cfish_CharBuf* self);
  
  extern uint32_t CFISH_CharBuf_Clone_OFFSET;
  
  static inline cfish_CharBuf*
  CFISH_CharBuf_Clone(cfish_CharBuf* self) {
  const CFISH_CharBuf_Clone_t method
  = (CFISH_CharBuf_Clone_t)cfish_obj_method(
  self,
  CFISH_CharBuf_Clone_OFFSET
  );
  return method(self);
  }
  
  L’utilisation ressemblait à ceci
  
  cfish_CharBuf *charbuf = cfish_CharBuf_new();
  cfish_CharBuf *clone = CFISH_CharBuf_Clone(charbuf);
  
  L’objectif de Clownfish était de fournir un modèle objet plus petit dénominateur commun pour plusieurs bindings de langages dynamiques, et les fichiers .cfh servaient aussi à dériver les types pour les langages de binding. Malgré tout, la quantité de code passe-partout générée pour éviter le problème signalé était franchement absurde
  C’est pourquoi presque tout le monde renonce à la sécurité de typage et se contente de caster la cible de l’appel en void*
  https://github.com/apache/lucy-clownfish
- En C, int main() ne signifie pas que la fonction ne prend pas d’arguments, mais qu’elle prend un nombre inconnu d’arguments. Pour dire qu’elle ne prend pas d’arguments, il faut écrire int main(void). C’est un fait que les personnes venant du C++ oublient souvent
- Ce serait bien que les union puissent être étendues de manière fédérative : qu’un type puisse se déclarer lui-même comme faisant partie de la même union qu’un autre type, sans avoir à déclarer au même endroit tous les types possibles à l’avance
- malloc(sizeof(*node) + data_size); peut aussi poser problème à cause du padding. La taille calculée peut être trop petite
Je ne suis pas d’accord
J’ai déjà créé tout un dialecte de C avec le trick#0 décrit dans l’article. Par exemple, un tas binaire générique se trouve ici : https://github.com/gritzko/librdx/blob/master/abc/HEAPx.h
La syntaxe est un peu lourde, mais le gros avantage est qu’au bout du compte on obtient une struct C ordinaire, simple, prévisible et facile à optimiser. C’est du code que le compilateur avale comme un beignet
Les autres approches finissent par nécessiter des void* et des calculs de taille mémoire à l’exécution, et il faut de toute façon aussi définir des macros
- Je suis l’auteur. Un tas binaire et une liste chaînée ont des cas d’usage différents. Pour stocker correctement un élément dans un tas binaire, il faut lire les données qu’on insère, alors qu’une liste chaînée n’en a pas besoin
  Si j’avais utilisé un tas binaire générique, j’aurais peut-être évalué les options autrement. Je le mentionne aussi dans une note de bas de page
- Il existe en fait plusieurs bonnes raisons de préférer une implémentation dans les en-têtes. Contrairement aux fonctions macros, le code d’en-tête peut être suivi pas à pas dans un débogueur, et les informations de type visibles par le débogueur sont meilleures, ce qui rend le débogage plus agréable
  Comme chaque instance est monomorphisée, le compilateur a aussi davantage de possibilités d’optimisation, et il n’y a pas de coût à l’exécution dû aux tailles variables. Comme la taille est fixe, on peut aussi placer la struct générique sur la pile
  Au moins deux des problèmes mentionnés par l’auteur peuvent être contournés. Les noms peuvent être transformés avec une simple macro de name mangling, de Bar_func(args…) en func(Bar)(args…). Le gonflement du binaire peut être en partie réduit en utilisant des symboles faibles, afin que les fonctions partagées entre unités de traduction soient dédupliquées à l’édition de liens
  Les conteneurs génériques de types pointeurs posent d’autres problèmes, mais on peut les contourner avec des typedefs ou des alias de type
  En C, les structures de données intrusives restent plus pratiques, mais elles sont pénibles à manipuler dans un débogueur
Le cast de type de fonction suppose que le type de pointeur vers l’élément, par exemple Foo*, a la même représentation que void*, ce que la norme C ne garantit pas. Dans la terminologie de la norme, les deux types ne sont pas « compatibles ».
Appeler une fonction avec le type converti relève donc d’un comportement indéfini. Même si la représentation des pointeurs se trouve être identique par hasard, cela affecte aussi l’analyse d’aliasing du compilateur. À ce sujet, [0] mérite aussi d’être consulté.
Caster une fonction avec des types d’arguments différents semble être au cœur de la sûreté de type des appels génériques, mais je ne sais pas si c’est un problème qu’on peut corriger.
https://news.ycombinator.com/item?id=44421185
- C’est traité dans les notes de bas de page. Le cast n’est pas au cœur de la sûreté de type. Il suffit de lire l’article en entier.
Si l’on veut du « C avec des génériques », pourquoi ne pas simplement utiliser C++ plutôt que de faire autant de détours ?
- Parce que je travaille sur des projets legacy soumis à des réglementations de sûreté et à d’autres contraintes d’assurance qualité. Je ne peux pas simplement livrer une solution portée en C++ dans la prochaine version, ni même dans la dixième. Il faut donc parfois faire en sorte que ça tourne coûte que coûte jusqu’à ce que ce soit possible.
  En revanche, pour les nouveaux projets, on peut fixer comme standard et comme attente d’utiliser C++, et c’est bien ce que nous faisons, en ciblant un std précis.
  Je vois assez souvent ce genre d’attitude sur Hacker News, et ça ressemble un peu à un « montez en compétence ». À mon avis, il faut beaucoup plus de contexte que ça.
- Parce que, pour beaucoup de cas d’usage où C est employé, passer à C++ demanderait au contraire encore plus de détours.
- Certains détestent viscéralement C++, d’où la persistance de ce genre de travaux.
  Après le regain d’intérêt de Microsoft pour Linux et les logiciels libres et open source, il a été vraiment décevant de les voir abandonner l’idée que « C++ est l’avenir ».
  https://herbsutter.com/2012/05/03/reader-qa-what-about-vc-an...
  https://devblogs.microsoft.com/cppblog/c11-and-c17-standard-...
  Aujourd’hui, avec les nouvelles politiques de Microsoft sur C et C++ liées aux pouvoirs publics et aux réglementations cyber, ce n’est plus très important.
  https://azure.microsoft.com/en-us/blog/microsoft-azure-secur...
  https://blogs.windows.com/windowsexperience/2024/11/19/windo...
- La vraie réponse, c’est que c’est plus amusant comme ça.
- Si l’on peut obtenir le même résultat en C avec seulement quelques détours, pourquoi utiliser C++ ?
Joli tour de passe-passe. Je l’utilise déjà dans ma bibliothèque expérimentale : https://github.com/uecker/noplate/blob/main/src/list.h
- S’il y a quelqu’un qui pourrait le savoir, c’est probablement vous : voyez-vous un moyen d’appliquer cette approche aux structures de données intrusives ?
  C’est-à-dire mettre la structure de nœud dans les données, plutôt que les données dans le nœud comme ici, avec l’avantage annexe qu’un même objet peut appartenir à plusieurs conteneurs.
Il faut faire attention à l’affirmation selon laquelle « les types structurellement identiques sont considérés comme le même type dans GCC 15 et dans Clang fin 2025 grâce à un changement de règles ».
Dans les nouvelles règles, seuls les unions avec tag sont considérés comme le même type, et il faut qu’ils aient la même structure ainsi que le même tag.
La macro List(T) devrait être modifiée pour générer un tag différent pour chaque T. C’est facile avec ## pour un type simple en un seul mot, mais impossible dès que ça devient un peu plus complexe, comme un pointeur vers char, c’est-à-dire une chaîne.
Bien sûr, on peut imposer que tous les types soient définis avec typedef avant d’être utilisés avec List, mais cela réduit fortement la généricité.

typedef char *str;
List(str) my_list_of_str;
List(str) tokenize(str input) {...}
- Je ne comprends pas l’idée que « seules les unions avec tag sont considérées comme le même type ». Une union taguée, ce n’est pas simplement un patron de conception ?
Le terme courant pour un « membre qui ne fait rien et ne sert qu’à porter un type » me semble être type witness. Cela dit, il y a beaucoup moins de littérature sur les type witnesses que je ne l’aurais cru.
- Quand on a une variable de type qui n’est jamais utilisée comme type d’une vraie variable, il existe un terme proche : phantom type.
  Je l’ai surtout vu en Haskell, et je m’en suis aussi servi en Scala pour simuler une hiérarchie de types qui n’existe pas dans le système de types réel.
  D’une certaine manière, cette astuce avec une union ressemble aussi à un phantom type, puisque le type auxiliaire n’est jamais réellement utilisé.
Il y a aussi l’approche utilisée dans le noyau Linux : embarquer struct list_head, qui contient les informations de liste, dans une structure propre à chaque type.
https://kernelnewbies.org/FAQ/LinkedLists
- Les noms LIST_HEAD_INIT et INIT_LIST_HEAD prêtent à confusion.
Si je dois en arriver là, autant utiliser directement les templates C++.
En D, on fait comme ça :

struct ListNode(T) {
ListNode* next;
T data;
}

T!int node;

Pourquoi se donner du mal avec le préprocesseur C ? Utiliser des macros du préprocesseur, c’est comme utiliser un marteau au lieu d’un cloueur pneumatique pour des travaux de finition en menuiserie. Le cloueur est 10 fois plus rapide, enfonce les clous précisément à chaque fois et ne laisse pas de marques en demi-lune sur la pièce.

Cet article parle de C. Dans certains projets, il faut impérativement utiliser C.
Il ne suffit pas d’utiliser un marteau : on peut aussi utiliser un chasse-clou. On enfonce le clou de moulure au marteau en laissant environ 1/8 de pouce, puis on le pousse jusqu’au bout avec le chasse-clou.