Dictionary in C implementieren

Dieser Artikel demonstriert mehrere Methoden, wie man ein Dictionary in C implementiert.

Verwenden Sie hcreate, hsearch und hdestroy, um Dictionaryfunktionalität in C zu implementieren

Im Allgemeinen enthält die C-Standardbibliothek keine eingebaute Dictionary-Datenstruktur, aber der POSIX-Standard spezifiziert Hash-Tabellen-Verwaltungsroutinen, die zur Implementierung der Dictionaryfunktionalität verwendet werden können. Die Routinen hcreate, hsearch und hdestroy bieten Funktionen wie das Erstellen einer Hash-Tabelle, das Einfügen von Elementen in diese, das Durchsuchen der Elemente in einer Tabelle und das Deallokieren der gesamten Datenstruktur. Auch wenn die implementierte Funktionalität das absolute Minimum ist, kann sie viele Problemszenarien lösen.

Zunächst muss die Funktion hcreate aufgerufen werden, um eine Hash-Tabelle mit einer vorgegebenen maximalen Anzahl von Elementen zu erzeugen, die als einziges Argument übergeben wird. Beachten Sie, dass die Kapazität nach dem Aufruf von hcreate nicht mehr verändert werden kann; daher muss der Anwender diesen Punkt in der Codestruktur berücksichtigen. Sobald die Tabelle erstellt ist, kann die Funktion hsearch aufgerufen werden, um Elemente in die Tabelle einzufügen. Sie nimmt 2 Argumente entgegen; das erste ist vom Typ ENTRY, definiert als struct von char* für den Schlüssel und void* für die entsprechenden Daten. Der zweite Parameter ist vom Typ ACTION, der im Wesentlichen ein enum ist, das aus zwei Elementen besteht, FIND und ENTER. Die letzteren Werte werden verwendet, um anzugeben, welche Operation auf der Tabelle ausgeführt werden soll.

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

Ausgabe:

Intel -> Willow Cove

Beachten Sie, dass in den Code-Beispielen die Schlüssel-Wert-Paare durch Klartext dargestellt werden, der Benutzer jedoch Hash-Algorithmen verwenden kann, um Schlüssel zu erstellen und diese in der Tabelle zu speichern. In diesem Fall haben wir mit der einfachen Iteration 6 Elemente zur Tabelle hinzugefügt und die letzten beiden Elemente übersprungen. Die nächste for-Schleife fragt jedoch jedes Element aus dem ursprünglichen Array ab und gibt die entsprechenden Daten aus.

Die Funktion hdestroy wird verwendet, um den Speicher der Hash-Tabelle freizugeben, aber sie gibt nicht die Puffer in den ENTRY-Objekten frei, die normalerweise vom Benutzer angelegt werden. Wenn also Zeiger in diesen Objekten auf dynamischen Speicher zeigen, ist der Aufrufer dafür verantwortlich, die Handles für sie zu halten und vor dem Programmende zu deallokieren. Beachten Sie, dass einzelne Einträge nicht aus der Tabelle gelöscht werden können.

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

Ausgabe:

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