Loading

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  -  Implementations  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);

       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 :

           *   Insertion d’un élément en tête de liste ;
           *   Insertion d’un élément après n’importe quel élément existant ;
           *   Suppression de n’importe quel élément ;
           *   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 :

           *   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 :

           *   Un élément peut être ajouté en fin de liste.
           *   Des entrées peuvent être ajoutées avant chaque entrée ;
           *   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
       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
       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);
                                               /* Parcours en avant */
       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);
                                               /* Parcours en avant */
       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);

   Listes circulaires
       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 BSD 4.4.

COLOPHON

       Cette page fait partie de  la  publication  3.23  du  projet  man-pages
       Linux.  Une description du projet et des instructions pour signaler des
       anomalies      peuvent      être       trouvées       à       l’adresse
       http://www.kernel.org/doc/man-pages/.

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> ».