hsearch(3) Library Functions Manual hsearch(3) NOM hcreate, hdestroy, hsearch, hcreate_r, hdestroy_r, hsearch_r - Gestion de table de hachage BIBLIOTHEQUE Bibliotheque C standard (libc, -lc) SYNOPSIS #include int hcreate(size_t nel); void hdestroy(void); ENTRY *hsearch(ENTRY item, ACTION action); #define _GNU_SOURCE /* Consultez feature_test_macros(7) */ #include int hcreate_r(size_t nel, struct hsearch_data *htab); void hdestroy_r(struct hsearch_data *htab); int hsearch_r(ENTRY item, ACTION action, ENTRY **retval, struct hsearch_data *htab); DESCRIPTION Les trois fonctions hcreate(), hsearch() et hdestroy() permettent a l'utilisateur de creer et de gerer une table de hachage qui associe une cle (une chaine de caracteres) avec des donnees quelconques. Une seule table de hachage peut etre utilisee a la fois avec ces fonctions. Les fonctions hcreate_r(), hsearch_r() et hdestroy_r() sont des versions reentrantes qui permettent d'utiliser plusieurs tables en meme temps. Le dernier argument htab pointe vers une structure qui identifie la table a utiliser. Le programmeur doit traiter la structure comme opaque (par exemple, il est impossible d'acceder ou de modifier la table de hachage depuis cette structure). La table doit d'abord etre creee avec hcreate(). L'argument nel est le nombre maximal d'elements de la table (le maximum ne peut pas etre change pas la suite). L'implementation peut decider d'augmenter cette valeur, afin d'ameliorer les performances de la table de hachage. hcreate_r() effectue la meme tache que hcreate() mais pour les tables decrites par la structure *htab. La structure pointee par htab doit etre initialisee avec des zeros avant le premier appel a hcreate_r(). La fonction hdestroy() libere la memoire occupee par la table de hachage creee par hcreate(). Apres un appel a hdestroy(), une nouvelle table de hachage peut etre creee avec hcreate(). La fonction hdestroy_r() effectue la meme tache pour une table de hachage decrite par *htab, qui a ete prealablement creee par hcreate_r(). hsearch() cherche dans la table de hachage un element dont la cle est la meme que item (au sens de strcmp(3)), et retourne un pointeur sur cet element si la recherche reussit. L'argument item est du type ENTRY, qui est defini dans ainsi : typedef struct entry { char *key; void *data; } ENTRY; Le champ key pointe vers une chaine terminee par un caractere nul qui est la cle cherchee. Le champ data pointe vers les donnees associees a la cle. Le parametre action determine ce que doit faire hsearch() apres une recherche infructueuse. Si action est egal a ENTER, alors une copie de item est inseree et un pointeur sur ce nouvel element est renvoye. Si action est egal a FIND, NULL est renvoye et data est ignore. hsearch_r() est similaire a hsearch(), mais elle opere sur la table de hachage decrite par *htab, et le pointeur de l'objet trouve est renvoye dans *retval et non dans la valeur de retour de la fonction. VALEUR RENVOYEE hcreate() et hcreate_r() renvoient une valeur non nulle en cas de succes. En cas d'erreur, 0 est renvoye et errno est positionne pour indiquer l'erreur. En cas de succes, hsearch renvoie un pointeur vers une entree de la table de hachage. Elle renvoie NULL en cas d'erreur, a savoir si action est egal a ENTER et la table de hachage pleine, ou si action est egal a FIND et item ne peut pas etre trouve. hsearch_r() renvoie une valeur non nulle en cas de succes et zero en cas d'erreur. En cas d'erreur, ces fonctions positionnent errno pour indiquer l'erreur. ERREURS hcreate_r() et hdestroy_r() peuvent echouer pour les raisons suivantes : EINVAL htab est NULL. hsearch et hsearch_r peuvent echouer pour les raisons suivantes : ENOMEM action est ENTER, key n'a pas ete trouve dans la table, et il n'y a plus de place dans la table pour ajouter un nouvel element. ESRCH action vaut FIND et key n'a pas ete trouve dans la table. POSIX.1 specifie seulement l'erreur ENOMEM. ATTRIBUTS Pour une explication des termes utilises dans cette section, consulter attributes(7). +------------------+--------------------------+------------------------+ |Interface | Attribut | Valeur | +------------------+--------------------------+------------------------+ |hcreate(), | Securite des threads | MT-Unsafe race:hsearch | |hsearch(), | | | |hdestroy() | | | +------------------+--------------------------+------------------------+ |hcreate_r(), | Securite des threads | MT-Safe race:htab | |hsearch_r(), | | | |hdestroy_r() | | | +------------------+--------------------------+------------------------+ STANDARDS hcreate() hsearch() hdestroy() POSIX.1-2008. hcreate_r() hsearch_r() hdestroy_r() GNU. HISTORIQUE hcreate() hsearch() hdestroy() SVr4, POSIX.1-2001. hcreate_r() hsearch_r() hdestroy_r() GNU. NOTES L'implementation des tables de hachage est generalement plus efficace lorsque la table possede assez d'espace libre pour minimiser les collisions. Typiquement, cela signifie que nel devrait etre 25 % plus large que le nombre maximal d'elements que l'on souhaite enregistrer dans la table. Les fonctions hdestroy() et hdestroy_r() ne liberent pas les tampons pointes par les elements key et data de la table de hachage. Elles ne peuvent pas le faire car elles ne savent pas ou ces tampons ont ete alloues dynamiquement. Si ces tampons doivent etre liberes (peut-etre car le programme cree et supprime des tables de hachage de facon repetitive, au lieu de creer un seule table pour toute la vie du programme), alors le programme doit maintenir la liste des tampons liberables. BOGUES SVr4 et POSIX.1-2001 precisent que action n'est significatif que pour les recherches infructueuses ; ainsi ENTER ne devrait avoir aucune influence pour une recherche reussie. Les implementations libc et glibc (anterieure a la 2.3) ne suivaient pas les specifications car elles mettaient a jour les donnees data de la cle key dans ce cas. Les entrees ne peuvent etre qu'ajoutees dans la table, on ne peut pas les supprimer individuellement. EXEMPLES Le programme suivant insere 24 elements dans une table de hachage, puis affiche quelques-uns d'entre eux. #include #include #include static 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; ENTRY *ep; hcreate(30); for (size_t i = 0; i < 24; i++) { e.key = data[i]; /* les donnees sont des entiers et non un pointeur vers quelque chose */ e.data = (void *) i; ep = hsearch(e, ENTER); /* il ne devrait pas y avoir d'echec */ if (ep == NULL) { fprintf(stderr, "l'entree a echoue\n"); exit(EXIT_FAILURE); } } for (size_t i = 22; i < 26; i++) { /* afficher deux entrees de la table et montrer qu'elles ne sont pas dans la 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) TRADUCTION La traduction francaise de cette page de manuel a ete creee par Christophe Blaess , Stephan Rafin , Thierry Vignaud , Francois Micaux, Alain Portal , Jean-Philippe Guerard , Jean-Luc Coulon (f5ibh) , Julien Cristau , Thomas Huriaux , Nicolas Francois , Florentin Duneau , Simon Paillard , Denis Barbier , David Prevot , Jean-Baptiste Holcroft , Gregoire Scano et Jean-Philippe MENGUAL Cette traduction est une documentation libre ; veuillez vous reporter a la GNU General Public License version 3 concernant les conditions de copie et de distribution. Il n'y a aucune RESPONSABILITE LEGALE. Si vous decouvrez un bogue dans la traduction de cette page de manuel, veuillez envoyer un message a . Pages du manuel de Linux 6.06 31 octobre 2023 hsearch(3)