Présentation du problème et des niveaux de génériques

Le langage C ne propose pas de mécanisme natif de génériques. L’auteur décrit quatre approches, chacune désignée comme un « niveau ». Le niveau 0 utilise des macros dans un en‑tête répété pour chaque type, le niveau 1 repose sur void * sans vérification de type, le niveau 2 stocke les données directement dans le nœud grâce à un tableau flexible, et le niveau 3 introduit une union qui fournit une information de type au moment de la compilation.

Technique d'union pour le contrôle de type (niveau 3)

Le cœur du procédé consiste à déclarer une macro #define List(type) union { ListNode *head; type *payload; }. Le champ payload n’occupe aucune place en mémoire, mais il permet au compilateur de connaître le type attendu. La macro list_prepend utilise l’opérateur ternaire 1 ? (item) : (list)->payload afin de forcer la conversion du paramètre item vers le type du payload. Si les types diffèrent, le compilateur génère une erreur de « pointer type mismatch », comme le montre l’exemple avec Foo et Bar. Cette stratégie évite les erreurs d’insertion à l’exécution tout en conservant une implémentation unique.

#define List(type) union { \
    ListNode *head; \
    type *payload; \
}
#define list_prepend(list, item) \
    _list_prepend(&((list)->head), \
        (1 ? (item) : (list)->payload), \
        sizeof(*(list)->payload))

Gestion de la mémoire et performances (niveaux 1‑2)

Le niveau 1, basé sur void *, nécessite deux allocations par nœud : une pour la structure et une pour l’objet pointé. Cette double allocation entraîne deux défauts de cache, car le processeur doit d’abord charger le nœud, puis l’objet séparé. Le niveau 2 résout ce problème en réservant un seul bloc mémoire contenant à la fois le nœud et les données grâce à un tableau flexible (char data[]). La fonction list_prepend copie les données avec memcpy, puis le nœud et les données sont contiguës, réduisant les accès mémoire et le nombre de défauts de cache. L’auteur recommande toutefois d’utiliser des arènes d’allocation pour éviter le coût de malloc répété.

struct ListNode { 
    ListNode *next; 
    char data[]; 
};
void list_prepend(ListNode **head, void *data, size_t data_size) {
    ListNode *node = malloc(sizeof(*node) + data_size);
    memcpy(node->data, data, data_size);
    node->next = *head;
    *head = node;
}

Limitations et perspectives d'utilisation

Le niveau 0, bien que fonctionnel, multiplie les définitions de fonctions, ce qui augmente la taille du binaire et complique la navigation dans le code. Les outils d’autocomplétion peinent à suivre les symboles générés par les macros. Le niveau 3, malgré son élégance, repose sur des macros complexes qui peuvent rendre le débogage plus difficile. De plus, la macro list_prepend masque la taille réelle des données, ce qui oblige le développeur à fournir le bon sizeof lors de l’appel de la fonction interne. L’article ne fournit pas de mesures de performance chiffrées, ce qui limite l’évaluation quantitative des gains de cache. Néanmoins, la combinaison d’union et de tableau flexible constitue une approche viable pour obtenir des structures génériques sûres en C sans recourir à des extensions du compilateur.