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);
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 maximum 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éussie.
L’argument item est du type ENTRY, qui est définie 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() et hcreate_r() peuvent échouer pour les raisons suivantes :
EINVAL (hcreate_r()) htab est NULL.
ENOMEM La table est pleine et action vaut ENTER.
ESRCH Le paramètre action vaut FIND et aucun élément n’a été trouvé
dans la table.
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.
CONFORMITÉ
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 maximum 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é keydans 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), feature_test_macros(7)
COLOPHON
Cette page fait partie de la publication 3.23 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
Cette page de manuel a été traduite et mise à jour par Christophe
Blaess <http://www.blaess.fr/christophe/> entre 1996 et 2003, puis par
Alain Portal <aportal AT univ-montp2 DOT fr> jusqu’en 2006, et mise à
disposition sur http://manpagesfr.free.fr/.
Les mises à jour et corrections de la version présente dans Debian sont
directement gérées par Florentin Duneau <fduneau@gmail.com> et l’équipe
francophone de traduction de Debian.
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> ».