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 /* Consultez feature_test_macros(7) */
#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 à 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 maximal 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éussit.
L'argument
item est du type
ENTRY, qui est défini 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. En cas d'erreur, 0 est renvoyé et
errno contient
le code d'erreur.
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.En
cas d'erreur de ces fonctions,
errno contient le code d'erreur.
ERREURS¶
hcreate_r() et
hdestroy_r() peuvent échouer pour les
raisons suivantes :
- EINVAL
- htab est NULL.
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.
ATTRIBUTS¶
Multithreading (voir pthreads(7))¶
Les fonctions
hcreate(),
hsearch() et
hdestroy() ne sont
pas sûres dans un contexte multithread car elles utilisent un espace
global pour stocker la table.
Les fonctions
hcreate_r(),
hsearch_r() et
hdestroy_r() sont
sûres dans un contexte multithread.
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 maximal
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é
key dans 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>
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, *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)
COLOPHON¶
Cette page fait partie de la publication 3.65 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¶
Depuis 2010, cette traduction est maintenue à l'aide de l'outil po4a
<
http://po4a.alioth.debian.org/> par l'équipe de traduction
francophone au sein du projet perkamon
<
http://perkamon.alioth.debian.org/>.
Christophe Blaess <
http://www.blaess.fr/christophe/> (1996-2003), Alain
Portal <
http://manpagesfr.free.fr/> (2003-2006). Florentin Duneau et
l'équipe francophone de traduction de Debian (2006-2009).
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> ».
