Estruturas genéricas

Até aqui, cada estrutura de dados que implementamos guardava um tipo fixo: a lista guardava int, a árvore de busca guardava pares de int. Se o programa precisar de uma lista de strings, ou de uma árvore de alunos, a saída mais direta é copiar a implementação inteira e trocar o tipo. Nesta página, vamos juntar duas ferramentas já vistas, o ponteiro void * e as funções de callback, para escrever uma única implementação de cada estrutura, que sirva para qualquer tipo de dado.

O problema: uma estrutura para cada tipo

Uma lista duplamente encadeada de inteiros tem um nó assim:

typedef struct noInt {
    int dado;
    struct noInt *anterior;
    struct noInt *proximo;
} NoInt;

void insereFimListaInt(ListaInt *lista, int dado);
void imprimeListaInt(const ListaInt *lista);   /* printf("%d", ...) */

Para uma lista de double, como NoInt guarda um int, não há o que reaproveitar: é preciso copiar NoInt, ListaInt e todas as funções, trocando int por double em cada uma. Para strings, mais uma cópia, agora alocando memória para o texto. Para um struct Aluno, mais uma.

Com tipos e cerca de 15 funções por lista, são funções quase idênticas. Um erro na lógica (esquecer de atualizar fim em uma remoção, por exemplo) precisa ser corrigido em todas as cópias. E o mesmo vale para pilhas, filas, árvores, tabelas de símbolos...

A ideia: void * e callbacks

A estrutura não precisa saber o que guarda. O nó passa a guardar um void *, um ponteiro para um dado de qualquer tipo, que fica fora do nó. E as operações que dependem do tipo (comparar, imprimir, liberar) chegam como callbacks, escritos por quem usa a estrutura e sabe o que há por trás do ponteiro.

A biblioteca padrão já usa essa ideia: o qsort ordena vetores de qualquer tipo porque recebe o tamanho de cada elemento e um comparador. A diferença é que, aqui, a ideia vai para dentro de uma estrutura de dados inteira.

A lista genérica

O TAD abaixo é a lista duplamente encadeada das páginas anteriores, com void *dado no lugar de int dado. Os tipos dos callbacks ficam no .h, com typedef:

typedef int (*Comparador)(const void *a, const void *b);
typedef void (*Impressor)(const void *dado);
typedef void (*Liberador)(void *dado);

Quase todo o código é igual ao da lista de inteiros. As diferenças aparecem em poucos lugares. A busca recebe a chave como const void * e um comparador, e devolve o dado encontrado (e não o nó, que é interno ao TAD):

void *buscaLista(const Lista *lista, const void *chave, Comparador comparar) {
    if (lista == NULL || chave == NULL || comparar == NULL)
        return NULL;
    for (No *p = lista->inicio; p != NULL; p = p->proximo)
        if (comparar(p->dado, chave) == 0)
            return p->dado;
    return NULL;
}

A impressão chama um Impressor para cada dado. E a liberação recebe um Liberador, porque nem sempre um free(dado) basta (um aluno tem o nome alocado à parte):

void liberaLista(Lista *lista, Liberador liberar) {
    if (lista == NULL)
        return;
    No *atual = lista->inicio;
    while (atual != NULL) {
        No *proximo = atual->proximo;
        if (liberar != NULL)
            liberar(atual->dado);       /* só quem conhece o tipo sabe liberar */
        free(atual);
        atual = proximo;
    }
    free(lista);
}

Com liberar igual a NULL, só os nós são liberados, e os dados ficam com quem os criou. Veremos mais adiante quando isso é necessário.

As remoções (removeInicioLista, removeFimLista, removePosicaoLista) devolvem o void * que estava no nó removido e não liberam o dado: quem chamou pode querer usá-lo antes de decidir o que fazer com ele.

O programa abaixo usa a mesma implementação para uma lista de inteiros e uma lista de strings. Explore os arquivos Lista.h e Lista.c: nenhuma linha deles menciona int ou char como tipo dos dados.

Para cada tipo, o main escreve só os callbacks: comparar e imprimir. Para liberar, free serve tanto para o int quanto para a string, porque cada dado é um único bloco alocado com malloc. O próprio free pode ser passado como Liberador: a assinatura void free(void *) é exatamente a que o tipo pede.

Uma lista de structs

O caso mais comum na prática é guardar structs. O Aluno tem o nome alocado dinamicamente, com o tamanho certo. Os callbacks do aluno ficam em um módulo próprio, Aluno.h e Aluno.c, que vamos reaproveitar na árvore genérica.

Dois detalhes:

• A chave da busca é um Aluno em que só a matrícula foi preenchida ({.matricula = 102}), porque compararMatricula só olha esse campo.
• liberarAluno libera primeiro o nome e depois o struct. Passar free para liberaLista liberaria só o struct, e os nomes vazariam.

Quem é o dono do dado?

Numa estrutura genérica, a estrutura guarda ponteiros, e não cópias. Isso levanta uma pergunta que a lista de inteiros nunca teve: quem é responsável por liberar cada dado? A regra que seguimos é a de um único dono:

1. Ao inserir, o dado (alocado por quem chamou) passa a ser da estrutura.
2. Ao remover, a estrutura devolve o dado, que volta a ser de quem chamou. Ele precisa ser liberado (ou inserido em outro lugar).
3. Ao destruir a estrutura, o liberador recebido libera os dados que ainda estavam nela.

for (int i = 0; i < 5; i++) {
    int x = 10 * i;
    insereFimLista(lista, &x);      /* ERRADO */
}

Map, filter e para cada

As funções de alta ordem da página anterior também funcionam sobre a lista genérica. mapLista e filterLista devolvem uma lista nova. paraCadaLista chama um callback para cada dado, com um contexto, e faz o papel do reduce: o contexto acumula o resultado, sem nenhuma alocação.

Lista *mapLista(const Lista *lista, Transformadora transformar);
Lista *filterLista(const Lista *lista, Predicado condicao);
void paraCadaLista(const Lista *lista, Visita visita, void *contexto);

Há uma diferença importante entre map e filter. O map cria dados novos (o callback transformar aloca cada um). Já o filter coloca na lista nova os mesmos ponteiros da lista original.

O contexto de paraCadaLista funciona como na página anterior. Em somar, ele é um long long * com a soma. Em guardarMaior, é o endereço de um ponteiro (int **) que, no fim, aponta para o maior dado, sem copiá-lo.

No fim do main, cada lista é liberada de um jeito, de acordo com quem é dono dos dados: numeros libera os seus, pares libera só os nós (os dados são de numeros) e dobrados libera os dados que o map criou.

Callback da operação ou da estrutura?

Na lista, cada operação recebe o callback de que precisa: buscaLista recebe um comparador, imprimeLista recebe um impressor. Isso é flexível: a mesma lista de alunos pode ser buscada por matrícula em um momento e por nome em outro, porque a busca na lista olha todos os elementos, um a um.

Em uma árvore de busca, isso não funciona. A posição de cada dado na árvore depende do comparador usado na inserção. Se cada insere ou busca pudesse receber um comparador diferente, a busca seguiria o caminho errado e não encontraria dados que estão na árvore. O comparador faz parte da definição da árvore: ele é escolhido na criação, guardado na estrutura e usado em todas as operações.

A árvore de busca genérica

A árvore genérica é a árvore binária de busca com void *dado nos nós e com o comparador e o liberador guardados na estrutura:

struct arvore {
    No *raiz;
    int tamanho;
    Comparador comparar;        /* os callbacks ficam guardados na árvore */
    Liberador liberar;
};

Arvore *criaArvore(Comparador comparar, Liberador liberar);

A busca é a mesma da árvore de inteiros. A única mudança é que as comparações < e > viram uma chamada ao comparador, e o sinal do resultado decide o caminho:

void *buscaArvore(const Arvore *arvore, const void *chave) {
    No *p = arvore->raiz;
    while (p != NULL) {
        int c = arvore->comparar(chave, p->dado);
        if (c == 0)
            return p->dado;
        p = c < 0 ? p->esq : p->dir;
    }
    return NULL;
}

O programa abaixo cria duas árvores com os mesmos alunos: uma em ordem de nome e outra em ordem de matrícula. Os módulos Aluno.h e Aluno.c são os mesmos da lista, sem nenhuma mudança.

Alguns pontos para observar:

• Duas árvores, um dono. porNome é criada com liberarAluno e é a dona dos alunos. porMatricula é criada com NULL: ela funciona como um índice, que só aponta para os alunos. É assim que bancos de dados mantêm vários índices sobre os mesmos registros.
• Inserção recusada. insereArvore devolve false quando já existe um dado equivalente (para compararNome, um aluno com o mesmo nome). Nesse caso, a árvore não guarda o dado, e ele continua sendo de quem chamou, que precisa liberá-lo.
• Percurso com contexto. percorreArvore visita os alunos em ordem, e o contexto acumula a soma das notas para a média. É o mesmo padrão do exercício de percurso com callback.

Uma lista com tipos diferentes em cada nó

Em Python, uma lista pode misturar tipos: [42, "olá", 3.14] é válida. Nas estruturas acima, cada uma guarda vários dados, mas todos do mesmo tipo: quem chama imprimeLista sabe se deve passar imprimirInt ou imprimirAluno. Dá para misturar tipos na mesma lista?

Um void * sozinho não basta. Ele não carrega nenhuma informação sobre o tipo do dado: essa informação se perde quando o ponteiro original é convertido para void *. Olhando só para o ponteiro, um callback não tem como saber se deve convertê-lo para int *, double * ou char *.

A solução é guardar o tipo junto com o dado. Em vez do dado, a lista recebe um pequeno pacote, o Elemento, com uma etiqueta (tag) que diz o tipo e um ponteiro para o valor:

A lista não mudou nada. Os callbacks consultam a etiqueta (com um switch) antes de converter o ponteiro. Essa é uma versão simplificada do que o Python faz por dentro: todo objeto Python carrega uma referência para o seu tipo, e é assim que o interpretador sabe, durante a execução, o que cada elemento é.

Vantagens e desvantagens

Vantagens:

• Uma única implementação para todos os tipos: um erro corrigido na lista genérica fica corrigido para todos os usos.
• Um tipo novo exige só os seus callbacks (comparar, imprimir, liberar), e não uma reimplementação.
• A mesma ideia vale para qualquer estrutura: listas, pilhas, filas, árvores, tabelas de símbolos, filas de prioridade.

Desvantagens:

• Menos verificação de tipos. O compilador não confere se um void * aponta para o tipo que o callback espera. Um erro vira acesso inválido à memória ou resultado errado durante a execução.
• Gerenciamento de memória mais delicado. É preciso definir quem é o dono de cada dado, e o liberador certo precisa chegar a cada estrutura.
• Custo extra. Cada dado é uma alocação à parte, e cada comparação é uma chamada de função por ponteiro. Para um único tipo, com desempenho crítico, uma estrutura escrita para aquele tipo é mais rápida.

Outras linguagens resolvem o mesmo problema com recursos próprios, como os templates de C++ e os generics de Java e C#, em que o compilador gera ou verifica o código para cada tipo e mantém a verificação de tipos. Em C, void * com callbacks é a forma padrão.

Exercícios

Encontre e corrija o erro

Os programas abaixo usam a lista genérica desta página. Cada um tem um erro diferente. Execute, leia a mensagem e encontre a causa.

Programa 1

liberaLista(numeros, free);
liberaLista(pares, NULL);

Programa 2

Aluno chave = {.nome = (char *)procurados[i]};
Aluno *achou = buscaLista(turma, &chave, compararNome);

Programa 3

void liberarAluno(void *dado) {
    Aluno *aluno = dado;
    free(aluno->nome);
    free(aluno);
}

Programa 4

Este programa acrescenta à lista a função removeSeLista, que remove todos os dados que satisfazem um predicado. O erro está nela, no arquivo Lista.c.

if (liberar != NULL)
    liberar(atual->dado);
free(atual);

Implemente

Inserção ordenada e remoção com predicado. Acrescente à lista genérica duas funções:

• insereOrdenadoLista(lista, dado, comparar), que insere o dado mantendo a lista em ordem crescente segundo comparar. Se houver dados equivalentes ao novo, ele entra depois deles.
• removeSeLista(lista, condicao, liberar), que remove todos os dados que satisfazem condicao, libera cada um com liberar (se ele não for NULL) e devolve quantos foram removidos.

As duas funções ficam em extras.c, que tem acesso à estrutura interna da lista (ListaInterno.h). Os testes conferem os encadeamentos (anterior, proximo, inicio, fim) e o tamanho depois de cada operação, quais dados foram liberados, e removem elementos de uma lista com 200 mil elementos.

Remoção na árvore de busca genérica. Implemente removeArvore(arvore, chave), que remove da árvore genérica o dado equivalente à chave e o libera com o liberador da árvore (se ele não for NULL), devolvendo false se não havia dado equivalente. O restante do TAD é o desta página. Os testes conferem a ordem da árvore e o tamanho, qual dado foi liberado em cada remoção, e fazem até 200 mil remoções.

Contador de palavras. Usando apenas a interface da árvore genérica (Arvore.h), implemente o contador de palavras de palavras.h. Cada Palavra guarda o texto (uma cópia alocada) e quantas vezes ele apareceu. contaPalavra acrescenta uma ocorrência, imprimeContagem imprime as palavras em ordem alfabética com as suas contagens e maisFrequente devolve a palavra que mais apareceu (no empate, a primeira em ordem alfabética). Os testes contam 400 mil palavras e conferem que toda a memória é liberada no fim.

Referências

• A. Backes. Linguagem C: Completa e Descomplicada. 2ª ed. Elsevier, 2018.
• D. R. Hanson. C Interfaces and Implementations: Techniques for Creating Reusable Software. Addison-Wesley, 1996.
• B. W. Kernighan e R. Pike. A Prática da Programação. Campus, 2000. Capítulo 2.