Provided by:
manpages-fr_1.67.0-1_all 
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;
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 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;
où 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;
où 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.