Como escrever estruturas de dados type-safe (genéricas) em C

 (danielchasehooper.com)
3 pontos por GN⁺ 2025-07-01 | 2 comentários | Compartilhar no WhatsApp
  • Este texto explica um novo método para criar estruturas de dados type-safe (genéricas) na linguagem C
  • Explica, com o exemplo da implementação de uma lista ligada, uma técnica que associa informações de tipo à estrutura de dados usando union
  • Compara as diferenças em relação aos padrões genéricos tradicionais em C (macros, ponteiros void, Flexible Array Member) e as desvantagens de cada abordagem
  • Como permite verificação de tipos em tempo de compilação, é possível evitar previamente o uso de tipos incorretos
  • A nova técnica fornece uma interface de funções/estruturas de dados clara e consistente, como foo_list

Introdução

  • Apresenta uma forma de criar estruturas de dados genéricas com segurança de tipos em C
  • Essa técnica conecta informações de tipo à estrutura de dados em tempo de compilação usando union
  • Pode ser aplicada a qualquer estrutura de dados, como mapas, arrays e árvores binárias, e é explicada usando como exemplo uma implementação básica de lista ligada
  • Como muitos desenvolvedores acreditam que genéricos são impossíveis em C, a explicação é feita de forma simples e passo a passo

Genéricos tradicionais baseados em macros

  • A forma tradicional de implementar estruturas de dados genéricas em C é usar macros para gerar nomes de structs, funções e tipos
  • Isso é expandido incluindo o header da estrutura de dados várias vezes para diferentes tipos

Exemplos:

  • Uso de macros (por exemplo, CONCAT, NODE_TYPE, PREPEND_FUNC) para gerar nomes de structs e funções adequados ao tipo
  • Para cada tipo, funções e structs são geradas separadamente, de modo que tipos como int e Foo acabam com definições de estrutura de dados distintas

Desvantagens:

  • É difícil identificar onde os tipos e as definições de função estão (como são gerados por macros, é difícil rastrear)
  • É difícil aproveitar recursos de autocompletar de código
  • A geração de várias versões da mesma função aumenta o tamanho do binário e o tempo de build
  • Os nomes das funções precisam de prefixos de tipo (por exemplo, Foo_list_prepend)

Genéricos etapa 1: abordagem com ponteiro void

  • O tipo de dado da estrutura é definido como void *, tornando-a independente de tipo
  • O campo data da lista ligada é declarado como void *
  • Como não é possível fazer verificação de tipo, erros de tipo podem ocorrer em tempo de execução, com baixa segurança em tempo de compilação
  • Ineficiência de memória e cache: nó e dados são alocados separadamente, aumentando overhead desnecessário e cache misses

Genéricos etapa 2: armazenamento inline (Flexible Array Member)

  • Usa Flexible Array Member para armazenar os próprios dados no nó, em vez de guardar apenas um ponteiro
  • Uma única alocação por nó é suficiente, e os dados ficam próximos ao ponteiro next no cache
  • Essa abordagem exige passar informações de tamanho e usar algo como memcpy, mas melhora o desempenho por manter um layout de memória consistente
  • Usando a função list_alloc_front, é possível inicializar diretamente a struct sem memcpy

Genéricos etapa 3: implementação de verificação de tipos

  • Declara-se, no membro payload de uma union, um ponteiro do tipo parametrizado para adicionar informações de tipo à estrutura de dados em tempo de compilação
  • Exemplo: #define List(type) union { ListNode *head; type *payload; }
  • Assim, é possível obter o tipo da lista correspondente com __typeof__(foo_list.payload)
  • Em macros (list_prepend), faz-se cast do tipo da função, permitindo compilação apenas quando o tipo estiver correto
  • Ao usar um tipo incorreto, ocorre erro em tempo de compilação

Exemplo de erro:

  • Ao adicionar um int a foo_list, é exibida a mensagem de erro de compilação 'incompatible integer to pointer conversion'

Compatibilidade com compiladores sem suporte a typeof

  • Até o C23, __typeof__ não era padrão, então alguns compiladores (por exemplo, versões antigas do MSVC) não funcionam com isso
  • É possível obter efeito semelhante por caminhos alternativos, como usar o membro payload dentro de uma struct

Passagem de parâmetros e typedef

  • Mesmo List(Foo) com a mesma forma, o compilador os considera tipos diferentes entre si
  • Ao usar typedef, a passagem de parâmetros e a atribuição passam a funcionar melhor

Exemplo:

  • typedef List(Foo) ListFoo;
  • É possível declarar variáveis ListFoo e usá-las como parâmetros de função

Encerramento e expansão para várias estruturas de dados

  • Essa técnica também pode ser usada em estruturas de dados que exigem vários parâmetros de tipo (por exemplo, hash maps)
  • Com union, é possível garantir segurança de tipo separadamente para key e value
  • Para prática mais detalhada e a implementação das macros, consulte o gist de código relacionado

Conclusão

  • A nova abordagem supera as desvantagens das técnicas anteriores (legibilidade, eficiência de build e manutenibilidade) e fornece um esquema consistente de nomenclatura de funções e segurança de tipos
  • É fácil dar suporte a várias estruturas de dados e a múltiplos parâmetros de tipo
  • Com verificação de tipos em tempo de compilação, garante ao mesmo tempo segurança e eficiência no uso de estruturas de dados genéricas

Agradecimentos

  • Este texto foi concluído com o feedback e o incentivo de Martin Fouilleul

Leituras relacionadas

2 comentários

 
click 2025-07-01

Fico com a dúvida se não seria mais simples simplesmente usar Zig.
 
GN⁺ 2025-07-01
Comentários do Hacker News

  • Foi apontado que, no código da etapa 2, a forma de usar uint64_t data[]; não serve para tipos com exigência de alinhamento maior que uint64_t e, para tipos menores, desperdiça espaço desnecessariamente; por exemplo, isso é ainda mais problemático em um ABI ilp32 numa arquitetura de 64 bits. No código da etapa 3, a observação foi que deveria ser algo como int main() { List(Foo) foo_list = {NULL};. Sem typeof, não dá para devolver o valor de retorno, e no código alternativo podem surgir erros relacionados a const, problema que fica mais evidente por causa da simetria do operador ==. Se remover payload, não há informação de tamanho, então deixa de ser seguro; por exemplo, ao adicionar int32_t a List(int64_t), pode parecer que tudo bem, mas na prática não há como determinar o tamanho real de int32_t. A ideia é que seriam necessários complementos para tornar isso mais seguro. Também se comenta que há duas grandes limitações no uso de genéricos em C: primeiro, a delegação via vtable restringe funcionalidades porque a struct não pode incluir macros; segundo, ao delegar para uma vtable externa, é preciso declarar previamente todos os tipos que serão usados. O melhor método seria declarar apenas funções estáticas no cabeçalho que contém o typedef, mas foi acrescentado que GCC e Clang emitem o aviso de static undefined em momentos diferentes. No fim, foi citado como exemplo o projeto de funções que recebem structs de buffer diferentes, enfatizando que é preciso gerenciar inclusive todas as versões const

    • Sobre o problema da delegação para vtable externa, alguém compartilhou que já chegou a criar até um compilador para resolver isso em um projeto antigo. Ao iniciar o projeto Apache Clownfish, começaram fazendo parse de arquivos .h, mas acabaram criando um formato próprio de cabeçalho, o .cfh. Mostrou como exemplo o código que chama o método "Clone" de um objeto real, e relatou a experiência de ter de gerar em massa esse tipo de código forçado para permitir bindings de linguagens dinâmicas que precisavam de recursos orientados a objetos. O objetivo do Clownfish era fornecer o menor modelo de objetos comum possível, e os tipos das linguagens de binding também eram gerados a partir de .cfh. Acrescentou que, por causa dessa complexidade, a maioria acaba abrindo mão da segurança de tipos com casts para void*. https://github.com/apache/lucy-clownfish

    • Sobre int main(), foi ressaltado que, em C, int main() significa que a quantidade de argumentos é indefinida. Para indicar que não há argumentos, é preciso declarar int main(void). Foi destacado que muita gente que escreve C++ esquece isso com frequência

    • Houve a opinião de que seria interessante esperar uma união de union, isto é, que um tipo pudesse declarar a si mesmo como parte do union de outro tipo

    • Foi apontado que, ao fazer malloc, por causa de padding interno, o tamanho calculado pode acabar sendo menor que o real; por exemplo, levantou-se o risco de algo como malloc(sizeof(*node) + data_size);

  • Houve uma contestação ao conteúdo do truque #0, dizendo que a pessoa usou esse truque ao criar todo um dialeto de C. Foi compartilhado, por exemplo, um código de implementação de heap binário genérico https://github.com/gritzko/librdx/blob/master/abc/HEAPx.h. A sintaxe é um pouco pesada, mas no fim vira uma struct C comum, o que traz grandes ganhos de otimização e previsibilidade. Na visão dela, outras implementações inevitavelmente exigem void*, dimensionamento de memória em tempo de execução e definição por macros

    • Como autor do texto, foi explicado que binary heap e linked list têm objetivos diferentes. Como o binary heap precisa ler os dados no momento do armazenamento, a abordagem é distinta, e ao escrever um binary heap genérico as escolhas podem ser outras. Foi acrescentado que isso já era mencionado nas notas de rodapé do texto

    • Foram apresentados vários motivos para preferir implementação em cabeçalho. Ao depurar, é mais fácil rastrear o código e aproveitar as informações de tipo do que com funções em macro. O compilador pode fazer otimização monomorfizada para cada instância, sem custo em tempo de execução nem ônus de tamanho variável. Também dá para colocar structs genéricas na stack. Os dois problemas citados pelo autor poderiam ser contornados: nomes de função podem ser trocados facilmente com macros, e também se pode usar weak symbols para que definições duplicadas sejam mescladas automaticamente na linkedição. Contêineres genéricos para tipos ponteiro têm outro problema, mas isso também pode ser resolvido com typedef e afins. A pessoa acha que, em C, estruturas de dados intrusivas continuam sendo convenientes, embora difíceis de depurar

    • A expressão "o compilador engole isso como quem come rosquinha" provocou muitas risadas

  • Ao converter tipos de função, por exemplo, costuma-se assumir que Foo* e void* têm a mesma representação interna, mas o padrão da linguagem C não garante isso. Em situações sem compatibilidade de tipos ("compatible"), esse tipo de cast pode levar a comportamento indefinido. Também foi comentado que isso pode afetar o compilador em análises como aliasing (com link de referência) https://news.ycombinator.com/item?id=44421185

    • Foi respondido que isso já está mencionado nas notas de rodapé do texto, e que o cast não é o ponto central da segurança de tipos. Também foi sugerido ler o texto completo

  • Surgiu a pergunta: "por que fazer tanta gambiarra para usar generics em C; não seria melhor simplesmente usar C++?"

    • Foi compartilhada a experiência de que, em muitos projetos legados, por critérios de segurança e outras exigências, migrar para C++ não é viável no curto prazo. Em projetos novos, define-se um padrão e adota-se C++, mas projetos existentes ainda precisam permanecer em C por algum tempo. Houve o comentário de que a visão de "é só usar C++" poderia levar mais em conta esse contexto

    • Na prática, em ambientes que usam C, fazer a transição para C++ pode ser mais complexo e causar mais problemas

    • Em contrapartida, também foi defendida a posição de que, com um pouco de esforço, é possível obter o mesmo resultado em C, então não há necessidade de ir até C++

  • Foi apresentada a abordagem realmente usada no kernel Linux: o padrão de incluir uma struct list_head com as informações da lista dentro da struct específica de cada tipo. Foi fornecido um link de referência relacionado https://kernelnewbies.org/FAQ/LinkedLists

    • Houve quem achasse que os nomes das macros LIST_HEAD_INIT e INIT_LIST_HEAD no kernel Linux não são muito intuitivos

  • Foi apontado que, no código da seção "typeof on old compilers", (list)->payload = (item); na verdade não é um no-op, e sim faz o cabeçalho da lista ser sobrescrito por item. Foi sugerido que, se esse era o comportamento pretendido, deveria estar envolvido por if(0)

    • No exemplo, trocaram union por struct, e isso também pareceu desperdício. Foi comentado que seria melhor tratar isso dentro de if(0)

  • Foi mostrado que, na linguagem D, esse tipo de estrutura de lista genérica é muito mais simples; reforçou-se o desconforto com o preprocessor do C usando a metáfora de que ele parece martelar um prego com a unha, enquanto para pregar uma nail gun é muito mais rápida e limpa

    • Foi respondido que o post é sobre C, e que em alguns projetos é obrigatório usar C

  • A ideia de usar union e typeof() pareceu interessante. A pessoa comentou que, no próprio caso, para estruturas de dados intrusivas acabou precisando de wrappers envoltos em macros grandes, e questionou se também seria possível implementar isso com union e typeof. Como exemplo, compartilhou código de wrapper de hash table e link para documentação https://github.com/FRRouting/frr/blob/master/lib/typesafe.h#L823-L971 https://docs.frrouting.org/projects/dev-guide/en/latest/lists.html

  • Outra pessoa compartilhou que já usa essa técnica numa biblioteca experimental própria https://github.com/uecker/noplate/blob/main/src/list.h

    • Foi perguntado se haveria alguma ideia para structs intrusivas, isto é, uma forma de incluir a estrutura de nó nos dados para que um objeto possa pertencer simultaneamente a vários contêineres

  • Parece que a ideia central é garantir segurança de tipos aproveitando o tipo de ponteiros de função, em vez de implementar isso com o tipo de handle mais comum. Foi observado que o padrão C23 melhorou os problemas de compatibilidade de tipos, e foram compartilhados o documento do padrão e o estado do suporte recente em GCC/Clang https://www.open-std.org/jtc1/sc22/wg14/www/docs/n3037.pdf

    • Como autor do texto, foi enfatizado que a ideia principal é usar union para vincular informações de tipo ao tipo de dado genérico; cast de função não é a única forma, e várias alternativas foram discutidas, inclusive nas notas de rodapé e na seção "typeof on old compilers"