Dizionario di implementazione in C

ISO C non definisce un tipo dizionario integrato. Se l’ambiente di destinazione fornisce l’interfaccia POSIX hsearch, le relative routine per tabelle hash offrono un modo per memorizzare e recuperare coppie chiave-valore. L’esempio seguente crea una tabella, vi inserisce due voci, cerca una chiave presente e una assente, controlla i puntatori restituiti e libera la tabella. Mostra un approccio, non tutti i possibili modi di progettare un dizionario.

Usare le routine POSIX hsearch per implementare un dizionario in C

hcreate, hsearch e hdestroy sono routine POSIX dichiarate in <search.h>, non funzioni della libreria ISO C. La loro disponibilità dipende dal sistema operativo e dalla libreria C di destinazione: prima di usare l’esempio, verifica che il tuo ambiente fornisca questa interfaccia. La specifica POSIX di hcreate e hsearch definisce l’interfaccia e permette di consultarne i requisiti. Il packet non indica una piattaforma o una versione specifica della libreria.

Creare una tabella hash e aggiungere voci con hcreate e hsearch

Chiama hcreate una volta per creare una tabella con la capacità richiesta. Restituisce un valore diverso da zero in caso di successo e zero se non riesce a creare la tabella. ENTRY contiene una chiave char * e un puntatore ai dati void *. Passa a hsearch un valore ENTRY e un valore ACTION: ENTER richiede l’inserimento, mentre FIND richiede la ricerca. In caso di successo, la chiamata restituisce un puntatore a una voce; in caso di errore, restituisce NULL.

Esegui questo esempio:

Il codice e le etichette o gli output visibili in questa sezione restano in inglese.

#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

Cercare le chiavi e gestire quelle mancanti

La prima chiamata a FIND cerca language, che il programma ha inserito con il valore C; la seconda cerca compiler, che non è stata inserita. Ogni risultato viene controllato prima che il programma legga data, quindi un risultato NULL porta in sicurezza al ramo «non trovato». Se la ricerca di una chiave che dovrebbe esistere restituisce NULL, l’esempio evita comunque di dereferenziarlo e segnala il risultato. Adatta i messaggi o la politica di restituzione alle esigenze della tua applicazione.

Anche hsearch restituisce NULL quando non riesce a completare un inserimento, quindi controlla ogni risultato di ENTER prima di proseguire. L’esempio gestisce gli errori di creazione e inserimento scrivendo un messaggio diagnostico su stderr, liberando una tabella già creata e restituendo uno stato di errore. Mantieni questi controlli vicino alle rispettive operazioni, così il codice successivo legge una voce solo dopo averne verificato il puntatore.

Liberare la tabella e comprenderne i limiti

Chiama hdestroy quando la tabella non serve più. La routine libera la tabella, ma spetta al chiamante gestire la memoria allocata dinamicamente per le chiavi o i valori a cui fanno riferimento le voci: conserva quei puntatori e libera separatamente le allocazioni di cui sei responsabile. L’esempio usa stringhe letterali, quindi non ha allocazioni di questo tipo da liberare. L’interfaccia POSIX mostrata non fornisce un’operazione per rimuovere una singola voce. Quando crei la tabella, scegli una capacità adeguata: il valore richiesto viene passato a hcreate e, nell’uso dell’interfaccia mostrato qui, non è disponibile un’operazione per ridimensionarla.