Provided by: manpages-fr-dev_4.13-4_all bug

NOM

       tsearch, tfind, tdelete, twalk, tdestroy - Manipuler un arbre binaire de recherche

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 *key, void **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é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).
       compar  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.

       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 parcours. S'il ne s'agit  pas  de  la  vraie
       racine  de  l'arbre, seule une partie 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  interne
       et  une  seule fois pour une feuille de l'arbre). action 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 :  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  post‐
       order 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  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.

       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  plusieurs  éléments  correspondent à la clé, l’élément dont le nœud est
       renvoyé 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 valable et auquel il ne faut pas accéder.

       tsearch(), tfind() et tdelete() renvoient également NULL si rootp valait NULL.

VERSIONS

       twalk_r() a été ajoutée à la glibc dans la version 2.30.

ATTRIBUTS

       Pour une explication des termes utilisés dans cette section, consulter attributes(7).

       ┌────────────────────┬──────────────────────┬────────────────────┐
       │InterfaceAttributValeur             │
       ├────────────────────┼──────────────────────┼────────────────────┤
       │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            │
       └────────────────────┴──────────────────────┴────────────────────┘

CONFORMITÉ

       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 fonctions 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
       System V.

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.

       #define _GNU_SOURCE     /* Expose la déclaration de tdestroy() */
       #include <search.h>
       #include <stddef.h>
       #include <stdlib.h>
       #include <stdio.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 **val;

           srand(time(NULL));
           for (int i = 0; i < 12; i++) {
               int *ptr = xmalloc(sizeof(*ptr));
               *ptr = rand() & 0xff;
               val = tsearch(ptr, &root, compare);
               if (val == NULL)
                   exit(EXIT_FAILURE);
               else if (*val != ptr)
                   free(ptr);
           }
           twalk(root, action);
           tdestroy(root, free);
           exit(EXIT_SUCCESS);
       }

VOIR AUSSI

       bsearch(3), hsearch(3), lsearch(3), qsort(3)

COLOPHON

       Cette page fait partie de la publication 5.10 du projet man-pages Linux.  Une  description
       du  projet et des instructions pour signaler des anomalies et la dernière version de cette
       page peuvent être trouvées à l'adresse https://www.kernel.org/doc/man-pages/.

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>

       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 ⟨⟩.