Pilha com elementos "genéricos" em C

10 de dezembro de 2011 4 respostas

davidbuzatto 10 de dezembro de 2011

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:

#ifndef PILHA_H
#define PILHA_H

#include <stdbool.h>

typedef struct elemento {
    void *valor;
    struct elemento *anterior;
} Elemento;

typedef struct pilha {
    int tamanho;
    Elemento *topo;
} Pilha;

void init( Pilha *pilha );
void push( Pilha *pilha, void *valor );
void* pop( Pilha *pilha );
bool empty( Pilha *pilha );
void print( Pilha *pilha, void (*print_func)(Elemento*) );

#endif // PILHA_H

pilha.c:

#include <stdlib.h>
#include <stdbool.h>
#include "pilha.h"

void init( Pilha *pilha ) {
    pilha->tamanho = 0;
    pilha->topo = NULL;
}

void push( Pilha *pilha, void *valor ) {

    Elemento *novoElemento = (Elemento*) malloc( sizeof( Elemento ) );
    novoElemento->valor = valor;
    novoElemento->anterior = pilha->topo;

    pilha->tamanho++;
    pilha->topo = novoElemento;

}

void* pop( Pilha *pilha ) {

    if ( !empty( pilha ) ) {

        Elemento *temp = pilha->topo;
        void *valor = temp->valor;

        pilha->topo = pilha->topo->anterior;
        pilha->tamanho--;

        free( temp );
        return valor;

    }

    return NULL;

}

bool empty( Pilha *pilha ) {
    if ( pilha->topo == NULL ) {
        return true;
    } else {
        return false;
    }
}

void print( Pilha *pilha, void (*print_func)(Elemento*) ) {

    Elemento *atual = pilha->topo;

    while ( atual != NULL ) {
        print_func( atual );
        atual = atual->anterior;
    }

}

main.c:

#include <stdio.h>
#include <stdlib.h>
#include "pilha.h"

void print_string( Elemento* e );

int main() {

    char v1[30] = "joao";
    char v2[30] = "maria";
    char v3[30] = "jose";

    Pilha pilha;
    init( &pilha );

    push( &pilha, v1 );
    push( &pilha, v2 );
    push( &pilha, v3 );

    void* e = pop( &pilha );
    printf( "Desempilhou: %s\n", (char*) e );

    print( &pilha, &print_string );

    return 0;
}

void print_string( Elemento* e ) {
    printf( "%s\n", (char*) e->valor );
}

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

[]'s

4 Respostas

entanglement 12 de dez. de 2011

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 é realmente um vector, 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).

davidbuzatto 12 de dez. de 2011

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

entanglement 12 de dez. de 2011

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) é 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.

davidbuzatto 12 de dez. de 2011

Oi entanglement,

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

[]'s

Criado 10 de dezembro de 2011

Ultima resposta 12 de dez. de 2011

Respostas 4

Participantes 2

4 Respostas

Topicos relacionados