Dictionary in C implementieren

ISO C definiert keinen integrierten Wörterbuchtyp. Wenn Ihre Zielumgebung die POSIX-Schnittstelle hsearch bereitstellt, können Sie mit ihren Hashtabellenroutinen Schlüssel-Wert-Einträge speichern und abrufen. Das folgende Beispiel legt eine Tabelle an, fügt zwei Einträge ein, sucht nach einem vorhandenen und einem fehlenden Schlüssel, prüft die zurückgegebenen Zeiger und gibt die Tabelle frei. Es zeigt einen möglichen Ansatz, nicht alle denkbaren Wörterbuchentwürfe.

POSIX-Routinen hsearch verwenden, um ein Wörterbuch in C zu implementieren

hcreate, hsearch und hdestroy sind POSIX-Routinen, die in <search.h> deklariert sind, und keine Funktionen der ISO-C-Bibliothek. Ob sie verfügbar sind, hängt vom Zielbetriebssystem und der C-Bibliothek ab. Prüfen Sie deshalb, ob Ihre Umgebung diese Schnittstelle bereitstellt, bevor Sie das Beispiel verwenden. Die POSIX-Spezifikation für hcreate und hsearch definiert die Schnittstelle und beschreibt ihre Anforderungen. Das Paket nennt keine bestimmte Plattform oder Bibliotheksversion.

Mit hcreate und hsearch eine Hashtabelle anlegen und Einträge hinzufügen

Rufen Sie hcreate einmal auf, um eine Tabelle mit der gewünschten Kapazität anzulegen. Bei Erfolg gibt die Funktion einen Wert ungleich null zurück, andernfalls null. ENTRY enthält einen Schlüssel vom Typ char * und einen Datenzeiger vom Typ void *. Übergeben Sie hsearch ein ENTRY und einen ACTION-Wert: ENTER fordert das Einfügen an, FIND die Suche. Bei einem erfolgreichen Aufruf erhalten Sie einen Zeiger auf einen Eintrag; schlägt der Aufruf fehl, gibt er NULL zurück.

Führen Sie dieses Beispiel aus:

Der Code und die angezeigten Bezeichnungen oder Ausgaben in diesem Abschnitt bleiben auf Englisch.

#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

Schlüssel suchen und fehlende Einträge behandeln

Der erste Aufruf von FIND sucht nach language, das das Programm mit dem Wert C eingefügt hat. Der zweite sucht nach compiler, das nicht eingefügt wurde. Vor dem Lesen von data prüft das Programm jedes Ergebnis. Ist es NULL, wird sicher der Pfad „nicht gefunden“ ausgeführt. Gibt eine Suche nach einem erwarteten Schlüssel NULL zurück, vermeidet das Beispiel ebenfalls eine Dereferenzierung und gibt das Ergebnis aus. Passen Sie die Meldungen oder die Rückgaberegel an Ihre Anwendung an.

hsearch gibt auch dann NULL zurück, wenn ein Einfügen nicht abgeschlossen werden kann. Prüfen Sie daher jedes Ergebnis von ENTER, bevor Sie fortfahren. Bei Fehlern beim Anlegen oder Einfügen schreibt das Beispiel eine Diagnose nach stderr, gibt eine bereits angelegte Tabelle frei und liefert einen Fehlerstatus zurück. Führen Sie diese Prüfungen direkt nach dem jeweiligen Aufruf aus, damit später nur auf einen Eintrag zugegriffen wird, dessen Zeiger zuvor geprüft wurde.

Tabelle freigeben und ihre Grenzen kennen

Rufen Sie hdestroy auf, wenn Sie die Tabelle nicht mehr benötigen. Die Funktion gibt die Tabelle frei; für dynamisch reservierten Speicher der Schlüssel oder Werte, auf den Einträge verweisen, bleibt jedoch der Aufrufer verantwortlich. Bewahren Sie diese Zeiger auf und geben Sie die selbst reservierten Speicherbereiche separat frei. Das Beispiel verwendet Zeichenkettenliterale und hat daher keinen solchen Speicher freizugeben. Die hier gezeigte POSIX-Schnittstelle bietet keine Möglichkeit, einzelne Einträge zu entfernen. Wählen Sie beim Anlegen eine ausreichende Kapazität: Sie übergeben die gewünschte Kapazität an hcreate, und der hier gezeigte Ablauf bietet keine Möglichkeit, die Tabelle zu vergrößern.