Cómo escribir estructuras de datos genéricas con seguridad de tipos en C

(danielchasehooper.com)

3 puntos por GN⁺ 2025-07-01 | 2 comentarios | Compartir por WhatsApp

En C también se pueden crear estructuras de datos genéricas con seguridad de tipos combinando macros, void *, flexible array member y union; el ejemplo muestra una implementación paso a paso con una lista enlazada
Incluir varias veces headers específicos por tipo es seguro, pero el código generado por macros dificulta rastrear definiciones y autocompletar, y puede aumentar el tamaño del binario y el tiempo de compilación
Una lista basada en void * es versátil, pero no evita errores de tipo; si el nodo y los datos se asignan por separado, puede haber 2 asignaciones por nodo y fallos de caché
Si se almacenan los datos dentro del nodo con flexible array member y se envuelve List(type) en un union, se puede añadir información de tipo en tiempo de compilación sin costo en tiempo de ejecución
La macro list_prepend hace coincidir, mediante el operador ternario, el valor pasado con el tipo de payload para provocar errores de compilación; para el tipo del puntero de retorno se puede usar __typeof__()

Punto de partida de la implementación de genéricos en C

El objetivo es declarar listas por tipo en C, como List(int) o List(Foo), y hacer que insertar un tipo incorrecto no compile
En el ejemplo se puede insertar un valor Foo en List(Foo), pero código como list_prepend(&foo_list, 7), que inserta otro tipo, no compila
Dentro de list_for(item, &foo_list), item puede tratarse como tipo Foo *

Nivel 0: enfoque de header genérico

Una forma es escribir la estructura de datos en un header y hacer varios #include cambiando la macro de tipo T
list.h genera mediante macros tipos y funciones como FooListNode y Foo_list_prepend, basándose en T
Este enfoque es genérico y seguro en tipos, pero su uso resulta tosco
- Como los tipos y funciones se componen con macros, es difícil encontrar dónde están definidos
- El autocompletado de código puede no funcionar bien
- Se crean copias de la misma función por cada tipo, lo que aumenta el tamaño del binario y el tiempo de compilación
- En vez de un único list_prepend(), hay que usar funciones con prefijo de tipo como Foo_list_prepend() o int_list_prepend()
Este enfoque puede ser más adecuado para funciones genéricas que requieren generación de código por tipo

Nivel 1: lista basada en `void *`

Si ListNode tiene void *data, puede contener datos de varios tipos
list_prepend(ListNode **head, void *data) guarda el puntero a los datos tal cual, por lo que la implementación es simple
El problema es que esta estructura no es segura en tipos
Si el nodo y los datos se asignan por separado, también aumentan los costos de memoria y rendimiento
- Se requieren dos asignaciones por nodo
- El propio puntero data usa memoria adicional
- Al recorrer la lista, puede haber fallos de caché tanto al acceder al siguiente nodo como al acceder a los datos
El código de ejemplo usa malloc por familiaridad, pero en la práctica se recomienda usar un Arena; como material relacionado se pueden consultar este video y este artículo

Nivel 2: almacenar los datos dentro del nodo

En lugar de void *data, usar Flexible Array Member permite colocar los datos dentro del nodo
struct ListNode tiene ListNode *next y char data[], y al asignar se reserva de una vez sizeof(* node) + data_size
list_prepend recibe los datos y su tamaño, y los copia a node->data con memcpy
Este enfoque ubica next y los datos reales cerca en memoria, reduciendo los problemas de asignación y caché del enfoque con void *
A cambio, el llamador debe pasar data_size
Si se quiere evitar memcpy, list_alloc_front puede devolver un puntero al área de datos del nodo para que el llamador inicialice esa memoria directamente
La alineación, el padding y el cálculo de tamaño del miembro data son otro tema, por lo que el ejemplo no los trata en detalle

Nivel 3: añadir información de tipo con `union`

La técnica clave es definir List(type) como un union, poniendo juntos el head real de la lista y un puntero para información de tipo

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

payload no se usa en tiempo de ejecución y proporciona información de tipo en tiempo de compilación
Como se usa union, payload no consume memoria adicional
Se pueden crear listas por tipo como List(Foo) foo_list o List(int) int_list

Verificación de tipos con el operador ternario

La macro list_prepend llama a la función interna _list_prepend y, mediante el operador ternario, hace coincidir los tipos de item y (list)->payload

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

Si los dos tipos candidatos del operador ternario no coinciden, el compilador emite un error de incompatibilidad de tipos
Por ejemplo, si se pasa un Bar * a List(Foo), Clang muestra un error de incompatibilidad entre los tipos de puntero Foo * y Bar *
La misma macro también pasa automáticamente el tamaño del tipo almacenado con sizeof(*(list)->payload)
El trabajo real lo realiza una función interna genérica como _list_prepend(ListNode **head, void *data, size_t data_size)

Usar `typeof()` para el tipo de retorno

Cuando una función genérica debe devolver un puntero a los datos internos, se puede usar __typeof__() para convertir el valor de retorno void * al tipo de payload

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

__typeof__() es compatible con Clang, GCC y MSVC 19.39 o superior
__typeof__() era una extensión opcional hasta su inclusión en el estándar C23
En compiladores sin __typeof__(), como MSVC anterior a 19.39, se puede usar verificación de tipos basada en el operador ternario
También es posible lograr retornos seguros en tipos mediante el método de asignación con payload, pero se omiten los detalles de implementación

Enfoque anterior y advertencias sobre definición

El enfoque anterior hacía una conversión de _list_prepend a un tipo de puntero a función que incluía __typeof__((list)->payload) antes de llamarla
Llamar a un puntero a función convertido de tipo es técnicamente comportamiento indefinido, aunque en compiladores y plataformas modernos se trata como algo que en la práctica no causa problemas
El enfoque actual induce el error mediante coincidencia de tipos con el operador ternario, en vez de convertir punteros a función

Problema al pasar `List(Foo)` como argumento

El compilador de C puede no considerar del mismo tipo dos definiciones de List(Foo) con la misma estructura

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

Si se define void my_function(List(Foo) list) como argumento de función y se llama my_function(a), también puede aparecer un error de tipos incompatibles
La solución es asignarle un nombre al tipo con typedef

typedef List(Foo) ListFoo;

ListFoo a;
ListFoo b = a; // ok

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

Para variables locales se puede seguir usando la forma List(Foo) local_foo_list
En GCC 15 y en Clang de fines de 2025, por un cambio de reglas, los tipos estructuralmente idénticos con el mismo nombre de etiqueta se tratarán como el mismo tipo

Aplicable también a estructuras de datos más allá de listas

La misma técnica puede aplicarse no solo a listas, sino también a varias estructuras de datos como maps, arrays o árboles binarios
También puede extenderse a estructuras de datos que requieren varios tipos relacionados
Por ejemplo, un hash map puede poner dentro del union la estructura interna, el tipo de clave y el tipo de valor

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

stb_ds.h también es un ejemplo de estructuras de datos genéricas con seguridad de tipos, pero como sus arrays y maps usan arrays de C, algunos errores de tipo se detectan en el momento de asignar el array, no cuando se pasa el valor

2 comentarios

click 2025-07-01

¿No sería más simple usar Zig?

GN⁺ 2025-07-01

Opiniones de Hacker News

En el código de nivel 2, uint64_t data[]; es incorrecto para tipos cuyos requisitos de alineación son mayores que los de uint64_t, y desperdicia espacio para tipos con requisitos menores. Por ejemplo, eso ocurre con el ABI ilp32 en arquitecturas de 64 bits.
El código de nivel 3 debería ser int main() { List(Foo) foo_list = {NULL};.
Como no hay typeof, si se recurre a un rodeo no se puede devolver nada, y como == es simétrico, ese rodeo también permite errores relacionados con const.
payload tampoco se puede omitir de forma segura, porque es necesario para conocer el tamaño correcto. Debería ser posible agregar un int32_t a List(int64_t), pero no se puede saber el sizeof de ese int32_t. A este código todavía le faltan bastantes piezas para funcionar correctamente.
Actualmente, los genéricos en C tienen dos grandes limitaciones. Primero, el enfoque de delegar en una vtable tiene funcionalidad limitada porque una estructura no puede contener macros, solo funciones. Segundo, para evitar overhead hay que delegar en una vtable externa, y para eso hay que declarar por adelantado todos los tipos que vayan a usar la vtable.
Lo mejor que he encontrado hasta ahora fue dejar solo declaradas, pero no definidas, funciones static en un header de avance que declara los typedef. De hecho, GCC y Clang difieren en la etapa en la que emiten la advertencia “undefined static” cuando no se incluye el header de un tipo específico en alguna unidad de traducción.
Por ejemplo, basta pensar en una función que reciba struct SizedBuffer {void *p; size_t len;}; o struct BoundedBuffer {void *begin; void *end;}; provenientes de headers distintos, y también sus respectivas versiones const.
- Debido al problema de que, para delegar en una vtable externa, hay que declarar por adelantado todos los tipos que usarán esa vtable, en el proyecto Apache Clownfish en el que participé hace tiempo incluso construimos un compilador para eso.
  Al principio parseábamos archivos .h, pero al final nos pareció mejor crear un pequeño lenguaje de headers llamado .cfh, “Clownfish Header”.
  Generábamos código como este para llamar a la versión CharBuf del método Clone definido en la clase padre Obj:
  
  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);
  }
  
  Se usaba así:
  
  cfish_CharBuf *charbuf = cfish_CharBuf_new();
  cfish_CharBuf *clone = CFISH_CharBuf_Clone(charbuf);
  
  El objetivo de Clownfish era ofrecer un modelo de objetos de mínimo común denominador para bindings de varios lenguajes dinámicos, y los archivos .cfh también se usaban para derivar tipos para los lenguajes de binding. Aun así, la cantidad de código repetitivo generado para evitar el problema señalado era realmente absurda.
  Por eso, casi todo el mundo prefiere renunciar a la seguridad de tipos y simplemente usar casts a void* en el destino de la llamada.
  https://github.com/apache/lucy-clownfish
- En C, int main() no significa que no reciba argumentos, sino que recibe un número desconocido de argumentos. Para indicar que no recibe argumentos hay que escribir int main(void). Es algo que quienes usan C++ suelen olvidar.
- Sería bueno que union pudiera extenderse de forma aditiva. Es decir, que un tipo pudiera declararse a sí mismo como parte de la misma union que otros tipos, sin tener que declarar de antemano en un solo lugar todos los tipos posibles.
- malloc(sizeof(*node) + data_size); también puede ser problemático por el padding. El tamaño calculado puede quedar demasiado pequeño.
No estoy de acuerdo.
Con el trick#0 mencionado en el artículo llegué a crear todo un dialecto de C. Por ejemplo, un heap binario genérico está en https://github.com/gritzko/librdx/blob/master/abc/HEAPx.h.
La sintaxis es algo pesada, pero tiene una gran ventaja: lo que obtienes al final es una estructura C normal, simple, predecible y fácil de optimizar. Es código que el compilador se devora como si nada.
Cualquier otro enfoque termina necesitando void* y cálculos de tamaño de memoria en runtime, y de todos modos también hay que definir macros.
- Soy el autor. Un heap binario y una lista enlazada tienen casos de uso distintos. Para almacenar correctamente en un heap binario hay que leer los datos que se insertan, pero en una lista enlazada no hace falta.
  Si hubiera usado un heap binario genérico, quizá habría ponderado las opciones de otra manera. También mencioné este punto en una nota al pie.
- Hay varias razones reales para preferir una implementación en headers. A diferencia de las funciones macro, el código en headers se puede seguir paso a paso en el debugger, y la información de tipos visible para el debugger también es mejor, así que el debugging mejora.
  Como cada instancia se monomorfiza, el compilador tiene más margen de optimización, y no hace falta pagar costos en runtime por tamaños variables. Al ser de tamaño fijo, también se puede poner una estructura genérica en el stack.
  Al menos dos de los problemas que menciona el autor se pueden esquivar. Los nombres pueden resolverse con una macro simple de name mangling, cambiando de Bar_func(args…) a func(Bar)(args…). La expansión del binario puede reducirse en parte usando símbolos débiles, para que el linker elimine duplicados de funciones compartidas entre unidades de traducción.
  Los contenedores genéricos de tipos puntero tienen otros problemas, pero se pueden esquivar con typedefs o alias de tipo.
  En C, las estructuras de datos intrusivas siguen siendo más cómodas, pero son dolorosas de manejar en el debugger.
El casteo de tipos de función asume que un tipo de puntero a elemento, por ejemplo Foo*, tiene la misma representación que void*, pero el estándar de C no garantiza eso. En términos del estándar, los dos tipos no son “compatibles”.
Por lo tanto, llamar a una función con el tipo convertido es comportamiento indefinido. Incluso si las representaciones de los punteros coinciden por casualidad, también afecta el análisis de aliasing del compilador. Sobre esto, también vale la pena ver [0].
Pareciera que castear funciones con distintos tipos de argumentos es el núcleo de la seguridad de tipos en las llamadas genéricas, pero no sé si esto es algo que se pueda corregir.
https://news.ycombinator.com/item?id=44421185
- Eso se trató en la nota al pie. El casteo no es el núcleo de la seguridad de tipos. Basta con leer todo el artículo.
Si uno quiere “C con genéricos”, ¿no sería mejor no dar tantas vueltas y simplemente usar C++?
- Porque trabajo en proyectos legacy sujetos a regulaciones de seguridad y otros controles de calidad. No puedo simplemente sacar una solución portada a C++, ni en la próxima release ni en la décima. Así que quizá haya que hacerla funcionar como se pueda hasta que eso sea posible.
  Dicho eso, para proyectos nuevos sí se pueden fijar estándares y expectativas para usar C++, y de hecho lo hacemos, definiendo un std específico como objetivo.
  Veo bastante seguido esta actitud en Hacker News, y se siente cercana a un “mejora tus habilidades”. Creo que acá hace falta mucho más contexto.
- Porque en muchos casos de uso donde se usa C, pasarse a C++ en realidad exige más vueltas.
- Algunas personas odian C++ hasta los huesos, por eso siguen apareciendo trabajos de este tipo.
  Fue realmente decepcionante que Microsoft se apartara de la postura de que “C++ es el futuro”, incluso después de su nuevo entusiasmo por Linux y el software libre y de código abierto.
  https://herbsutter.com/2012/05/03/reader-qa-what-about-vc-an...
  https://devblogs.microsoft.com/cppblog/c11-and-c17-standard-...
  Hoy eso ya no importa tanto, porque por las regulaciones gubernamentales y de ciberseguridad Microsoft tiene una nueva política para C y C++.
  https://azure.microsoft.com/en-us/blog/microsoft-azure-secur...
  https://blogs.windows.com/windowsexperience/2024/11/19/windo...
- La verdadera respuesta es que esto es más divertido.
- Si en C se puede lograr lo mismo con unas pocas vueltas, ¿para qué usar C++?
Es un truco genial. Ya lo estoy usando en mi propia biblioteca experimental: https://github.com/uecker/noplate/blob/main/src/list.h
- Si hay alguien que podría saberlo, probablemente seas tú: ¿ves alguna forma de aplicar este enfoque también a estructuras de datos intrusivas?
  Es el enfoque en el que, en vez de meter los datos dentro del nodo como ahora, se mete la estructura del nodo dentro de los datos y, como efecto adicional, un objeto puede pertenecer a varios contenedores.
Hay que tener cuidado con la parte que dice que “los tipos estructuralmente idénticos se consideran el mismo tipo gracias a un cambio de reglas en GCC 15 y Clang de fines de 2025”.
En las nuevas reglas, lo único que se considera el mismo tipo son las uniones con etiqueta, y deben tener la misma estructura y la misma etiqueta.
El macro List(T) tendría que cambiar para generar una etiqueta distinta para cada T. Para tipos simples de una sola palabra es fácil con ##, pero con algo apenas más complejo, como un puntero a char, es decir, un string, se vuelve imposible.
Claro que se podría obligar a hacer typedef de todos los tipos antes de usarlos en List, pero eso reduce mucho la generalidad.

typedef char *str;
List(str) my_list_of_str;
List(str) tokenize(str input) {...}
- No entiendo eso de que “solo las uniones con etiqueta se consideran el mismo tipo”. ¿Una tagged union no es simplemente un patrón de diseño?
Creo que el término habitual para un “miembro que no hace nada y solo conserva el tipo” es type witness. Pero hay mucha menos literatura sobre type witness de la que esperaba.
- Hay un término parecido, phantom type, para cuando existe una variable de tipo que no se usa en absoluto como tipo de una variable real.
  Lo vi sobre todo en Haskell, y también lo usé en Scala para imitar jerarquías de tipos que no existen en el sistema de tipos real.
  En cierto sentido, este truco con union también se parece a un phantom type, porque el tipo auxiliar en realidad no se usa para nada.
También está el enfoque que se usa en el kernel de Linux: embeber struct list_head, que contiene la información de la lista, dentro de la estructura específica de cada tipo.
https://kernelnewbies.org/FAQ/LinkedLists
- Los nombres LIST_HEAD_INIT e INIT_LIST_HEAD son confusos.
Si tengo que hacer esto, preferiría usar directamente templates de C++.
En D se hace así:

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

T!int node;

¿Por qué sufrir con el preprocesador de C? Usar macros del preprocesador es como usar un martillo en vez de una pistola de clavos para carpintería de acabado. La pistola de clavos es 10 veces más rápida, clava los clavos con precisión siempre y no deja marcas en forma de media luna en la pieza

Este artículo trata sobre C. En algunos proyectos es obligatorio usar C
No se trata de usar solo el martillo; se puede usar también un punzón. Clavas el clavo de moldura con el martillo hasta dejar unos 1/8 de pulgada, y luego lo terminas de hundir con el punzón