Editer un article - Informaticien.be

Editer un article

Titre
Mots Clés
Texte	[size=18] [b]Nom[/b] [/size] hsearch, hcreate, hdestroy - Gestion de table de hachage. [size=18] [b]Résumé[/b] [/size] [b]#include <search.h>[/b] [b][i]ENTRY hsearch (ENTRY item , ACTION action );[/i][/b] [b][i]int hcreate (unsigned nel );[/i][/b] [b]void hdestroy (void);[/b] 2 [b]#define _GNU_SOURCE[/b] [b][/b] [b]#include <search.h>[/b] [b][i]int hcreate_r(size_t nel , struct hsearch_data tab );[/i][/b] [b][i]int hsearch_r(ENTRY item , ACTION action ,[/i][/b] [b][i]ENTRY * ret , struct hsearch_data * tab );[/i][/b] [b][i]void hdestroy_r(struct hsearch_data * tab );[/i][/b] [size=18] [b]Description[/b] [/size] Les trois fonctions [b]hcreate ,[/b] [b]hsearch ,[/b] et [b]hdestroy[/b] permettent à l'utilisateur de céeer une table (une seule à la fois) de hachage du type [i]ENTRY[/i] (definie dans [b]<search.h>[/b]) qui associe une clé avec des données quelconques. Les fonctions [b]hcreate_r ,[/b] [b]hsearch_r ,[/b] [b]hdestroy_r[/b] sont des versions réentrantes qui permettent d'utiliser plusieurs tables simultanément. La table doit d'abord être créée avec la fonction [b]hcreate()[/b]. [i]nel[/i] est une estimation du nombre d'éléments dans la table. La fonction [b]hcreate()[/b] permet d'augmenter cette valeur, afin d'améliorer les performances de la table de hachage. La fonction [i]hdestroy()[/i] libère la mémoire occupée par la table, afin de pouvoir en construire une nouvelle. L'argument [i]item[/i] est du type [b]ENTRY[/b], qui est définie dans [i]<search.h>[/i] ainsi: .nf typedef struct entry { char [i]key[/i]; void [i]data[/i]; } ENTRY; .fi Le champ [i]key[/i] 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 [i]data[/i] pointe sur les données associées à cette clé. La fonction [b]hsearch()[/b] recherche dans la table un élément associé à la même clé que [i]item[/i] (comparées avec [b]strcmp (3)),[/b] et si elle réussit, elle renvoie un pointeur sur cet élément. Le paramètre [i]action[/i] détermine ce que fera [b]hsearch()[/b] si la recherche est infructueuse. Si [i]action[/i] vaut [b]ENTER[/b] alors [b]hsearch()[/b] insèrera une copie de [i]item[/i]. Si [i]action[/i] vaut [b]FIND[/b] alors elle renverra [b]NULL[/b]. [size=18] [b]Valeur renvoyée[/b] [/size] [b]hcreate()[/b] et [b]hcreate_r[/b] renvoie zéro si la table ne peut PAS être installée.     [b]hsearch()[/b] renvoie [i]NULL[/i] si l'action est [i]ENTER[/i] et si la table est pleine ou si l'action est [i]FIND[/i] et si l'[i]item[/i] n'est pas trouvé dans la table.     [b]hsearch_r()[/b] renvoie zéro si [i]action[/i] est [b]ENTER[/b] et si la table de hachage est pleine, ou zéro sinon. [size=18] [b]Erreurs[/b] [/size] [b]ENOMEM[/b] [table][row][col]    [/col][col]Plus de mémoire.[/col][/row][/table] [size=18] [b]Conformité[/b] [/size] Les fonctions [b]hcreate ,[/b] [b]hsearch ,[/b] et [b]hdestroy[/b] viennent de SVID, et sont décrites dans POSIX 1003.1-2001. Les fonctions [b]hcreate_r ,[/b] [b]hsearch_r ,[/b] [b]hdestroy_r[/b] sont des extensions GNU. [size=18] [b]Bugs[/b] [/size] SVID et POSIX 1003.1-2001 précisent que [i]action[/i] 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 [i]data[/i] de la clé [i]key[/i] fournie dans ce cas.     Les entrées ne peuvent être qu'ajoutées dans la table, on ne peut pas les supprimer individuellement. [size=18] [b]Exemple[/b] [/size] Le programme suivant insère 24 éléments dans une table de hachage, puis affiche quelques uns d'entre-eux. .nf #include <stdio.h> #include <search.h> char data[]= { "alpha", "bravo", "charlie", "delta", "echo", "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 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 "); 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 ", e.key, ep?ep->key:"NULL", ep ? (int)(ep->data) : 0); } return (0); } .fi [size=18] [b]Voir aussi[/b] [/size] [b]bsearch (3),[/b] [b]lsearch (3),[/b] [b]malloc (3)[/b] [size=18] [b]Traduction[/b] [/size] Christophe Blaess, 1996-2003.
Fichier