Provided by: manpages-fr-dev_2.64.1-1_all bug

NOM

     LIST_ENTRY, LIST_HEAD, LIST_INIT, LIST_INSERT_AFTER, LIST_INSERT_HEAD,
     LIST_REMOVE, TAILQ_ENTRY, TAILQ_HEAD, TAILQ_INIT, TAILQ_INSERT_AFTER,
     TAILQ_INSERT_HEAD, TAILQ_INSERT_TAIL, TAILQ_REMOVE, CIRCLEQ_ENTRY,
     CIRCLEQ_HEAD, CIRCLEQ_INIT, CIRCLEQ_INSERT_AFTER, CIRCLEQ_INSERT_BEFORE,
     CIRCLEQ_INSERT_HEAD, CIRCLEQ_INSERT_TAIL, CIRCLEQ_REMOVE - Implémentation
     des listes, listes doubles et circulaires

SYNOPSIS

     #include <sys/queue.h>

     LIST_ENTRY(TYPE);

     LIST_HEAD(HEADNAME, TYPE);

     LIST_INIT(LIST_HEAD *head);

     LIST_INSERT_AFTER(LIST_ENTRY *listelm, TYPE *elm, LIST_ENTRY NAME);

     LIST_INSERT_HEAD(LIST_HEAD *head, TYPE *elm, LIST_ENTRY NAME);

     LIST_REMOVE(TYPE *elm, LIST_ENTRY NAME);

     TAILQ_ENTRY(TYPE);

     TAILQ_HEAD(HEADNAME, TYPE);

     TAILQ_INIT(TAILQ_HEAD *head);

     TAILQ_INSERT_AFTER(TAILQ_HEAD *head, TYPE *listelm, TYPE *elm,
             TAILQ_ENTRY NAME);

     TAILQ_INSERT_HEAD(TAILQ_HEAD *head, TYPE *elm, TAILQ_ENTRY NAME);

     TAILQ_INSERT_TAIL(TAILQ_HEAD *head, TYPE *elm, TAILQ_ENTRY NAME);

     TAILQ_REMOVE(TAILQ_HEAD *head, TYPE *elm, TAILQ_ENTRY NAME);

     CIRCLEQ_ENTRY(TYPE);

     CIRCLEQ_HEAD(HEADNAME, TYPE);

     CIRCLEQ_INIT(CIRCLEQ_HEAD *head);

     CIRCLEQ_INSERT_AFTER(CIRCLEQ_HEAD *head, TYPE *listelm, TYPE *elm,
             CIRCLEQ_ENTRY NAME);

     CIRCLEQ_INSERT_BEFORE(CIRCLEQ_HEAD *head, TYPE *listelm, TYPE *elm,
             CIRCLEQ_ENTRY NAME);

     CIRCLEQ_INSERT_HEAD(CIRCLEQ_HEAD *head, TYPE *elm, CIRCLEQ_ENTRY NAME);

     CIRCLEQ_INSERT_TAIL(CIRCLEQ_HEAD *head, TYPE *elm, CIRCLEQ_ENTRY NAME);

     CIRCLEQ_REMOVE(CIRCLEQ_HEAD *head, TYPE *elm, CIRCLEQ_ENTRY NAME);

DESCRIPTION

     Ces macros définissent et manipulent trois types de structures de
     données : les listes simples, les listes doubles et les listes
     circulaires. Ces trois structures supportent les fonctionnalités
     suivantes :
           1.   Insertion d’un élément en tête de liste ;
           2.   Insertion d’un élément après n’importe quel élément existant ;
           3.   Suppression de n’importe quel élément ;
           4.   Traversée séquentielle de la liste.

     Les listes sont les plus simples de ces trois structures de données et ne
     supportent que les fonctionnalités ci-dessus.

     Les listes doubles ajoutent la fonctionnalité suivante :
           1.   Un élément peut être ajouté en fin de liste.
     Cependant :
           1.   Toutes les insertions et suppressions doivent mentionner la
                tête de la liste ;
           2.   L’élément de tête nécessite deux pointeurs au lieu d’un seul ;
           3.   La taille du code est environ 15% plus grande, et l’exécution
                environ 20% plus lente que les listes.

     Les listes circulaires ajoutent les fonctionnalités suivantes :
           1.   Un élément peut être ajouté en fin de liste.
           2.   Des entrées peuvent être ajoutées avant chaque entrée ;
           3.   Elles peuvent être traversées à l’envers, de la queue à la
                tête ;
     Cependant :
           1.   Toutes les insertions et suppressions doivent mentionner la
                tête de la liste ;
           2.   L’élément de tête nécessite deux pointeurs au lieu d’un seul ;
           3.   La condition de terminaison pour la traversée est plus
                compliquée ;
           4.   La taille du code est environ 40% plus grande, et l’exécution
                environ 45% plus lente que les listes.

     Dans les définitions de macros, TYPE est le nom d’une structure définie
     par l’utilisateur, qui doit contenir un champ de type LIST_ENTRY,
     TAILQ_ENTRY ou CIRCLEQ_ENTRY, appelé NAME.  L’argument HEADNAME est le
     nom d’une structure définie par l’utilisateur qui doit être déclarée en
     utilisant les macros LIST_HEAD, TAILQ_HEAD ou CIRCLEQ_HEAD.  Voir les
     exemples plus bas pour une explication sur l’utilisation de ces macros.

LISTES SIMPLES

     Une liste débute par une structure définie par la macro LIST_HEAD.  Cette
     structure contient un pointeur simple sur le premier élément de la liste.
     Les éléments sont doublement chaînés afin qu’un élément puisse être
     supprimé sans parcourir toute la liste. Des éléments peuvent être ajoutés
     après un élément existant ou en tête de liste. Une structure LIST_HEAD
     est déclarée ainsi :

           LIST_HEAD(HEADNAME, TYPE) head;

     où HEADNAME est le nom de la structure à définir, et TYPE le type
     d’élément à lier dans la liste. Un pointeur sur la tête de la liste peut
     ensuite être déclaré ainsi :

           struct HEADNAME *headp;

     (les noms head et headp sont choisis par l’utilisateur)

     La macro LIST_ENTRY déclare une structure qui connecte les éléments dans
     la liste.

     La macro LIST_INIT initialise la liste référencée par head.

     La macro LIST_INSERT_HEAD insère le nouvel élément elm à la tête de la
     liste.

     La macro LIST_INSERT_AFTER insère le nouvel élément elm après l’élément
     listelm.

     La macro LIST_REMOVE supprime l’élément elm de la liste.

EXEMPLE DE LISTE SIMPLE

     LIST_HEAD(listhead, entry) head;
     struct listhead *headp;         /* tête de la liste */
     struct entry {
             ...
             LIST_ENTRY(entry) entries;      /* liste */
             ...
     } *n1, *n2, *np;

     LIST_INIT(&head);                       /* Initialisation de liste */

     n1 = malloc(sizeof(struct entry));      /* Insertion en tête */
     LIST_INSERT_HEAD(&head, n1, entries);

     n2 = malloc(sizeof(struct entry));      /* Insertion après */
     LIST_INSERT_AFTER(n1, n2, entries);
                                             /* Traversée */
     for (np = head.lh_first; np != NULL; np = np->entries.le_next)
             np-> ...

     while (head.lh_first != NULL)           /* Suppression */
             LIST_REMOVE(head.lh_first, entries);

LISTES DOUBLES

     La tête d’une liste double est désignée par une structure définie par la
     macro TAILQ_HEAD.  Cette structure contient deux pointeurs, l’un sur le
     premier élément et l’autre sur le dernier élément. Les éléments sont
     doublement chaînés, ainsi un élément quelconque peut être supprimé sans
     reparcourir toute la liste. Les nouveaux éléments peuvent être ajoutés
     après un élément existant, en tête ou en queue de liste. Une structure
     TAILQ_HEAD est déclarée ainsi :

           TAILQ_HEAD(HEADNAME, TYPE) head;

     où HEADNAME est le nom de la structure à définir, et TYPE représente le
     type des éléments à lier dans la liste. Un pointeur sur la tête de la
     liste peut être déclaré ainsi :

           struct HEADNAME *headp;

     (les noms head et headp sont choisis par l’utilisateur)

     La macro TAILQ_ENTRY déclare une structure qui connecte les éléments dans
     la liste double.

     La macro TAILQ_INIT initialise la liste double référencée par head.

     La macro TAILQ_INSERT_HEAD insère le nouvel élément elm à la fin de la
     liste double.

     La macro TAILQ_INSERT_TAIL insère le nouvel élément elm à la fin de la
     liste double.

     La macro TAILQ_INSERT_AFTER insère le nouvel élément elm après l’élément
     listelm.

     La macro TAILQ_REMOVE supprime l’élément elm de la liste double.

EXEMPLE DE LISTE DOUBLE

     TAILQ_HEAD(tailhead, entry) head;
     struct tailhead *headp;         /* Tête de liste double */
     struct entry {
             ...
             TAILQ_ENTRY(entry) entries;     /* Liste double */
             ...
     } *n1, *n2, *np;

     TAILQ_INIT(&head);                      /* Initialisation de liste */

     n1 = malloc(sizeof(struct entry));      /* Insertion au début */
     TAILQ_INSERT_HEAD(&head, n1, entries);

     n1 = malloc(sizeof(struct entry));      /* Insertion à la fin */
     TAILQ_INSERT_TAIL(&head, n1, entries);

     n2 = malloc(sizeof(struct entry));      /* Insertion après */
     TAILQ_INSERT_AFTER(&head, n1, n2, entries);
                                             /* Traversée */
     for (np = head.tqh_first; np != NULL; np = np->entries.tqe_next)
             np-> ...
                                             /* Suppression */
     while (head.tqh_first != NULL)
             TAILQ_REMOVE(&head, head.tqh_first, entries);

LISTE CIRCULAIRE

     La tête d’une liste circulaire est désignée par une structure définie par
     la macro CIRCLEQ_HEAD.  Cette structure contient une paire de pointeurs,
     l’un sur le premier élément de la liste circulaire et l’autre sur le
     dernier élément. Les éléments sont doublement chaînés, afin de pouvoir
     supprimer un élément quelconque sans reparcourir toute la liste. De
     nouveaux éléments peuvent être ajoutés avant ou après un élément
     existant, au début ou à la fin de la liste. Une structure CIRCLEQ_HEAD
     est déclarée ainsi :

           CIRCLEQ_HEAD(HEADNAME, TYPE) head;

     où HEADNAME est le nom de la structure à définir, et TYPE est le type de
     l’élément à lier dans la liste circulaire. Un pointeur sur la tête de la
     liste circulaire peut être déclaré ainsi :

           struct HEADNAME *headp;

     (les noms head et headp sont choisis par l’utilisateur)

     La macro CIRCLEQ_ENTRY déclare une structure qui connecte les éléments
     dans la liste circulaire.

     La macro CIRCLEQ_INIT initialise la liste circulaire référencée par head.

     La macro CIRCLEQ_INSERT_HEAD insère le nouvel élément elm au début de la
     liste circulaire.

     La macro CIRCLEQ_INSERT_TAIL insère le nouvel élément elm à la fin de la
     liste circulaire.

     La macro CIRCLEQ_INSERT_AFTER insère le nouvel élément elm après
     l’élément listelm.

     La macro CIRCLEQ_INSERT_BEFORE insère le nouvel élément elm avant
     l’élément listelm.

     La macro CIRCLEQ_REMOVE supprime l’élément elm de la liste circulaire.

EXEMPLE DE LISTE CIRCULAIRE

     CIRCLEQ_HEAD(circleq, entry) head;
     struct circleq *headp;                  /* Tête de liste circulaire */
     struct entry {
             ...
             CIRCLEQ_ENTRY(entry) entries;           /* Liste circulaire */
             ...
     } *n1, *n2, *np;

     CIRCLEQ_INIT(&head);                    /* Initialisation */

     n1 = malloc(sizeof(struct entry));      /* Insertion au début */
     CIRCLEQ_INSERT_HEAD(&head, n1, entries);

     n1 = malloc(sizeof(struct entry));      /* Insertion à la fin */
     CIRCLEQ_INSERT_TAIL(&head, n1, entries);

     n2 = malloc(sizeof(struct entry));      /* Insertion après */
     CIRCLEQ_INSERT_AFTER(&head, n1, n2, entries);

     n2 = malloc(sizeof(struct entry));      /* Insertion avant */
     CIRCLEQ_INSERT_BEFORE(&head, n1, n2, entries);
                                             /* Parcours en avant */
     for (np = head.cqh_first; np != (void *)&head; np = np->entries.cqe_next)
             np-> ...
                                             /* Parcours en arrière */
     for (np = head.cqh_last; np != (void *)&head; np = np->entries.cqe_prev)
             np-> ...
                                             /* Suppression */
     while (head.cqh_first != (void *)&head)
             CIRCLEQ_REMOVE(&head, head.cqh_first, entries);

CONFORMITÉ

     Pas dans POSIX.1-2001. Présentes sur les BSD. Les fonctions de liste
     queue sont apparues dans 4.4BSD.

TRADUCTION

     Cette page de manuel a été traduite et mise à jour par Christophe Blaess
     <http://www.blaess.fr/christophe/> entre 1996 et 2003, puis par Alain
     Portal <aportal AT univ-montp2 DOT fr> jusqu’en 2006, et mise à
     disposition sur http://manpagesfr.free.fr/.

     Les mises à jour et corrections de la version présente dans Debian sont
     directement gérées par Nicolas François
     <nicolas.francois@centraliens.net> et l’équipe francophone de traduction
     de Debian.

     Veuillez signaler toute erreur de traduction en écrivant à
     <debian-l10n-french@lists.debian.org> ou par un rapport de bogue sur le
     paquet manpages-fr.

     Vous pouvez toujours avoir accès à la version anglaise de ce document en
     utilisant la commande « man -L C <section> <page_de_man> ».