A programação genérica em C é uma técnica que permite escrever código que funciona com diferentes tipos de dados sem duplicar a lógica. O principal mecanismo para isso é o ponteiro void*, que é um ponteiro genérico capaz de apontar para qualquer tipo de dado. Essa abordagem é amplamente utilizada em bibliotecas como a função qsort da biblioteca padrão, que ordena arrays de qualquer tipo. Nesta aula, vamos explorar como criar estruturas de dados genéricas, realizar casts de forma segura, entender as vantagens e desvantagens dessa técnica e ver exemplos práticos que ilustram o conceito.

Dominar a programação genérica com void* é essencial para escrever código reutilizável e flexível em C, mas exige cuidado com a segurança de tipos e gerenciamento de memória. Ao final desta aula, você estará apto a implementar listas, pilhas e outras estruturas genéricas, além de compreender as implicações de usar ponteiros genéricos em projetos reais.

Estruturas genéricas

Estruturas genéricas são containers que armazenam dados de qualquer tipo, usando ponteiros void* para referenciar os elementos. A ideia central é que a estrutura não conhece o tipo dos dados, apenas o tamanho de cada elemento e funções de comparação ou cópia fornecidas pelo usuário. Isso permite criar listas, pilhas, filas e árvores que funcionam com inteiros, floats, strings ou estruturas definidas pelo programador.

Um exemplo clássico é uma lista dinâmica genérica. A estrutura contém um ponteiro para os dados (que pode ser um array de void* ou um array de bytes), o número de elementos, a capacidade e o tamanho de cada elemento. As funções de manipulação (inserir, remover, acessar) usam memcpy para copiar os dados, pois não conhecem o tipo específico. Vejamos um exemplo de implementação de uma lista genérica:

#include <stdio.h>
#include <stdlib.h>
#include <string.h>

typedef struct {
    void *data;        // ponteiro para o array de elementos
    size_t size;       // número de elementos
    size_t capacity;   // capacidade máxima
    size_t elem_size;  // tamanho de cada elemento em bytes
} Vector;

void vector_init(Vector *v, size_t elem_size) {
    v->data = NULL;
    v->size = 0;
    v->capacity = 0;
    v->elem_size = elem_size;
}

void vector_push_back(Vector *v, const void *element) {
    if (v->size == v->capacity) {
        v->capacity = v->capacity ? v->capacity * 2 : 4;
        v->data = realloc(v->data, v->capacity * v->elem_size);
        if (!v->data) {
            perror("realloc");
            exit(EXIT_FAILURE);
        }
    }
    // copia o elemento para o final do array
    memcpy((char*)v->data + v->size * v->elem_size, element, v->elem_size);
    v->size++;
}

void *vector_get(Vector *v, size_t index) {
    if (index >= v->size) return NULL;
    return (char*)v->data + index * v->elem_size;
}

void vector_free(Vector *v) {
    free(v->data);
    v->data = NULL;
    v->size = v->capacity = 0;
}

int main() {
    Vector v;
    vector_init(&v, sizeof(int));
    int x = 10, y = 20, z = 30;
    vector_push_back(&v, &x);
    vector_push_back(&v, &y);
    vector_push_back(&v, &z);
    for (size_t i = 0; i < v.size; i++) {
        int *p = (int*)vector_get(&v, i);
        printf("%d ", *p);
    }
    printf("\n");
    vector_free(&v);
    return 0;
}

Nesse código, a estrutura Vector armazena um ponteiro void* para os dados e o tamanho de cada elemento. A função vector_push_back usa memcpy para copiar o elemento para o array, e vector_get retorna um ponteiro para o elemento na posição desejada. Esse padrão permite que a mesma estrutura seja usada para qualquer tipo de dado, desde que o tamanho do elemento seja passado na inicialização.

Casting seguro

Casting seguro em C envolve converter um void* para um tipo específico de maneira que respeite o alinhamento e o tamanho dos dados. Como void* não carrega informações sobre o tipo, o programador deve garantir que o cast seja feito para o tipo correto, ou o comportamento será indefinido. Técnicas como usar memcpy para copiar dados em vez de fazer cast direto podem evitar problemas de alinhamento, especialmente em arquiteturas com requisitos estritos.

Outra prática é criar funções que encapsulam o cast, como vector_get que retorna um void* e deixa o usuário fazer o cast. Para aumentar a segurança, podemos fornecer macros ou funções inline que verificam o tipo em tempo de compilação, se possível. No entanto, em C puro, a verificação é limitada. Vejamos um exemplo de cast seguro usando memcpy:

#include <stdio.h>
#include <string.h>

int main() {
    int num = 42;
    void *ptr = &num;
    // Cast direto (potencialmente problemático em alguns casos)
    int *direct = (int*)ptr;
    printf("Direct: %d\n", *direct);
    // Cópia segura usando memcpy
    int copy;
    memcpy(&copy, ptr, sizeof(int));
    printf("Copy: %d\n", copy);
    return 0;
}

Nesse exemplo, tanto o cast direto quanto a cópia com memcpy funcionam para um inteiro, mas memcpy é mais seguro porque não depende do alinhamento do ponteiro. Em arquiteturas onde o alinhamento é obrigatório, um cast direto pode causar falhas de segmentação. Portanto, ao trabalhar com void*, é recomendável usar memcpy sempre que possível.

Trade-offs

A programação genérica com void* oferece flexibilidade, mas também apresenta desvantagens significativas. Entre as vantagens estão a reutilização de código e a possibilidade de criar estruturas de dados que funcionam com qualquer tipo. No entanto, a perda de informações de tipo pode levar a erros difíceis de depurar, pois o compilador não pode verificar se o cast é correto.

Além disso, o uso de void* pode impactar o desempenho, pois frequentemente requer cópias adicionais (como memcpy) e indireções extras. A legibilidade do código também pode ser comprometida, já que o leitor precisa saber o tipo real dos dados para fazer os casts corretamente. Outro ponto é a segurança: se um ponteiro for convertido para o tipo errado, o programa pode corromper memória ou falhar. Por isso, é fundamental documentar bem as funções e, se possível, usar macros ou wrappers para reduzir a chance de erro.

Em resumo, os trade-offs são:

  • Flexibilidade vs Segurança de tipo
  • Reutilização vs Complexidade
  • Desempenho vs Abstração

Cabe ao programador avaliar se a genericidade é necessária e se os riscos são aceitáveis.

Exemplos

Vamos explorar dois exemplos práticos: uma função de ordenação genérica e uma pilha genérica.

Exemplo 1: Função de ordenação genérica

A biblioteca padrão oferece qsort, que é genérica. Podemos implementar nossa própria versão para entender o mecanismo. A função recebe um array, o número de elementos, o tamanho de cada elemento e uma função de comparação. Usamos memcpy para trocar elementos.

#include <stdio.h>
#include <stdlib.h>
#include <string.h>

void swap(void *a, void *b, size_t size) {
    void *temp = malloc(size);
    memcpy(temp, a, size);
    memcpy(a, b, size);
    memcpy(b, temp, size);
    free(temp);
}

void bubble_sort(void *base, size_t n, size_t size, int (*cmp)(const void*, const void*)) {
    char *arr = (char*)base;
    for (size_t i = 0; i < n-1; i++) {
        for (size_t j = 0; j < n-i-1; j++) {
            if (cmp(arr + j*size, arr + (j+1)*size) > 0) {
                swap(arr + j*size, arr + (j+1)*size, size);
            }
        }
    }
}

int cmp_int(const void *a, const void *b) {
    int ia = *(int*)a;
    int ib = *(int*)b;
    return (ia > ib) - (ia < ib);
}

int main() {
    int arr[] = {5, 2, 9, 1, 7};
    size_t n = sizeof(arr)/sizeof(arr[0]);
    bubble_sort(arr, n, sizeof(int), cmp_int);
    for (size_t i = 0; i < n; i++) printf("%d ", arr[i]);
    printf("\n");
    return 0;
}

Exemplo 2: Pilha genérica

Uma pilha genérica pode armazenar qualquer tipo de dado. Implementamos as operações push, pop e top usando void*.

#include <stdio.h>
#include <stdlib.h>
#include <string.h>

typedef struct {
    void *data;
    size_t top;
    size_t capacity;
    size_t elem_size;
} Stack;

void stack_init(Stack *s, size_t elem_size) {
    s->data = NULL;
    s->top = 0;
    s->capacity = 0;
    s->elem_size = elem_size;
}

void stack_push(Stack *s, const void *elem) {
    if (s->top == s->capacity) {
        s->capacity = s->capacity ? s->capacity * 2 : 4;
        s->data = realloc(s->data, s->capacity * s->elem_size);
        if (!s->data) exit(1);
    }
    memcpy((char*)s->data + s->top * s->elem_size, elem, s->elem_size);
    s->top++;
}

void *stack_pop(Stack *s) {
    if (s->top == 0) return NULL;
    s->top--;
    return (char*)s->data + s->top * s->elem_size;
}

void stack_free(Stack *s) {
    free(s->data);
    s->data = NULL;
    s->top = s->capacity = 0;
}

int main() {
    Stack s;
    stack_init(&s, sizeof(double));
    double a = 3.14, b = 2.71;
    stack_push(&s, &a);
    stack_push(&s, &b);
    double *p = (double*)stack_pop(&s);
    printf("Pop: %.2f\n", *p);
    p = (double*)stack_pop(&s);
    printf("Pop: %.2f\n", *p);
    stack_free(&s);
    return 0;
}

Esses exemplos mostram como a programação genérica com void* pode ser aplicada em situações reais, permitindo criar funções e estruturas reutilizáveis.

Boas práticas

Ao usar void*, é importante seguir algumas boas práticas para evitar erros:

  • Documente claramente o tipo de dados esperado em cada função.
  • Use memcpy para copiar dados, em vez de atribuição direta, para evitar problemas de alinhamento.
  • Sempre valide índices e tamanhos antes de acessar a memória.
  • Considere usar macros para gerar funções específicas para cada tipo, evitando a perda de segurança.
  • Prefira funções genéricas da biblioteca padrão, como qsort, quando possível.

Referências

Exercícios

  1. Implemente uma função generic_swap que troca dois elementos de qualquer tipo, usando void* e memcpy. Teste com inteiros e com estruturas simples.

    2. ✓ Resposta: 
    #include <stdio.h>
#include <string.h>
#include <stdlib.h>

void generic_swap(void *a, void *b, size_t size) {
    void *temp = malloc(size);
    memcpy(temp, a, size);
    memcpy(a, b, size);
    memcpy(b, temp, size);
    free(temp);
}

typedef struct {
    int x;
    char c;
} Pair;

int main() {
    int i = 1, j = 2;
    generic_swap(&i, &j, sizeof(int));
    printf("i=%d, j=%d\n", i, j);
    Pair p1 = {10, 'a'}, p2 = {20, 'b'};
    generic_swap(&p1, &p2, sizeof(Pair));
    printf("p1: %d %c, p2: %d %c\n", p1.x, p1.c, p2.x, p2.c);
    return 0;
}
  2. Crie uma função generic_find que recebe um array genérico, seu tamanho, o tamanho de cada elemento, um ponteiro para o valor procurado, e uma função de comparação. Retorne o índice do elemento ou -1 se não encontrado.

    3. ✓ Resposta: 
    #include <stdio.h>
#include <string.h>

int generic_find(const void *base, size_t n, size_t size, const void *target, int (*cmp)(const void*, const void*)) {
    const char *arr = (const char*)base;
    for (size_t i = 0; i < n; i++) {
        if (cmp(arr + i*size, target) == 0) return (int)i;
    }
    return -1;
}

int cmp_int(const void *a, const void *b) {
    return *(int*)a - *(int*)b;
}

int main() {
    int arr[] = {5, 2, 9, 1, 7};
    int target = 9;
    int idx = generic_find(arr, 5, sizeof(int), &target, cmp_int);
    printf("Index: %d\n", idx);
    return 0;
}
  3. Modifique a lista genérica (Vector) para incluir uma função vector_remove que remove um elemento em um índice específico, deslocando os elementos seguintes.

    4. ✓ Resposta: 
    void vector_remove(Vector *v, size_t index) {
    if (index >= v->size) return;
    // desloca elementos para a esquerda
    memmove((char*)v->data + index * v->elem_size,
            (char*)v->data + (index+1) * v->elem_size,
            (v->size - index - 1) * v->elem_size);
    v->size--;
}
  4. Escreva uma função generic_max que recebe um array genérico e retorna um ponteiro para o maior elemento, usando uma função de comparação.

    5. ✓ Resposta: 
    void *generic_max(const void *base, size_t n, size_t size, int (*cmp)(const void*, const void*)) {
    const char *arr = (const char*)base;
    const char *max = arr;
    for (size_t i = 1; i < n; i++) {
        if (cmp(arr + i*size, max) > 0) max = arr + i*size;
    }
    return (void*)max;
}

// Exemplo de uso
int main() {
    int arr[] = {5, 2, 9, 1, 7};
    int *max = (int*)generic_max(arr, 5, sizeof(int), cmp_int);
    printf("Max: %d\n", *max);
    return 0;
}
  5. Implemente uma pilha genérica que armazene strings (char*). Use strdup para copiar as strings ao inserir e libere a memória ao remover. Considere que a pilha armazena ponteiros para strings.

    6. ✓ Resposta: 
    #include <stdio.h>
#include <stdlib.h>
#include <string.h>

typedef struct {
    void **data; // array de ponteiros
    size_t top;
    size_t capacity;
} Stack;

void stack_init(Stack *s) {
    s->data = NULL;
    s->top = 0;
    s->capacity = 0;
}

void stack_push(Stack *s, const char *str) {
    if (s->top == s->capacity) {
        s->capacity = s->capacity ? s->capacity * 2 : 4;
        s->data = realloc(s->data, s->capacity * sizeof(char*));
        if (!s->data) exit(1);
    }
    s->data[s->top++] = strdup(str);
}

char *stack_pop(Stack *s) {
    if (s->top == 0) return NULL;
    char *str = s->data[--s->top];
    return str; // o chamador deve liberar
}

void stack_free(Stack *s) {
    for (size_t i = 0; i < s->top; i++) free(s->data[i]);
    free(s->data);
    s->data = NULL;
    s->top = s->capacity = 0;
}

int main() {
    Stack s;
    stack_init(&s);
    stack_push(&s, "hello");
    stack_push(&s, "world");
    char *p = stack_pop(&s);
    printf("%s\n", p);
    free(p);
    p = stack_pop(&s);
    printf("%s\n", p);
    free(p);
    stack_free(&s);
    return 0;
}