Implémenter le dictionnaire en C

Cet article présente plusieurs méthodes pour mettre en œuvre un dictionnaire en C.

Utilisez hcreate, hsearch et hdestroy pour implémenter la fonctionnalité de dictionnaire en C

En général, la bibliothèque standard C ne comprend pas de structure de données de dictionnaire intégrée, mais la norme POSIX spécifie des routines de gestion de table de hachage qui peuvent être utilisées pour mettre en œuvre la fonctionnalité de dictionnaire. À savoir, hcreate, hsearch et hdestroy fournissent des fonctionnalités telles que la création d’une table de hachage, l’insertion d’éléments dans celle-ci, la recherche d’éléments dans une table et la désaffectation de l’ensemble de la structure de données. Même si les fonctionnalités implémentées sont le strict minimum, elles peuvent résoudre de nombreux scénarios de problèmes.

Au début, la fonction hcreate doit être appelée pour créer une table de hachage avec un nombre maximum donné d’éléments, qui est passé comme seul argument. Notez que la capacité ne peut pas être modifiée après l’appel de la fonction hcreate ; ainsi, l’utilisateur doit prendre en compte ce problème dans la structure du code. Une fois que la table est créée, la fonction hsearch peut être appelée pour y ajouter des éléments. Elle prend 2 arguments ; le premier est de type ENTRY, défini comme struct de char* pour la clé et void* pour les données correspondantes. Le second paramètre est de type ACTION, qui est essentiellement un enum constitué de deux éléments, FIND et ENTER. Ces dernières valeurs sont utilisées pour indiquer l’opération à effectuer sur la table.

#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);
}

Production :

Intel -> Willow Cove

Remarquez que les exemples de code montrent les paires clé-valeur représentées par du texte en clair, mais l’utilisateur peut employer des algorithmes de hachage pour créer des clés et les stocker dans la table. Dans ce cas, nous avons ajouté 6 éléments au tableau en utilisant l’itération simple et avons sauté les deux derniers éléments. La boucle for suivante, cependant, interroge chaque élément du tableau original et imprime les données correspondantes.

La fonction hdestroy est utilisée pour libérer la mémoire de la table de hachage, mais elle ne libère pas les tampons des objets ENTRY, qui sont généralement créés par l’utilisateur. Ainsi, si les pointeurs de ces objets pointent vers la mémoire dynamique, l’appelant est responsable de la conservation des handles pour ces objets et de la désaffectation avant la sortie du programme. Gardez à l’esprit que les entrées individuelles ne peuvent pas être supprimées de la table.

#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);
}

Production :

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