Provided by:
manpages-fr-dev_3.27fr1.4-1_all 
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);
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 reussie.
L'argument item est du type ENTRY, qui est definie dans <search.h>
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 RENVOY'EE
hcreate() et hcreate_r() renvoient une valeur non nulle en cas de
succes, zero sinon.
En cas de succes, hsearch renvoie un pointeur vers une entree de la
table de hachage. Elle renvoie NULL en cas d'erreur ou 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.
ERREURS
hcreate() et hcreate_r() peuvent echouer pour les raisons suivantes :
EINVAL (hcreate_r()) htab est NULL.
ENOMEM La table est pleine et action vaut ENTER.
ESRCH Le parametre action vaut FIND et aucun element n'a ete trouve
dans la table.
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-2001 specifie seulement l'erreur ENOMEM.
CONFORMIT'E
Les fonctions hcreate(), hsearch() et hdestroy() viennent de SVr4, et
sont decrites dans POSIX.1-2001. Les fonctions hcreate_r(), hsearch_r()
et hdestroy_r() sont des extensions 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 keydans ce cas.
Les entrees ne peuvent etre qu'ajoutees dans la table, on ne peut pas
les supprimer individuellement.
EXEMPLE
Le programme suivant insere 24 elements 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.27 du projet man-pages
Linux. Une description du projet et des instructions pour signaler des
anomalies peuvent etre trouvees a l'adresse
<URL:http://www.kernel.org/doc/man-pages/>.
TRADUCTION
Depuis 2010, cette traduction est maintenue a l'aide de l'outil po4a
<URL:http://po4a.alioth.debian.org/> par l'equipe de traduction
francophone au sein du projet perkamon
<URL:http://perkamon.alioth.debian.org/>.
Christophe Blaess <URL:http://www.blaess.fr/christophe/> (1996-2003),
Alain Portal <URL:http://manpagesfr.free.fr/> (2003-2006). Florentin
Duneau et l'equipe francophone de traduction de Debian (2006-2009).
Veuillez signaler toute erreur de traduction en ecrivant a
<debian-l10n-french@lists.debian.org> ou par un rapport de bogue sur le
paquet manpages-fr.
Vous pouvez toujours avoir acces a la version anglaise de ce document
en utilisant la commande << man -L C <section> <page_de_man> >>.