Implementar Dicionário em C

ISO C não define um tipo de dicionário integrado. Se o ambiente de destino oferecer a interface POSIX hsearch, suas rotinas de tabela hash permitem armazenar e recuperar pares de chave e valor. O exemplo abaixo cria uma tabela, insere duas entradas, consulta uma chave presente e outra ausente, verifica os ponteiros retornados e libera a tabela. Ele demonstra uma abordagem, não todos os projetos de dicionário possíveis.

Use as rotinas POSIX hsearch para implementar um dicionário em C

hcreate, hsearch e hdestroy são rotinas POSIX declaradas em <search.h>, e não funções da biblioteca ISO C. A disponibilidade depende do sistema operacional e da biblioteca C de destino; portanto, confirme se o seu ambiente oferece essa interface antes de usar o exemplo. A especificação POSIX de hcreate e hsearch define a interface e permite consultar seus requisitos. O material fornecido não identifica uma plataforma ou versão específica de biblioteca.

Crie uma tabela hash e adicione entradas com hcreate e hsearch

Chame hcreate uma vez para criar uma tabela com a capacidade solicitada. A função retorna um valor diferente de zero em caso de sucesso e zero se não conseguir criar a tabela. ENTRY contém uma chave char * e um ponteiro de dados void *. Passe um ENTRY e um valor ACTION para hsearch: ENTER solicita a inserção, enquanto FIND solicita uma consulta. Uma chamada bem-sucedida retorna um ponteiro para uma entrada; em caso de falha, retorna NULL.

Execute este exemplo:

O código e os rótulos ou saídas exibidos nesta seção permanecem em inglês.

#define _XOPEN_SOURCE 700
#include <search.h>
#include <stdio.h>

int main(void) {
    if (hcreate(4) == 0) {
        fputs("could not create table\n", stderr);
        return 1;
    }

    ENTRY item = {"language", "C"};
    if (hsearch(item, ENTER) == NULL) {
        fputs("could not insert language\n", stderr);
        hdestroy();
        return 1;
    }

    item.key = "standard";
    item.data = "POSIX";
    if (hsearch(item, ENTER) == NULL) {
        fputs("could not insert standard\n", stderr);
        hdestroy();
        return 1;
    }

    ENTRY query = {"language", NULL};
    ENTRY *found = hsearch(query, FIND);
    if (found == NULL) {
        puts("language: not found");
    } else {
        printf("language: %s\n", (char *)found->data);
    }

    query.key = "compiler";
    found = hsearch(query, FIND);
    if (found == NULL) {
        puts("compiler: not found");
    } else {
        printf("compiler: %s\n", (char *)found->data);
    }

    hdestroy();
    return 0;
}

language: C
compiler: not found

A saída exibida inclui a mensagem compiler: not found, que permanece em inglês no exemplo inalterado.

Consulte chaves e trate entradas ausentes

A primeira chamada a FIND procura language, que o programa inseriu com o valor C; a segunda procura compiler, que não foi inserida. O resultado de cada consulta é verificado antes de o programa ler data, então um resultado NULL segue com segurança o caminho de “não encontrado”. Se uma consulta por uma chave que deveria existir retornar NULL, o exemplo ainda evita desreferenciar o ponteiro e informa o resultado. Adapte as mensagens ou a política de retorno às necessidades da sua aplicação.

hsearch também retorna NULL quando não consegue concluir uma inserção; por isso, verifique o resultado de cada chamada a ENTER antes de continuar. O exemplo trata falhas na criação e na inserção escrevendo um diagnóstico em stderr, liberando uma tabela que já tenha sido criada e retornando um status de falha. Faça essas verificações junto de cada operação para que o código seguinte só leia uma entrada depois de confirmar o ponteiro.

Libere a tabela e entenda seus limites

Chame hdestroy quando não precisar mais da tabela. A função libera a tabela, mas cabe ao chamador cuidar do armazenamento alocado dinamicamente para chaves ou valores referenciados pelas entradas; mantenha esses ponteiros e libere separadamente as alocações sob sua responsabilidade. O exemplo usa literais de string, portanto não há alocações desse tipo para liberar. A interface POSIX apresentada não oferece uma operação para remover uma entrada individual. Escolha uma capacidade adequada ao criar a tabela: o valor solicitado é passado a hcreate, e o fluxo mostrado não oferece uma operação para redimensioná-la.