Loading

NOM

       hcreate,  hdestroy, hsearch, hcreate_r, hdestroy_r, hsearch_r - Gestion
       de table de hachage.

SYNOPSIS

       #include <search.h>

       int hcreate(size_t nel);

       ENTRY *hsearch(ENTRY item, ACTION action);

       void hdestroy(void);

       #define _GNU_SOURCE
       #include <search.h>

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

       int hsearch_r(ENTRY item, ACTION action, ENTRY **retval,
                     struct hsearch_data *htab);

       void hdestroy_r(struct hsearch_data *htab);

       Les trois fonctions hcreate(), hsearch()  et  hdestroy()  permettent  à
       l’utilisateur de créer et de gérer une table de hachage qui associe une
       clé (une chaîne de caractères) avec des données quelconques. Une  seule
       table de hachage peut être utilisée à la fois avec ces fonctions.

       Les   fonctions  hcreate_r(),  hsearch_r()  et  hdestroy_r()  sont  des
       versions ré-entrantes qui permettent  d’utiliser  plusieurs  tables  en
       même  temps.  Le  dernier  argument  htab pointe vers une structure qui
       identifie la table à utiliser. Le programmeur doit traiter la structure
       comme  opaque  (par exemple, il est impossible d’accéder ou de modifier
       la table de hachage depuis cette structure).

       La table doit d’abord être créée avec hcreate(). L’argument nel est  le
       nombre  maximum  d’éléments  de  la  table (le maximum ne peut pas être
       changé pas la suite). L’implémentation peut décider  d’augmenter  cette
       valeur, afin d’améliorer les performances de la table de hachage.

       hcreate_r()  effectue  la même tâche que hcreate() mais pour les tables
       décrites par la structure *htab. La structure  pointée  par  htab  doit
       être initialisée avec des zéros avant le premier appel à hcreate_r().

       La  fonction  hdestroy()  libère  la  mémoire  occupée  par la table de
       hachage créée par hcreate(). Après un appel à hdestroy(), une  nouvelle
       table   de   hachage  peut  être  créée  avec  hcreate().  La  fonction
       hdestroy_r() effectue la même tâche pour une table de  hachage  décrite
       par *htab, qui a été préalablement créée par hcreate_r().

       hsearch()  cherche  dans la table de hachage un élément dont la clé est
       la même que item (au sens de strcmp(3)), et retourne  un  pointeur  sur
       cet élément si la recherche réussie.

       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 vers une chaîne terminée par un caractère  nul  qui
       est  la clé cherchée. Le champ data pointe vers les données associées à
       la clé.

       Le paramètre action détermine ce que doit  faire  hsearch()  après  une
       recherche  infructueuse. Si action est égal à ENTER, alors une copie de
       item est insérée et un pointeur sur ce nouvel élément est  renvoyé.  Si
       action est égal à FIND, NULL est renvoyé et data est ignoré.

       hsearch_r()  est similaire à hsearch(), mais elle opère sur la table de
       hachage décrite par *htab, et le pointeur de l’objet trouvé est renvoyé
       dans *retval et non dans la valeur de retour de la fonction.

VALEUR RENVOYÉE

       hcreate()  et  hcreate_r()  renvoient  une  valeur  non nulle en cas de
       succès, zéro sinon.

       En cas de succès, hsearch renvoie un pointeur vers  une  entrée  de  la
       table  de  hachage.  Elle renvoie NULL en cas d’erreur ou si action est
       égal à ENTER, et la table de hachage pleine, ou  si action est  égal  à
       FIND,  et  item ne peut pas être trouvé. hsearch_r() renvoie une valeur
       non nulle en cas de succès et zéro en cas d’erreur.

ERREURS

       hcreate() et hcreate_r() peuvent échouer pour les raisons suivantes :

       EINVAL (hcreate_r())  htab est NULL.

       ENOMEM La table est pleine et action vaut ENTER.

       ESRCH  Le paramètre action vaut FIND et aucun élément  n’a  été  trouvé
              dans la table.

       hsearch et hsearch_r peuvent échouer pour les raisons suivantes :

       ENOMEM action  est  ENTER,  key n’a pas été trouvé dans la table, et il
              n’y a plus de  place  dans  la  table  pour  ajouter  un  nouvel
              élément.

       ESRCH  action vaut FIND et key n’a pas été trouvé dans la table.

       POSIX.1-2001 spécifie seulement l’erreur ENOMEM.

CONFORMITÉ

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

NOTES

       L’implémentation  des  tables de hachage est généralement plus efficace
       lorsque la table  possède  assez  d’espace  libre  pour  minimiser  les
       collisions.  Typiquement,  cela signifie que nel devrait être 25 % plus
       large que le nombre maximum d’éléments que  l’on  souhaite  enregistrer
       dans la table.

       Les  fonctions  hdestroy()  et hdestroy_r() ne libèrent pas les tampons
       pointés par les éléments key et data de la table de hachage.  Elles  ne
       peuvent  pas  le  faire  car elles ne savent pas où ces tampons ont été
       alloués dynamiquement. Si ces tampons doivent être  libérés  (peut-être
       car  le  programme  crée  et  supprime  des  tables de hachage de façon
       répétitive, au lieu de créer un  seule  table  pour  toute  la  vie  du
       programme),  alors  le  programme  doit  maintenir la liste des tampons
       libérables.

BOGUES

       SVr4 et POSIX.1-2001 précisent que action n’est significatif  que  pour
       les  recherches  infructueuses ;  ainsi  ENTER  ne devrait avoir aucune
       influence pour une recherche réussie. Les implémentations libc et glibc
       (antérieure  à  la  2.3)  ne suivaient pas les spécifications car elles
       mettaient à jour les données data de la clé keydans ce cas.

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

EXEMPLE

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

       #include <stdio.h>
       #include <stdlib.h>
       #include <search.h>

       char *data[] = { "alpha", "bravo", "charlie", "delta",
            "echo", "foxtrot", "golf", "hotel", "india", "juliet",
            "kilo", "lima", "mike", "november", "oscar", "papa",
            "quebec", "romeo", "sierra", "tango", "uniform",
            "victor", "whisky", "x-ray", "yankee", "zulu"
       };

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

           hcreate(30);

           for (i = 0; i < 24; i++) {
               e.key = data[i];
               /* data is just an integer, instead of a
                  pointer to something */
               e.data = (void *) i;
               ep = hsearch(e, ENTER);
               /* there should be no failures */
               if (ep == NULL) {
                   fprintf(stderr, "entry failed\n");
                   exit(EXIT_FAILURE);
               }
           }

           for (i = 22; i < 26; i++) {
               /* print two entries from the table, and
                  show that two are not in the table */
               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);
           }
           hdestroy();
           exit(EXIT_SUCCESS);
       }

VOIR AUSSI

       bsearch(3), lsearch(3), malloc(3), tsearch(3), feature_test_macros(7)

COLOPHON

       Cette page fait partie de  la  publication  3.23  du  projet  man-pages
       Linux.  Une description du projet et des instructions pour signaler des
       anomalies      peuvent      être       trouvées       à       l’adresse
       http://www.kernel.org/doc/man-pages/.

TRADUCTION

       Cette  page  de  manuel  a  été  traduite et mise à jour par Christophe
       Blaess <http://www.blaess.fr/christophe/> entre 1996 et 2003, puis  par
       Alain  Portal  <aportal AT univ-montp2 DOT fr> jusqu’en 2006, et mise à
       disposition sur http://manpagesfr.free.fr/.

       Les mises à jour et corrections de la version présente dans Debian sont
       directement gérées par Florentin Duneau <fduneau@gmail.com> et l’équipe
       francophone de traduction de Debian.

       Veuillez  signaler  toute  erreur   de   traduction   en   écrivant   à
       <debian-l10n-french@lists.debian.org> ou par un rapport de bogue sur le
       paquet manpages-fr.

       Vous pouvez toujours avoir accès à la version anglaise de  ce  document
       en utilisant la commande « man -L C <section> <page_de_man> ».