Provided by: manpages-fr-dev_4.19.0-7_all bug

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é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() est disponible depuis la glibc 2.30.

ATTRIBUTS

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

       ┌─────────────────────────────────────────────┬──────────────────────┬────────────────────┐
       │InterfaceAttributValeur             │
       ├─────────────────────────────────────────────┼──────────────────────┼────────────────────┤
       │tsearch(), tfind(), tdelete()                │ Sécurité des threads │ MT-Safe race:rootp │
       ├─────────────────────────────────────────────┼──────────────────────┼────────────────────┤
       │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  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 <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 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⟩.