Provided by:
manpages-fr-dev_3.27fr1.4-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 - 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);
DESCRIPTION
Ces macros definissent et manipulent trois types de structures de
donnees : les listes simples, les listes doubles et les listes
circulaires. Ces trois structures supportent les fonctionnalites
suivantes :
* Insertion d'un element en tete de liste ;
* Insertion d'un element apres n'importe quel element existant ;
* Suppression de n'importe quel element ;
* Traversee sequentielle de la liste.
Les listes sont les plus simples de ces trois structures de donnees et
ne supportent que les fonctionnalites ci-dessus.
Les listes doubles ajoutent la fonctionnalite suivante :
* Un element peut etre ajoute en fin de liste.
Cependant :
1. Toutes les insertions et suppressions doivent mentionner la
tete de la liste ;
2. L'element de tete necessite deux pointeurs au lieu d'un seul ;
3. La taille du code est environ 15% plus grande, et l'execution
environ 20% plus lente que les listes.
Les listes circulaires ajoutent les fonctionnalites suivantes :
* Un element peut etre ajoute en fin de liste.
* Des entrees peuvent etre ajoutees avant chaque entree ;
* Elles peuvent etre traversees a l'envers, de la queue a la
tete ;
Cependant :
1. Toutes les insertions et suppressions doivent mentionner la
tete de la liste ;
2. L'element de tete necessite deux pointeurs au lieu d'un seul ;
3. La condition de terminaison pour la traversee est plus
compliquee ;
4. La taille du code est environ 40% plus grande, et l'execution
environ 45% plus lente que les listes.
Dans les definitions de macros, TYPE est le nom d'une structure definie
par l'utilisateur, qui doit contenir un champ de type LIST_ENTRY,
TAILQ_ENTRY ou CIRCLEQ_ENTRY, appele NAME. L'argument HEADNAME est le
nom d'une structure definie par l'utilisateur qui doit etre declaree en
utilisant les macros LIST_HEAD, TAILQ_HEAD ou CIRCLEQ_HEAD. Consultez
les exemples plus bas pour une explication sur l'utilisation de ces
macros.
Listes
Une liste debute par une structure definie par la macro LIST_HEAD.
Cette structure contient un pointeur simple sur le premier element de
la liste. Les elements sont doublement chaines afin qu'un element
puisse etre supprime sans parcourir toute la liste. Des elements
peuvent etre ajoutes apres un element existant ou en tete de liste. Une
structure LIST_HEAD est declaree ainsi :
LIST_HEAD(HEADNAME, TYPE) head;
ou HEADNAME est le nom de la structure a definir, et TYPE le type
d'element a lier dans la liste. Un pointeur sur la tete de la liste
peut ensuite etre declare ainsi :
struct HEADNAME *headp;
(les noms head et headp sont choisis par l'utilisateur)
La macro LIST_ENTRY declare une structure qui connecte les elements
dans la liste.
La macro LIST_INIT initialise la liste referencee par head.
La macro LIST_INSERT_HEAD insere le nouvel element elm a la tete de la
liste.
La macro LIST_INSERT_AFTER insere le nouvel element elm apres l'element
listelm.
La macro LIST_REMOVE supprime l'element elm de la liste.
Exemple de liste
LIST_HEAD(listhead, entry) head;
struct listhead *headp; /* Tete 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 tete */
LIST_INSERT_HEAD(&head, n1, entries);
n2 = malloc(sizeof(struct entry)); /* Insertion apres */
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 tete d'une liste double est designee par une structure definie par
la macro TAILQ_HEAD. Cette structure contient deux pointeurs, l'un sur
le premier element et l'autre sur le dernier element. Les elements sont
doublement chaines, ainsi un element quelconque peut etre supprime sans
reparcourir toute la liste. Les nouveaux elements peuvent etre ajoutes
apres un element existant, en tete ou en queue de liste. Une structure
TAILQ_HEAD est declaree ainsi :
TAILQ_HEAD(HEADNAME, TYPE) head;
ou HEADNAME est le nom de la structure a definir, et TYPE represente le
type des elements a lier dans la liste. Un pointeur sur la tete de la
liste peut etre declare ainsi :
struct HEADNAME *headp;
(les noms head et headp sont choisis par l'utilisateur)
La macro TAILQ_ENTRY declare une structure qui connecte les elements
dans la liste double.
La macro TAILQ_INIT initialise la liste double referencee par head.
La macro TAILQ_INSERT_HEAD insere le nouvel element elm a la fin de la
liste double.
La macro TAILQ_INSERT_TAIL insere le nouvel element elm a la fin de la
liste double.
La macro TAILQ_INSERT_AFTER insere le nouvel element elm apres
l'element listelm.
La macro TAILQ_REMOVE supprime l'element elm de la liste double.
Exemple de liste double
TAILQ_HEAD(tailhead, entry) head;
struct tailhead *headp; /* Tete 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 debut */
TAILQ_INSERT_HEAD(&head, n1, entries);
n1 = malloc(sizeof(struct entry)); /* Insertion a la fin */
TAILQ_INSERT_TAIL(&head, n1, entries);
n2 = malloc(sizeof(struct entry)); /* Insertion apres */
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 tete d'une liste circulaire est designee par une structure definie
par la macro CIRCLEQ_HEAD. Cette structure contient une paire de
pointeurs, l'un sur le premier element de la liste circulaire et
l'autre sur le dernier element. Les elements sont doublement chaines,
afin de pouvoir supprimer un element quelconque sans reparcourir toute
la liste. De nouveaux elements peuvent etre ajoutes avant ou apres un
element existant, au debut ou a la fin de la liste. Une structure
CIRCLEQ_HEAD est declaree ainsi :
CIRCLEQ_HEAD(HEADNAME, TYPE) head;
ou HEADNAME est le nom de la structure a definir, et TYPE est le type
de l'element a lier dans la liste circulaire. Un pointeur sur la tete
de la liste circulaire peut etre declare ainsi :
struct HEADNAME *headp;
(les noms head et headp sont choisis par l'utilisateur)
La macro CIRCLEQ_ENTRY declare une structure qui connecte les elements
dans la liste circulaire.
La macro CIRCLEQ_INIT initialise la liste circulaire referencee par
head.
La macro CIRCLEQ_INSERT_HEAD insere le nouvel element elm au debut de
la liste circulaire.
La macro CIRCLEQ_INSERT_TAIL insere le nouvel element elm a la fin de
la liste circulaire.
La macro CIRCLEQ_INSERT_AFTER insere le nouvel element elm apres
l'element listelm.
La macro CIRCLEQ_INSERT_BEFORE insere le nouvel element elm avant
l'element listelm.
La macro CIRCLEQ_REMOVE supprime l'element elm de la liste circulaire.
Exemple de liste circulaire
CIRCLEQ_HEAD(circleq, entry) head;
struct circleq *headp; /* Tete 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 debut */
CIRCLEQ_INSERT_HEAD(&head, n1, entries);
n1 = malloc(sizeof(struct entry)); /* Insertion a la fin */
CIRCLEQ_INSERT_TAIL(&head, n1, entries);
n2 = malloc(sizeof(struct entry)); /* Insertion apres */
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 arriere */
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'E
Pas dans POSIX.1-2001. Presentes sur les BSD. Les fonctions de liste
queue sont apparues dans BSD 4.4.
COLOPHON
Cette page fait partie de la publication 3.27 du projet man-pages
Linux. Une description du projet et des instructions pour signaler des
anomalies peuvent etre trouvees a l'adresse
<URL:http://www.kernel.org/doc/man-pages/>.
TRADUCTION
Depuis 2010, cette traduction est maintenue a l'aide de l'outil po4a
<URL:http://po4a.alioth.debian.org/> par l'equipe de traduction
francophone au sein du projet perkamon
<URL:http://perkamon.alioth.debian.org/>.
Christophe Blaess <URL:http://www.blaess.fr/christophe/> (1996-2003),
Alain Portal <URL:http://manpagesfr.free.fr/> (2003-2006). Nicolas
Francois et l'equipe francophone de traduction de Debian (2006-2009).
Veuillez signaler toute erreur de traduction en ecrivant a
<debian-l10n-french@lists.debian.org> ou par un rapport de bogue sur le
paquet manpages-fr.
Vous pouvez toujours avoir acces a la version anglaise de ce document
en utilisant la commande << man -L C <section> <page_de_man> >>.
Linux 28 decembre 2007 QUEUE(3)