Provided by: manpages-fr-dev_4.21.0-2_all 
NOM
hcreate, hdestroy, hsearch, hcreate_r, hdestroy_r, hsearch_r - Gestion de table de hachage
BIBLIOTHÈQUE
Bibliothèque C standard (libc, -lc)
SYNOPSIS
#include <search.h>
int hcreate(size_t nel);
void hdestroy(void);
ENTRY *hsearch(ENTRY item, ACTION action);
#define _GNU_SOURCE /* Consultez feature_test_macros(7) */
#include <search.h>
int hcreate_r(size_t nel, struct hsearch_data *htab);
void hdestroy_r(struct hsearch_data *htab);
int hsearch_r(ENTRY item, ACTION action, ENTRY **retval,
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 est positionné pour indiquer l'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, à savoir 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, ces fonctions positionnent errno pour indiquer l'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 spécifie seulement l'erreur ENOMEM.
ATTRIBUTS
Pour une explication des termes utilisés dans cette section, consulter attributes(7).
┌───────────────────────────────────────────────────────┬──────────────────────┬────────────────────────┐
│ Interface │ Attribut │ Valeur │
├───────────────────────────────────────────────────────┼──────────────────────┼────────────────────────┤
│ hcreate(), hsearch(), hdestroy() │ Sécurité des threads │ MT-Unsafe race:hsearch │
├───────────────────────────────────────────────────────┼──────────────────────┼────────────────────────┤
│ hcreate_r(), hsearch_r(), hdestroy_r() │ Sécurité des threads │ MT-Safe race:htab │
└───────────────────────────────────────────────────────┴──────────────────────┴────────────────────────┘
STANDARDS
Les fonctions hcreate(), hsearch() et hdestroy() viennent de SVr4, et sont décrites dans POSIX.1-2001 et
POSIX.1-2008.
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é al‐
loué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 ; ain‐
si 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.
EXEMPLES
Le programme suivant insère 24 éléments dans une table de hachage, puis affiche quelques-uns d'entre eux.
#include <search.h>
#include <stdio.h>
#include <stdlib.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;
ENTRY *ep;
hcreate(30);
for (size_t i = 0; i < 24; i++) {
e.key = data[i];
/* les données sont un entier et non un
pointeur vers quelque chose */
e.data = (void *) i;
ep = hsearch(e, ENTER);
/* il ne devrait pas y avoir d'échec */
if (ep == NULL) {
fprintf(stderr, "l'entrée a échoué\n");
exit(EXIT_FAILURE);
}
}
for (size_t i = 22; i < 26; i++) {
/* afficher deux entrées de la table et montrer qu'elles
ne sont pas dans la 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)
TRADUCTION
La traduction française de cette page de manuel a été créée par Christophe Blaess
<https://www.blaess.fr/christophe/>, Stéphan Rafin <stephan.rafin@laposte.net>, Thierry Vignaud <tvi‐
gnaud@mandriva.com>, François Micaux, Alain Portal <aportal@univ-montp2.fr>, Jean-Philippe Guérard <fe‐
vrier@tigreraye.org>, Jean-Luc Coulon (f5ibh) <jean-luc.coulon@wanadoo.fr>, Julien Cristau <jcristau@de‐
bian.org>, Thomas Huriaux <thomas.huriaux@gmail.com>, Nicolas François <nicolas.francois@centra‐
liens.net>, Florentin Duneau <fduneau@gmail.com>, Simon Paillard <simon.paillard@resel.enst-bretagne.fr>,
Denis Barbier <barbier@debian.org>, David Prévot <david@tilapin.org>, Jean-Baptiste Holcroft <jean-bap‐
tiste@holcroft.fr>, Grégoire Scano <gregoire.scano@malloc.fr> et Jean-Philippe MENGUAL <jpmengual@de‐
bian.org>
Cette traduction est une documentation libre ; veuillez vous reporter à la GNU General Public License
version 3 concernant les conditions de copie et de distribution. Il n'y a aucune RESPONSABILITÉ LÉGALE.
Si vous découvrez un bogue dans la traduction de cette page de manuel, veuillez envoyer un message à de‐
bian-l10n-french@lists.debian.org.
Pages du manuel de Linux 6.03 15 décembre 2022 hsearch(3)