hsearch, hcreate, hdestroy − Gestion de table de hachage.

#include <search.h>

ENTRY *hsearch (ENTRY item, ACTION action);

int hcreate (unsigned nel);

void hdestroy (void);

#define _GNU_SOURCE
#include <search.h>

int hcreate_r(size_t nel, struct hsearch_data *tab);

int *hsearch_r(ENTRY item, ACTION action, ENTRY **ret, struct hsearch_data *tab);

void hdestroy_r(struct hsearch_data *tab);

Les trois fonctions hcreate, hsearch, et hdestroy permettent à l’utilisateur de céeer une table (une seule à la fois) de hachage du type ENTRY (definie dans <search.h>) qui associe une clé avec des données quelconques. Les fonctions hcreate_r, hsearch_r, hdestroy_r sont des versions réentrantes qui permettent d’utiliser plusieurs tables simultanément.

La table doit d’abord être créée avec la fonction hcreate(). nel est une estimation du nombre d’éléments dans la table. La fonction hcreate() permet d’augmenter cette valeur, afin d’améliorer les performances de la table de hachage.

La fonction hdestroy() libère la mémoire occupée par la table, afin de pouvoir en construire une nouvelle.

L’argument item est du type ENTRY, qui est définie dans <search.h> ainsi:

  typedef struct entry {
      char *key;
      void *data;
  } ENTRY;

Le champ key pointe sur une chaîne de caractères ASCII terminée par un caractère nul. Cette chaîne est la clé de recherche. Le champ data pointe sur les données associées à cette clé. La fonction hsearch() recherche dans la table un élément associé à la même clé que item (comparées avec strcmp(3)), et si elle réussit, elle renvoie un pointeur sur cet élément. Le paramètre action détermine ce que fera hsearch() si la recherche est infructueuse. Si action vaut ENTER alors hsearch() insèrera une copie de item. Si action vaut FIND alors elle renverra NULL.

hcreate() et hcreate_r renvoie zéro si la table ne peut PAS être installée.

hsearch() renvoie NULL si l’action est ENTER et si la table est pleine ou si l’action est FIND et si l’item n’est pas trouvé dans la table.

hsearch_r() renvoie zéro si action est ENTER et si la table de hachage est pleine, ou zéro sinon.

ENOMEM

Plus de mémoire.

Les fonctions hcreate, hsearch, et hdestroy viennent de SVID, et sont décrites dans POSIX 1003.1-2001. Les fonctions hcreate_r, hsearch_r, hdestroy_r sont des extensions GNU.

SVID et POSIX 1003.1-2001 précisent que action n’est significative que pour les recherches infructueuses ; ainsi ENTER ne devrait avoir aucune influence pour une recherche réussie. Les implémentations libC et GlibC mettent à jour data de la clé key fournie dans ce cas.

Les entrées ne peuvent être qu’ajoutées dans la table, on ne peut pas les supprimer individuellement.

Le programme suivant insère 24 éléments dans une table de hachage, puis affiche quelques uns d’entre-eux.

  #include <stdio.h>
  #include <search.h>
  char *data[]= { "alpha",   "bravo",  "charlie", "delta",    "echo",
                  "foxtrot", "golf",   "hotel",   "inde",    "juliette",
                  "kilo",    "lima",   "mike",    "novembre", "oscar",
                  "papa",    "quebec", "romeo",   "sierra",   "tango",
                  "uniforme", "victor", "whisky",  "x-ray",    "rikain",
                  "zoulou"
  };

int
main ()
{
    ENTRY e, *ep;
    int i;

   /* On commence avec une petite table, qu’on agrandit ensuite */

   hcreate(30);
    for (i = 0; i < 24; i++) {
        e.key = data[i];
        /* Les données sont de simples entiers, pas des pointeur */
        e.data = (char *)i;
        ep = hsearch(e, ENTER);
        /* Il ne devrait pas y avoir d’échec */
        if (ep == NULL) {
            fprintf (stderr, "Echec\n");

exit(1);

}

}
for (i = 22; i < 26; i++) {
/* Afficher 2 entrées, et vérifier que 2 autres sont absentes */
e.key = data[i];
ep = hsearch(e, FIND);
printf ("%9.9s -> %9.9s:%d\n", e.key,

ep?ep->key:"NULL",

ep ? (int)(ep->data) : 0);
}
return (0);
}

bsearch(3), lsearch(3), malloc(3)

Christophe Blaess, 1997.