hcreate, hdestroy, hsearch, hcreate_r, hdestroy_r, hsearch_r - Gestion de table
de hachage
Bibliothèque C standard (
libc,
-lc)
#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);
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.
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.
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.
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 |
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.
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.
SVr4 and POSIX.1-2001 specify that
action is significant only for
unsuccessful searches, so that an
ENTER should not do anything for a
successful search. In libc and glibc (before glibc 2.3), the implementation
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.
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);
}
bsearch(3),
lsearch(3),
malloc(3),
tsearch(3)
La traduction française de cette page de manuel a été
créée par Christophe Blaess
<
https://www.blaess.fr/christophe/>, Stéphan Rafin
<
[email protected]>, Thierry Vignaud
<
[email protected]>, François Micaux, Alain Portal
<
[email protected]>, Jean-Philippe Guérard
<
[email protected]>, Jean-Luc Coulon (f5ibh)
<
[email protected]>, Julien Cristau
<
[email protected]>, Thomas Huriaux <
[email protected]>,
Nicolas François <
[email protected]>, Florentin
Duneau <
[email protected]>, Simon Paillard
<
[email protected]>, Denis Barbier
<
[email protected]>, David Prévot <
[email protected]>,
Jean-Baptiste Holcroft <
[email protected]> et Grégoire
Scano <
[email protected]>
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 à
[email protected]