Dizionario di implementazione in C

Questo articolo illustrerà più metodi su come implementare un dizionario in C.

Usa hcreate, hsearch e hdestroy per implementare la funzionalità del dizionario in C

In genere, la libreria standard C non include una struttura dati di dizionario incorporata, ma lo standard POSIX specifica routine di gestione delle tabelle hash che possono essere utilizzate per implementare la funzionalità del dizionario. Vale a dire, hcreate, hsearch e hdestroy forniscono funzionalità come la creazione di una tabella hash, l’inserimento di elementi in essa, la ricerca dell’elemento in una tabella e la deallocazione dell’intera struttura dei dati. Anche se la funzionalità implementata è il minimo indispensabile, può risolvere molti scenari di problemi.

All’inizio, la funzione hcreate deve essere chiamata per creare una tabella hash con un dato numero massimo di elementi, che viene passato come unico argomento. Nota che la capacità non può essere modificata dopo la chiamata hcreate; pertanto, l’utente deve considerare questo problema nella struttura del codice. Una volta creata la tabella, è possibile richiamare la funzione hsearch per aggiungervi elementi. Richiede 2 argomenti; il primo è di tipo ENTRY, definito come struct di char* per la chiave e void* per i dati corrispondenti. Il secondo parametro è di tipo AZIONE, che è essenzialmente un enum costituito da due elementi, FIND e ENTER. Questi ultimi valori vengono utilizzati per indicare quale operazione eseguire sul tavolo.

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

Produzione:

Intel -> Willow Cove

Si noti che gli esempi di codice dimostrano le coppie chiave-valore rappresentate da testo non crittografato, ma l’utente può utilizzare algoritmi di hashing per creare chiavi e memorizzarle nella tabella. In questo caso, abbiamo aggiunto 6 elementi alla tabella utilizzando l’iterazione semplice e abbiamo saltato gli ultimi due elementi. Il successivo cicli for, però, interroga ogni elemento dall’array originale e stampa i dati corrispondenti.

La funzione hdestroy viene utilizzata per liberare la memoria della tabella hash, ma non libera i buffer negli oggetti ENTRY, che di solito vengono creati dall’utente. Pertanto, se i puntatori in questi oggetti puntano alla memoria dinamica, il chiamante è responsabile della conservazione degli handle e della deallocazione prima dell’uscita del programma. Tieni presente che le singole voci non possono essere eliminate dalla tabella.

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

Produzione:

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