NOM¶

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() 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ée. 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 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 postorder est un peu déroutant.

twalk_r() is similar to twalk(), but instead of the depth argument, the closure argument pointer is passed to each invocation of the action callback, unchanged. This pointer can be used to pass information to and from the callback function in a thread-safe fashion, without resorting to global variables.

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¶

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¶

ATTRIBUTS¶

CONFORMITɶ

NOTES¶

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ée 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.

EXEMPLE¶

#define _GNU_SOURCE     /* Expose la déclaration de tdestroy() */
#include <search.h>
#include <stdlib.h>
#include <stdio.h>
#include <time.h>
static void *racine = NULL;
static void *
xmalloc(unsigned n)
{
    void *p;
    p = malloc(n);
    if (p)
        return p;
    fprintf(stderr, "pas assez de mémoire\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 i, *ptr;
    void *val;
    srand(time(NULL));
    for (i = 0; i < 12; i++) {
        ptr = xmalloc(sizeof(int));
        *ptr = rand() & 0xff;
        val = tsearch((void *) ptr, &root, compare);
        if (val == NULL)
            exit(EXIT_FAILURE);
        else if ((*(int **) val) != ptr)
            free(ptr);
    }
    twalk(root, action);
    tdestroy(root, free);
    exit(EXIT_SUCCESS);
}

VOIR AUSSI¶

COLOPHON¶

TRADUCTION¶

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 à <debian-l10n-french@lists.debian.org>.