hsearch(3) Library Functions Manual hsearch(3)
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 ver-
sions 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 ha-
chage créée par hcreate(). Après un appel à hdestroy(), une nouvelle
table de hachage peut être créée avec hcreate(). La fonction hdes-
troy_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 re-
cherche 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() and hcreate_r() return nonzero on success. They return 0 on
error, with errno set to indicate the error.
On success, hsearch() returns a pointer to an entry in the hash table.
hsearch() returns NULL on error, that is, if action is ENTER and the
hash table is full, or action is FIND and item cannot be found in the
hash table. hsearch_r() returns nonzero on success, and 0 on error. In
the event of an error, these two functions set errno to indicate the
error.
ERREURS
hcreate_r() et hdestroy_r() peuvent échouer pour les raisons sui-
vantes :
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(), │ Sécurité des threads │ MT-Unsafe race:hsearch │
│hdestroy() │ │ │
├──────────────────────┼──────────────────────┼────────────────────────┤
│hcreate_r(), │ Sécurité des threads │ MT-Safe race:htab │
│hsearch_r(), │ │ │
│hdestroy_r() │ │ │
└──────────────────────┴──────────────────────┴────────────────────────┘
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 exten-
sions 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 colli-
sions. 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éti-
tive, 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 and POSIX.1-2001 specify that action is significant only for un-
successful searches, so that an ENTER should not do anything for a suc-
cessful search. In libc and glibc (before glibc 2.3), the implementa-
tion violates the specification, updating the data for the given key in
this case.
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];
/* 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 (size_t 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)
TRADUCTION
La traduction française de cette page de manuel a été créée par Chris-
tophe Blaess <https://www.blaess.fr/christophe/>, Stéphan Rafin <ste-
phan.rafin@laposte.net>, Thierry Vignaud <tvignaud@mandriva.com>, Fran-
çois Micaux, Alain Portal <aportal@univ-montp2.fr>, Jean-Philippe Gué-
rard <fevrier@tigreraye.org>, Jean-Luc Coulon (f5ibh) <jean-luc.cou-
lon@wanadoo.fr>, Julien Cristau <jcristau@debian.org>, Thomas Huriaux
<thomas.huriaux@gmail.com>, Nicolas François <nicolas.francois@centra-
liens.net>, Florentin Duneau <fduneau@gmail.com>, Simon Paillard <si-
mon.paillard@resel.enst-bretagne.fr>, Denis Barbier <barbier@de-
bian.org>, David Prévot <david@tilapin.org>, Jean-Baptiste Holcroft
<jean-baptiste@holcroft.fr> et Grégoire Scano <gregoire.scano@mal-
loc.fr>
Cette traduction est une documentation libre ; veuillez vous reporter à
la GNU General Public License version 3
⟨https://www.gnu.org/licenses/gpl-3.0.html⟩ 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 à ⟨debian-l10n-french@lists.debian.org⟩.
Pages du manuel de Linux 6.03 15 décembre 2022 hsearch(3)
Generated by dwww version 1.15 on Sat Jun 29 00:27:05 CEST 2024.