Implémenter le dictionnaire en C

ISO C ne définit pas de type dictionnaire intégré. Si votre environnement cible fournit l’interface POSIX hsearch, ses routines de table de hachage permettent de stocker et de retrouver des entrées clé-valeur. L’exemple ci-dessous crée une table, y insère deux entrées, recherche une clé présente et une clé absente, vérifie les pointeurs renvoyés, puis libère la table. Il illustre une approche parmi d’autres conceptions possibles de dictionnaire.

Utiliser les routines POSIX hsearch pour implémenter un dictionnaire en C

hcreate, hsearch et hdestroy sont des routines POSIX déclarées dans <search.h>, et non des fonctions de la bibliothèque ISO C. Leur disponibilité dépend du système d’exploitation et de la bibliothèque C cibles ; vérifiez donc que votre environnement fournit cette interface avant d’utiliser l’exemple. La spécification POSIX de hcreate et hsearch définit l’interface et permet d’en consulter les exigences. Le paquet ne précise ni plateforme ni version de bibliothèque.

Créer une table de hachage et ajouter des entrées avec hcreate et hsearch

Appelez hcreate une seule fois pour créer une table de la capacité demandée. La fonction renvoie une valeur non nulle en cas de réussite et zéro si elle ne peut pas créer la table. ENTRY contient une clé de type char * et un pointeur de données de type void *. Passez à hsearch une valeur ENTRY et une valeur ACTION : ENTER demande une insertion, tandis que FIND demande une recherche. En cas de réussite, l’appel renvoie un pointeur vers une entrée ; en cas d’échec, il renvoie NULL.

Exécutez cet exemple :

Le code et les libellés ou sorties affichés dans cette section restent en anglais.

#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

Rechercher des clés et gérer les entrées absentes

Le premier appel à FIND recherche language, que le programme a insérée avec la valeur C ; le second recherche compiler, qui n’a pas été insérée. Chaque résultat est vérifié avant que le programme lise le champ data : si le résultat vaut NULL, le chemin « introuvable » est donc traité sans risque. Si la recherche d’une clé qui devrait exister renvoie NULL, l’exemple évite tout de même de déréférencer le pointeur et signale le résultat. Adaptez les messages ou la politique de retour à votre application.

hsearch renvoie aussi NULL lorsqu’une insertion ne peut pas aboutir ; vérifiez donc chaque résultat de ENTER avant de poursuivre. En cas d’échec de création ou d’insertion, l’exemple écrit un diagnostic sur stderr, libère la table si elle a déjà été créée, puis renvoie un code d’échec. Effectuez ces vérifications près de chaque opération afin que le code suivant ne lise une entrée qu’après avoir confirmé la validité de son pointeur.

Libérer la table et comprendre ses limites

Appelez hdestroy lorsque vous n’avez plus besoin de la table. Cette fonction libère la table, mais l’appelant reste responsable de la mémoire allouée dynamiquement pour les clés ou les valeurs référencées par les entrées ; conservez ces pointeurs et libérez séparément les allocations dont vous êtes responsable. L’exemple utilise des chaînes littérales, il n’a donc aucune allocation de ce type à libérer. L’interface POSIX présentée ici ne fournit pas d’opération pour supprimer une entrée individuelle. Choisissez une capacité suffisante lors de la création de la table : la capacité demandée est transmise à hcreate, et cette interface ne propose pas d’opération de redimensionnement dans le déroulement présenté.