.\" -*- coding: UTF-8 -*-
'\" t
.\" Copyright 1995 by Jim Van Zandt <jrv@vanzandt.mv.com>
.\"
.\" SPDX-License-Identifier: Linux-man-pages-copyleft
.\"
.\"*******************************************************************
.\"
.\" This file was generated with po4a. Translate the source file.
.\"
.\"*******************************************************************
.TH tsearch 3 "26 janvier 2023" "Pages du manuel de Linux 6.03" 
.SH NOM
tsearch, tfind, tdelete, twalk, twalk_r, tdestroy \- Manipuler un arbre
binaire de recherche
.SH BIBLIOTHÈQUE
Bibliothèque C standard (\fIlibc\fP, \fI\-lc\fP)
.SH SYNOPSIS
.nf
\fB#include <search.h>\fP
.PP
\fBtypedef enum { preorder, postorder, endorder, leaf } VISIT;\fP
.PP
\fBvoid *tsearch(const void *\fP\fIkey\fP\fB, void **\fP\fIrootp\fP\fB,\fP
\fB                int (*\fP\fIcompar\fP\fB)(const void *, const void *));\fP
\fBvoid *tfind(const void *\fP\fIkey\fP\fB, void *const *\fP\fIrootp\fP\fB,\fP
\fB                int (*\fP\fIcompar\fP\fB)(const void *, const void *));\fP
\fBvoid *tdelete(const void *restrict \fP\fIkey\fP\fB, void **restrict \fP\fIrootp\fP\fB,\fP
\fB                int (*\fP\fIcompar\fP\fB)(const void *, const void *));\fP
\fBvoid twalk(const void *\fP\fIroot\fP\fB,\fP
\fB                void (*\fP\fIaction\fP\fB)(const void *\fP\fInodep\fP\fB, VISIT \fP\fIwhich\fP\fB,\fP
\fB                               int \fP\fIdepth\fP\fB));\fP
.PP
\fB#define _GNU_SOURCE\fP         /* Consultez feature_test_macros(7) */
\fB#include <search.h>\fP
.PP
\fBvoid twalk_r(const void *\fP\fIroot\fP\fB,\fP
\fB                void (*\fP\fIaction\fP\fB)(const void *\fP\fInodep\fP\fB, VISIT \fP\fIwhich\fP\fB,\fP
\fB                               void *\fP\fIclosure\fP\fB),\fP
\fB                void *\fP\fIclosure\fP\fB);\fP
\fBvoid tdestroy(void *\fP\fIroot\fP\fB, void (*\fP\fIfree_node\fP\fB)(void *\fP\fInodep\fP\fB));\fP
.fi
.SH DESCRIPTION
\fBtsearch\fP(), \fBtfind\fP(), \fBtwalk\fP() et \fBtdelete\fP() permettent de manipuler
un arbre binaire de recherche. Ces fonctions implémentent une généralisation
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). \fIcompar\fP pointe sur une
routine de comparaison prenant en argument deux pointeurs 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.
.PP
\fBtsearch\fP() recherche un élément dans l'arbre. \fIkey\fP pointe sur l'élément
à chercher. \fIrootp\fP pointe vers une variable qui pointe vers la racine de
l'arbre. Si l'arbre est vide, alors \fIrootp\fP doit pointer sur une variable
devant être réglée à \fBNULL\fP. Si l'élément est trouvé dans l'arbre,
\fBtsearch\fP() renvoie un pointeur sur le nœud de l'arbre correspondant. (En
d'autres termes, \fBtsearch\fP() retourne un pointeur sur un pointeur sur
l'élément.) Si l'élément n'est pas trouvé, \fBtsearch\fP() l'ajoute dans
l'arbre et renvoie un pointeur sur le nœud de l'arbre correspondant.
.PP
\fBtfind\fP() fonctionne comme \fBtsearch\fP(), sauf que si l'élément n'est pas
trouvé, la fonction \fBtfind\fP() renvoie \fBNULL\fP.
.PP
\fBtdelete\fP() supprime un élément de l'arbre. Ses arguments sont les mêmes
que ceux de \fBtsearch\fP().
.PP
\fBtwalk\fP() exécute un parcours en profondeur d'abord, de gauche à droite
ensuite, de l'arbre binaire. \fIroot\fP pointe sur le nœud de départ du
parcours. S'il ne s'agit pas de la vraie racine de l'arbre, seule une partie
de celui\-ci sera balayé. \fBtwalk\fP() appelle la fonction \fIaction\fP chaque
fois qu'un nœud est rencontré (c'est\-à\-dire trois fois pour un nœud interne
et une seule fois pour une feuille de l'arbre). \fIaction\fP doit accepter
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 possible de
transformer le pointeur sous forme de pointeur\-vers\-pointeur\-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 argument. Le deuxième argument est
un entier prenant l'une des valeurs suivantes\ : \fBpreorder\fP, \fBpostorder\fP
ou \fBendorder\fP suivant qu'il s'agisse de la première, deuxième ou troisième
rencontre du nœud, ou la valeur \fBleaf\fP s'il s'agit d'un nœud feuille (ces
symboles sont définis dans \fI<search.h>\fP). Le troisième argument est
la profondeur du nœud dans l'arbre, le nœud racine ayant la profondeur zéro.
.PP
Ordinairement, \fBpreorder\fP, \fBpostorder\fP et \fBendorder\fP sont connus sous le
nom \fBpreorder\fP (préfixe), \fBinorder\fP (infixe), et \fBpostorder\fP (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 \fBpost\%order\fP est un peu
déroutant.
.PP
\fBtwalk_r\fP() est similaire à \fBtwalk\fP(), mais à la place de l'argument
\fIdepth\fP, le pointeur argument \fIclosure\fP est passé à chaque invocation de
la fonction 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.
.PP
\fBtdestroy\fP() supprime tout l'arbre pointé par \fIroot\fP, libérant toutes les
ressources allouées par la fonction \fBtsearch\fP(). Pour libérer les données
de chaque nœud, la fonction \fIfree_node\fP est invoquée. Le pointeur sur les
données est passé en argument à cette fonction. Si aucune libération n'est
nécessaire, \fIfree_node\fP doit pointer vers une fonction ne faisant rien.
.SH "VALEUR RENVOYÉE"
\fBtsearch\fP() renvoie un pointeur sur un nœud correspondant de l'arbre, ou
sur le nœud nouvellement ajouté, ou \fBNULL\fP s'il n'y avait pas assez de
mémoire pour ajouter le nœud. \fBtfind\fP() renvoie un pointeur sur le nœud
recherché, ou \fBNULL\fP si aucune correspondance n'a été trouvée. Si plusieurs
éléments correspondent à la clé, l’élément dont le nœud est renvoyé n'est
pas spécifié.
.PP
\fBtdelete\fP() renvoie un pointeur sur le nœud père de celui détruit, ou
\fBNULL\fP si l'élément n'a pas été trouvé. Si le nœud détruit était le nœud
racine, \fBtdelete\fP() renvoie un pointer ne pointant sur aucun objet valable
et auquel il ne faut pas accéder.
.PP
\fBtsearch\fP(), \fBtfind\fP() et \fBtdelete\fP() renvoient également \fBNULL\fP si
\fIrootp\fP valait \fBNULL\fP.
.SH VERSIONS
\fBtwalk_r\fP() est disponible depuis la glibc\ 2.30.
.SH ATTRIBUTS
Pour une explication des termes utilisés dans cette section, consulter
\fBattributes\fP(7).
.ad l
.nh
.TS
allbox;
lbx lb lb
l l l.
Interface	Attribut	Valeur
T{
\fBtsearch\fP(),
\fBtfind\fP(),
\fBtdelete\fP()
T}	Sécurité des threads	MT\-Safe race:rootp
T{
\fBtwalk\fP()
T}	Sécurité des threads	MT\-Safe race:root
T{
\fBtwalk_r\fP()
T}	Sécurité des threads	MT\-Safe race:root
T{
\fBtdestroy\fP()
T}	Sécurité des threads	MT\-Safe
.TE
.hy
.ad
.sp 1
.SH STANDARDS
POSIX.1\-2001, POSIX.1\-2008, SVr4. Les fonctions \fBtdestroy\fP() et
\fBtwalk_t\fP() sont des extensions GNU.
.SH NOTES
\fBtwalk\fP() utilise un pointeur sur la racine, alors que les autres fonctions
utilisent un pointeur sur une variable pointant sur la racine.
.PP
\fBtdelete\fP() 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.
.PP
Le programme d'exemple s'appuie sur le fait que \fBtwalk\fP() 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
System\ V.
.SH EXEMPLES
Le programme suivant insère douze nombres aléatoires dans un arbre binaire,
où les doublons sont supprimés, puis affiche les nombres classés.
.PP
.\" SRC BEGIN (tsearch.c)
.EX
#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\en");
    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\en", *datap);
        break;
    case endorder:
        break;
    case leaf:
        datap = *(int **) nodep;
        printf("%6d\en", *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);
}
.EE
.\" SRC END
.SH "VOIR AUSSI"
\fBbsearch\fP(3), \fBhsearch\fP(3), \fBlsearch\fP(3), \fBqsort\fP(3)
.PP
.SH 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 <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.coulon@wanadoo.fr>,
Julien Cristau <jcristau@debian.org>,
Thomas Huriaux <thomas.huriaux@gmail.com>,
Nicolas François <nicolas.francois@centraliens.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-baptiste@holcroft.fr>
et
Grégoire Scano <gregoire.scano@malloc.fr>
.
.PP
Cette traduction est une documentation libre ; veuillez vous reporter à la
.UR https://www.gnu.org/licenses/gpl-3.0.html
GNU General Public License version 3
.UE
concernant les conditions de copie et 
de distribution. Il n'y a aucune RESPONSABILITÉ LÉGALE.
.PP
Si vous découvrez un bogue dans la traduction de cette page de manuel, 
veuillez envoyer un message à
.MT debian-l10n-french@lists.debian.org
.ME .