Implementar Dicionário em C

Este artigo demonstrará vários métodos sobre como implementar um dicionário em C.

Use hcreate, hsearch e hdestroy para implementar a funcionalidade de dicionário em C

Geralmente, a biblioteca padrão C não inclui uma estrutura de dados de dicionário embutida, mas o padrão POSIX especifica rotinas de gerenciamento de tabela hash que podem ser utilizadas para implementar a funcionalidade de dicionário. A saber, hcreate, hsearch e hdestroy fornecem recursos como criar uma tabela hash, inserir itens nela, pesquisar o item em uma tabela e desalocar toda a estrutura de dados. Mesmo que a funcionalidade implementada seja o mínimo, ela pode resolver muitos cenários de problemas.

A princípio, a função hcreate precisa ser chamada para criar uma tabela hash com um determinado número máximo de elementos, que é passado como o único argumento. Observe que a capacidade não pode ser modificada após a chamada hcreate; portanto, o usuário precisa fatorar esse problema na estrutura do código. Depois que a tabela é criada, a função hsearch pode ser chamada para adicionar itens a ela. Leva 2 argumentos; o primeiro é do tipo ENTRY, definido como struct de char* para a chave e void* para os dados correspondentes. O segundo parâmetro é do tipo ACTION, que é essencialmente um enum que consiste em dois elementos, FIND e ENTER. Os últimos valores são usados para indicar qual operação realizar na mesa.

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

static char *companies[] = {"Intel",   "AMD",      "ARM", "Apple",
                            "Marvell", "Qualcomm", "IBM", "Nvidia"};

static char *uarch[] = {"Willow Cove", "Zen 3", "A78", "A14",
                        "ThunderX2",   "Kryo",  "z15", "Ampere"};

int main(void) {
  ENTRY e;
  ENTRY *ep;

  const size_t capacity = sizeof companies / sizeof companies[0];
  hcreate(capacity);

  for (size_t i = 0; i < capacity - 2; i++) {
    e.key = companies[i];
    e.data = (void *)uarch[i];

    ep = hsearch(e, ENTER);

    if (ep == NULL) {
      fprintf(stderr, "entry failed\n");
      exit(EXIT_FAILURE);
    }
  }

  e.key = "Intel";
  ep = hsearch(e, FIND);
  printf("%s -> %s\n", e.key, (char *)ep->data);

  hdestroy();
  exit(EXIT_SUCCESS);
}

Resultado:

Intel -> Willow Cove

Observe que os exemplos de código demonstram os pares de valores-chave representados por texto não criptografado, mas o usuário pode empregar algoritmos de hash para criar chaves e armazená-las na tabela. Nesse caso, adicionamos 6 itens à tabela usando a iteração simples e pulamos os dois últimos elementos. O próximo loop for, entretanto, consulta cada item do array original e imprime os dados correspondentes.

A função hdestroy é usada para liberar a memória da tabela hash, mas não libera os buffers nos objetos ENTRY, que geralmente são criados pelo usuário. Portanto, se os ponteiros nesses objetos apontam para a memória dinâmica, o chamador é responsável por manter os identificadores para eles e desalocá-los antes da saída do programa. Lembre-se de que entradas individuais não podem ser excluídas da tabela.

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

static char *companies[] = {"Intel",   "AMD",      "ARM", "Apple",
                            "Marvell", "Qualcomm", "IBM", "Nvidia"};

static char *uarch[] = {"Willow Cove", "Zen 3", "A78", "A14",
                        "ThunderX2",   "Kryo",  "z15", "Ampere"};

int main(void) {
  ENTRY e;
  ENTRY *ep;

  const size_t capacity = sizeof companies / sizeof companies[0];
  hcreate(capacity);

  for (size_t i = 0; i < capacity - 2; i++) {
    e.key = companies[i];
    e.data = (void *)uarch[i];

    ep = hsearch(e, ENTER);

    if (ep == NULL) {
      fprintf(stderr, "entry failed\n");
      exit(EXIT_FAILURE);
    }
  }

  for (size_t i = 0; i < capacity; i++) {
    e.key = companies[i];
    ep = hsearch(e, FIND);

    ep ? printf("%s -> %s\n", e.key, (char *)ep->data)
       : printf("%s -> %s\n", e.key, "Entry not found");
  }

  hdestroy();
  exit(EXIT_SUCCESS);
}

Resultado:

Intel -> Willow Cove
AMD -> Zen 3
ARM -> A78
Apple -> A14
Marvell -> ThunderX2
Qualcomm -> Kryo
IBM -> Entry not found
Nvidia -> Entry not found