Provided by: manpages-fr_1.67.0-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,  files   linéaires   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_REMOVE (CIRCLEQ_HEAD *head, TYPE *elm, CIRCLEQ_ENTRY NAME);

       CIRCLEQ_INIT (CIRCLEQ_HEAD *head);

       CIRCLEQ_INSERT_AFTER   (CIRCLEQ_HEAD   *head,   TYPE   *listelm,   TYPE
       *elmCIRCLEQ_ENTRY NAME);

       CIRCLEQ_INSERT_BEFORE   (CIRCLEQ_HEAD   *head,   TYPE   *listelm,  TYPE
       *elmCIRCLEQ_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 :

              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 simples ne supportent que les fonctionnalités ci-dessus.

       Les listes doubles ajoutent les fonctionnalités suivantes :

              Un élément peut être ajouté en fin de liste ;
       Toutefois :

              Toutes les insertions et suppressions doivent mentionner la tête
              de la liste ;

              L’élement de tête nécessite deux pointeurs au lieu d’un seul ;

              La  taille  du  code est environ 15% plus grande, et l’exécution
              environ
                     20% plus lente que les listes.

       Les listes ciculaires ajoutent les fonctionnalités suivantes :

              Un élément peut être ajouté à la fin de la liste ;

              Un élément peut être ajouté avant n’importe quel autre élément ;

              On peut parcourir la file en sens inverse.
       Toutefois :

              Toutes  les  insertions et suppressions doivent indiquer la tête
              de la liste ;

              L’élément de tête nécessite deux pointeurs au lieu d’un seul ;

              La   condition   de   terminaison  pour  le  parcours  est  plus
              compliquée ;

              La taille du code est environ 40% plus grande et l’exécution 45%
              plus lente
                     que les listes simples.

                     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,
                     nommé  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;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 et 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);             /* Initialisatoin 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 est déclarée ainsi :
       TAILQ_HEAD(HEADNAME, TYPE) head;HEADNAME est le nom de la structure à définir, et 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 élement 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  inssè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 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);

LISTE CIRCULAIRE

       La tête d’une liste circulaire est désignée par  une  structur  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;HEADNAME  est le nom de la structure à définir, et TYPE est le type
       de l’élement à 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 et 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. */
       struct entry {
            ...
            CIRCLEQ_ENTRY(entry) entries;      /* liste circulaire */
            ...
       } *n1, *n2, *np;

       CIRCLEQ_INIT(&head);               /* initialisation liste */

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

HISTORIQUE

       Les fonctions de liste sont apparues dans BSD 4.4

TRADUCTION

       Christophe Blaess, 2003.