tsearch(3) Library Functions Manual tsearch(3)
NOM
tsearch, tfind, tdelete, twalk, twalk_r, tdestroy - Manipuler un arbre
binaire de recherche
BIBLIOTHÈQUE
Bibliothèque C standard (libc, -lc)
SYNOPSIS
#include <search.h>
typedef enum { preorder, postorder, endorder, leaf } VISIT;
void *tsearch(const void *key, void **rootp,
int (*compar)(const void *, const void *));
void *tfind(const void *key, void *const *rootp,
int (*compar)(const void *, const void *));
void *tdelete(const void *restrict key, void **restrict rootp,
int (*compar)(const void *, const void *));
void twalk(const void *root,
void (*action)(const void *nodep, VISIT which,
int depth));
#define _GNU_SOURCE /* Consultez feature_test_macros(7) */
#include <search.h>
void twalk_r(const void *root,
void (*action)(const void *nodep, VISIT which,
void *closure),
void *closure);
void tdestroy(void *root, void (*free_node)(void *nodep));
DESCRIPTION
tsearch(), tfind(), twalk() et tdelete() permettent de manipuler un
arbre binaire de recherche. Ces fonctions implémentent une généralisa-
tion de l'algorithme T de Knuth (6.2.2). Le premier membre de chaque
nœud de l'arbre est un pointeur vers la donnée elle-même (le programme
appelant doit prendre en charge le stockage de ces données). compar
pointe sur une routine de comparaison prenant en argument deux poin-
teurs sur ces données. Elle doit renvoyer un entier négatif, nul, ou
positif suivant que le premier élément est inférieur, égal ou supérieur
au second.
tsearch() recherche un élément dans l'arbre. key pointe sur l'élément à
chercher. rootp pointe vers une variable qui pointe vers la racine de
l'arbre. Si l'arbre est vide, alors rootp doit pointer sur une variable
devant être réglée à NULL. Si l'élément est trouvé dans l'arbre,
tsearch() renvoie un pointeur sur le nœud de l'arbre correspondant. (En
d'autres termes, tsearch() retourne un pointeur sur un pointeur sur
l'élément.) Si l'élément n'est pas trouvé, tsearch() l'ajoute dans
l'arbre et renvoie un pointeur sur le nœud de l'arbre correspondant.
tfind() fonctionne comme tsearch(), sauf que si l'élément n'est pas
trouvé, la fonction tfind() renvoie NULL.
tdelete() supprime un élément de l'arbre. Ses arguments sont les mêmes
que ceux de tsearch().
twalk() exécute un parcours en profondeur d'abord, de gauche à droite
ensuite, de l'arbre binaire. root pointe sur le nœud de départ du par-
cours. S'il ne s'agit pas de la vraie racine de l'arbre, seule une par-
tie de celui-ci sera balayé. twalk() appelle la fonction action chaque
fois qu'un nœud est rencontré (c'est-à-dire trois fois pour un nœud in-
terne et une seule fois pour une feuille de l'arbre). action doit ac-
cepter trois arguments. Le premier argument est un pointeur sur le nœud
rencontré. La structure du nœud n'est pas spécifiée, mais il est pos-
sible de transformer le pointeur sous forme de pointeur-vers-poin-
teur-vers-élément afin d'accéder à l'élément enregistré dans le nœud.
L'application ne doit pas modifier la structure pointée par cet argu-
ment. Le deuxième argument est un entier prenant l'une des valeurs sui-
vantes : preorder, postorder ou endorder suivant qu'il s'agisse de la
première, deuxième ou troisième rencontre du nœud, ou la valeur leaf
s'il s'agit d'un nœud feuille (ces symboles sont définis dans
<search.h>). Le troisième argument est la profondeur du nœud dans
l'arbre, le nœud racine ayant la profondeur zéro.
Ordinairement, preorder, postorder et endorder sont connus sous le nom
preorder (préfixe), inorder (infixe), et postorder (postfixe) : avant
de visiter le nœud fils, après le premier et avant le second, après
avoir visité les enfants. Ainsi, le choix du nom postorder est un peu
déroutant.
twalk_r() est similaire à twalk(), mais à la place de l'argument depth,
le pointeur argument closure est passé à chaque invocation de la fonc-
tion de rappel d'action, inchangé. Ce pointeur peut être utilisé pour
passer de l'information vers et depuis la fonction de rappel de façon
sûre pour les threads, sans utiliser de variables globales.
tdestroy() supprime tout l'arbre pointé par root, libérant toutes les
ressources allouées par la fonction tsearch(). Pour libérer les données
de chaque nœud, la fonction free_node est invoquée. Le pointeur sur les
données est passé en argument à cette fonction. Si aucune libération
n'est nécessaire, free_node doit pointer vers une fonction ne faisant
rien.
VALEUR RENVOYÉE
tsearch() renvoie un pointeur sur un nœud correspondant de l'arbre, ou
sur le nœud nouvellement ajouté, ou NULL s'il n'y avait pas assez de
mémoire pour ajouter le nœud. tfind() renvoie un pointeur sur le nœud
recherché, ou NULL si aucune correspondance n'a été trouvée. Si plu-
sieurs éléments correspondent à la clé, l’élément dont le nœud est ren-
voyé n'est pas spécifié.
tdelete() renvoie un pointeur sur le nœud père de celui détruit, ou
NULL si l'élément n'a pas été trouvé. Si le nœud détruit était le nœud
racine, tdelete() renvoie un pointer ne pointant sur aucun objet va-
lable et auquel il ne faut pas accéder.
tsearch(), tfind() et tdelete() renvoient également NULL si rootp va-
lait NULL.
VERSIONS
twalk_r() est disponible depuis la glibc 2.30.
ATTRIBUTS
Pour une explication des termes utilisés dans cette section, consulter
attributes(7).
┌──────────────────────────┬──────────────────────┬────────────────────┐
│Interface │ Attribut │ Valeur │
├──────────────────────────┼──────────────────────┼────────────────────┤
│tsearch(), tfind(), │ Sécurité des threads │ MT-Safe race:rootp │
│tdelete() │ │ │
├──────────────────────────┼──────────────────────┼────────────────────┤
│twalk() │ Sécurité des threads │ MT-Safe race:root │
├──────────────────────────┼──────────────────────┼────────────────────┤
│twalk_r() │ Sécurité des threads │ MT-Safe race:root │
├──────────────────────────┼──────────────────────┼────────────────────┤
│tdestroy() │ Sécurité des threads │ MT-Safe │
└──────────────────────────┴──────────────────────┴────────────────────┘
STANDARDS
POSIX.1-2001, POSIX.1-2008, SVr4. Les fonctions tdestroy() et twalk_t()
sont des extensions GNU.
NOTES
twalk() utilise un pointeur sur la racine, alors que les autres fonc-
tions utilisent un pointeur sur une variable pointant sur la racine.
tdelete() libère la mémoire nécessaire au stockage du nœud dans
l'arbre. Le programme appelant est responsable de la libération de la
mémoire occupée par l'élément de données correspondant.
Le programme d'exemple s'appuie sur le fait que twalk() ne fait plus
jamais référence à un nœud après avoir appelé la fonction utilisateur
avec l'argument « endorder » ou « leaf ». Ceci fonctionne avec l'implé-
mentation de la bibliothèque GNU, mais n'est pas spécifié sous Sys-
tem V.
EXEMPLES
Le programme suivant insère douze nombres aléatoires dans un arbre bi-
naire, où les doublons sont supprimés, puis affiche les nombres clas-
sés.
#define _GNU_SOURCE /* Expose la déclaration de tdestroy() */
#include <search.h>
#include <stddef.h>
#include <stdio.h>
#include <stdlib.h>
#include <time.h>
static void *racine = NULL;
static void *
xmalloc(size_t n)
{
void *p;
p = malloc(n);
if (p)
return p;
fprintf(stderr, "insufficient memory\n");
exit(EXIT_FAILURE);
}
static int
compare(const void *pa, const void *pb)
{
if (*(int *) pa < *(int *) pb)
return -1;
if (*(int *) pa > *(int *) pb)
return 1;
return 0;
}
static void
action(const void *nodep, VISIT which, int depth)
{
int *datap;
switch (type) {
case preorder:
break;
case postorder:
datap = *(int **) nodep;
printf("%6d\n", *datap);
break;
case endorder:
break;
case leaf:
datap = *(int **) nodep;
printf("%6d\n", *datap);
break;
}
}
int
main(void)
{
int *ptr;
int **val;
srand(time(NULL));
for (unsigned int i = 0; i < 12; i++) {
ptr = xmalloc(sizeof(*ptr));
*ptr = rand() & 0xff;
val = tsearch(ptr, &root, compare);
if (val == NULL)
exit(EXIT_FAILURE);
if (*val != ptr)
free(ptr);
}
twalk(root, action);
tdestroy(root, free);
exit(EXIT_SUCCESS);
}
VOIR AUSSI
bsearch(3), hsearch(3), lsearch(3), qsort(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 26 janvier 2023 tsearch(3)
Generated by dwww version 1.15 on Sat Jun 29 00:52:55 CEST 2024.