#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);
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 :
Les listes circulaires ajoutent les fonctionnalités suivantes :
Toutefois :
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.
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.
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);
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.
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 la 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);
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.
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 de la 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);
Ce document est une traduction réalisée par Christophe Blaess <http://www.blaess.fr/christophe/> le 21 juillet 2003 et révisée le 17 juillet 2008.
L'équipe de traduction a fait le maximum pour réaliser une adaptation française de qualité. La version anglaise la plus à jour de ce document est toujours consultable via la commande : « LANG=C man 3 queue ». N'hésitez pas à signaler à l'auteur ou au traducteur, selon le cas, toute erreur dans cette page de manuel.
Dernière mise à jour : 17 juillet 2008