Pilha com elementos "genéricos" em C

This message was edited 1 time. Last update was at 10/12/2011 12:12:59

Pessoal, meu exemplo é uma pilha, mas poderia ser qualquer outra estrutura de dados.
Gostaria que minha pilha pudesse armazenar qualquer tipo de dado, facilitando a criação da estrutura que representa cada elemento.
Em C++ o mecanismo de templates, assim como os genéricos em Java, poderia resolver isso para mim, mas em C não existe essa funcionalidade. Uma alternativa seria usar uniões, mas mesmo assim, caso eu queira inserir um novo tipo de dado na pilha eu teria que modificar a união.
Implementei a seguinte solução, usando elementos com valores do tipo void*:

pilha.h:

pilha.c:

main.c:

Gostaria de saber se este é o caminho mais usual adotado pela comunidade C nesse tipo de situação.

[]'s

GUJ Hacker Membro desde: 26/09/2009 09:18:56 Mensagens: 5750 Offline

davidbuzatto wrote:
Em C++ o mecanismo de templates, assim como os genéricos em Java, poderia resolver isso para mim, mas em C não existe essa funcionalidade.

Se você olhar o código do OpenSSL ( http://www.openssl.org ) vai ver que ele implementa algo semelhante a orientação a objeto (incluindo polimorfismo e herança) e estruturas de dados genéricas apenas com macros. (OK, não é a implementação mais bonita do mundo - na verdade foi um pouco "ad hoc" - mas você pode ter uma idéia de como fazer a sua.)

A vantagem é que como são macros, o equivalente de um vector<double> é realmente um vector<double>, não um vector<void*> que tem de apontar para N doubles alocados dinamicamente (o que é uma coisa muito custosa em linguagens como o C e o C++ que usam um alocador padrão de memória, que não é adequado para alocar milhões de objetos pequenos na memória).

This message was edited 1 time. Last update was at 12/12/2011 08:47:13

Oi entanglement,

Legal, entendi. Vou dar uma olhada.

Realmente fica um pouco estranho ter que ficar alocando tipos simples como o int usando malloc toda vez que for inserir algo na estrutura. Não sabia que o malloc era lento para tipos fundamentais. Pensei que o tempo de execução fosse quase o mesmo do que é resolvido durante compilação.

Acho que lembro de um post seu onde vc mencionava a openssl e dizia que era algo que não deveria se copiar pq era algo feito para simular OO.
Na verdade estou estudando estruturas de dados agora nas férias (vou dar aula ano que vem dessa disciplina) e normalmente ensina-se estruturas de um tipo simples para simplificar a implementação (o que é sempre abordado nos livros), mas me surgiu essa dúvida de como fazer algo genérico.

Muito obrigado!

[]'s

GUJ Hacker Membro desde: 26/09/2009 09:18:56 Mensagens: 5750 Offline

davidbuzatto wrote:Não sabia que o malloc era lento para tipos fundamentais.

Não é que ele seja lento. É que ocorre o seguinte: normalmente a alocação de memória em C é feita com algum algoritmo que é uma variação do percorrimento de uma "lista livre" (ou seja, lista de blocos vazios, onde você pode alocar memória). Como não há garbage collection, com o tempo a memória vai ficando muito fragmentada (cheia de blocos pequenos vazios).

Digamos que, por algum motivo, você crie 2 vetores de int* com um milhão de posições cada, e você vá alocando alternadamente ints para um e outro vetor. Imagine como a memória vai ficar fragmentada se você desalocar um desses vetores (obviamente desalocando cada um dos int que você alocou via malloc (sizeof (int)).

Quando você tem um padrão desses de alocação de memória, então alguma coisa está errada, e você normalmente tem de criar um método próprio de alocação de memória. Em vez disso, é preferível ter uma estrutura de dados que em vez de apontar para coisas tão pequenas, ponha essas coisas pequenas dentro do próprio objeto.

Em Java esse problema (digamos que você quer criar um ArrayList<Integer>

é grave mesmo, tanto é que
a) O Apache tem aquelas estruturas de dados em http://commons.apache.org/primitives/userguide.html que suportam alguns tipos primitivos;
b) Alguns engenheiros da Oracle estavam propondo que houvesse suporte na JVM (não na linguagem) para "structs", usados para evitar essa fragmentação na memória (que é mais ou menos aliviada pelo fato de haver garbage collection). Esse suporte seria transparente.

Oi entanglement,

Realmente não tinha pensado no problema da fragmentação.
Obrigado pelos esclarecimentos!

[]'s

Notícias, artigos e o maior fórum brasileiro sobre Java