HSEARCH(3) Manuel du programmeur Linux HSEARCH(3) NOM hsearch, hcreate, hdestroy - Gestion de table de hachage. SYNOPSIS #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); DESCRIPTION Les trois fonctions hcreate, hsearch, et hdestroy permettent l'util- isateur de ceer une table (une seule la fois) de hachage du type ENTRY (definie dans <search.h>) qui associe une cl avec des donnes quelconques. Les fonctions hcreate_r, hsearch_r, hdestroy_r sont des versions rentrantes qui permettent d'utiliser plusieurs tables simul- tanment. La table doit d'abord tre cre avec la fonction hcreate(). nel est une estimation du nombre d'lments dans la table. La fonction hcreate() permet d'augmenter cette valeur, afin d'amliorer les per- formances de la table de hachage. La fonction hdestroy() libre la mmoire occupe par la table, afin de pouvoir en construire une nouvelle. L'argument item est du type ENTRY, qui est dfinie dans <search.h> ainsi: typedef struct entry { char *key; void *data; } ENTRY; Le champ key pointe sur une chane de caractres ASCII termine par un caractre nul. Cette chane est la cl de recherche. Le champ data pointe sur les donnes associes cette cl. La fonction hsearch() recherche dans la table un lment associ la mme cl que item (compares avec strcmp(3)), et si elle russit, elle renvoie un pointeur sur cet lment. Le paramtre action dtermine ce que fera hsearch() si la recherche est infructueuse. Si action vaut ENTER alors hsearch() insrera une copie de item. Si action vaut FIND alors elle renverra NULL. VALEUR RENVOYE hcreate() et hcreate_r renvoie zro si la table ne peut PAS tre installe. 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 zro si action est ENTER et si la table de hachage est pleine, ou zro sinon. ERREURS ENOMEM Plus de mmoire. CONFORMIT Les fonctions hcreate, hsearch, et hdestroy viennent de SVID, et sont dcrites dans POSIX 1003.1-2001. Les fonctions hcreate_r, hsearch_r, hdestroy_r sont des extensions GNU. BOGUES SVID et POSIX 1003.1-2001 prcisent que action n'est significative que pour les recherches infructueuses ; ainsi ENTER ne devrait avoir aucune influence pour une recherche russie. Les implmentations libC et GlibC mettent jour data de la cl key fournie dans ce cas. Les entres ne peuvent tre qu'ajoutes dans la table, on ne peut pas les supprimer individuellement. EXEMPLE Le programme suivant insre 24 lments 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(1,3x,1 builtins)", "foxtrot", "golf", "hotel", "india" "juliette", "kilo", "lima", "mike", "novembre", "oscar", "papa", "quebec", "romeo", "sierra", "tango", "uniforme", "victor", "whisky", "x-ray", "yankee" "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 donnes sont de simples entiers, pas des pointeur */ e.data = (char *)i; ep = hsearch(e, ENTER); /* Il ne devrait pas y avoir d'chec */ if(3,n) (ep == NULL) { fprintf (stderr, "Echec\n"); exit(3,n,1 builtins)(1); } } for (i = 22; i < 26; i++) { /* Afficher 2 entres, et vrifier que 2 autres sont absentes */ e.key = data[i]; ep = hsearch(e, FIND); printf(1,3,1 builtins) ("%9.9s -> %9.9s:%d\n", e.key, ep?ep->key:"NULL", ep ? (int)(ep->data) : 0); } return (0); } VOIR AUSSI bsearch(3), lsearch(3,n)(3), malloc(3) TRADUCTION Christophe Blaess, 1996-2003. LDP 21 juillet 2003 HSEARCH(3)