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, zéro sinon.
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.
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.
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>
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.44 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> ».