Votre IP: 38.107.179.241 
  		 
Google
 
Accueil e-mail Linux
Linux		 Perl
Perl		 C
Langage C		 Dico
Dictionnaire		 Biblio liens
Bibliothèque de liens		 Index articles
Index articles		  

Date création : 27-03-2008 20:23:44

Linux  Vous êtes dans : GNU/Linux Astuces / Pages man [Section3 - Sous-fonctions]


QUEUE

 

Index

  1. NOM
  2. SYNOPSIS
  3. DESCRIPTION
  4. LISTES SIMPLES
  5. EXEMPLE DE LISTE SIMPLE
  6. LISTES DOUBLES
  7. EXEMPLE DE LISTE DOUBLE
  8. LISTE CIRCULAIRE
  9. EXEMPLE DE LISTE CIRCULAIRE
  10. CONFORMITÉ
  11. TRADUCTION
24 janvier 1994 BSD 4  

NOMIndex

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, listes doubles et circulaires  

SYNOPSISIndex

Fd #include <sys/queue.h> Fn LIST_ENTRY TYPE Fn LIST_HEAD HEADNAME TYPE Fn LIST_INIT LIST_HEAD *head Fn LIST_INSERT_AFTER LIST_ENTRY *listelm TYPE *elm LIST_ENTRY NAME Fn LIST_INSERT_HEAD LIST_HEAD *head TYPE *elm LIST_ENTRY NAME Fn LIST_REMOVE TYPE *elm LIST_ENTRY NAME Fn TAILQ_ENTRY TYPE Fn TAILQ_HEAD HEADNAME TYPE Fn TAILQ_INIT TAILQ_HEAD *head Fn TAILQ_INSERT_AFTER TAILQ_HEAD *head TYPE *listelm TYPE *elm TAILQ_ENTRY NAME Fn TAILQ_INSERT_HEAD TAILQ_HEAD *head TYPE *elm TAILQ_ENTRY NAME Fn TAILQ_INSERT_TAIL TAILQ_HEAD *head TYPE *elm TAILQ_ENTRY NAME Fn TAILQ_REMOVE TAILQ_HEAD *head TYPE *elm TAILQ_ENTRY NAME Fn CIRCLEQ_ENTRY TYPE Fn CIRCLEQ_HEAD HEADNAME TYPE Fn CIRCLEQ_INIT CIRCLEQ_HEAD *head Fn CIRCLEQ_INSERT_AFTER CIRCLEQ_HEAD *head TYPE *listelm TYPE *elm CIRCLEQ_ENTRY NAME Fn CIRCLEQ_INSERT_BEFORE CIRCLEQ_HEAD *head TYPE *listelm TYPE *elm CIRCLEQ_ENTRY NAME Fn CIRCLEQ_INSERT_HEAD CIRCLEQ_HEAD *head TYPE *elm CIRCLEQ_ENTRY NAME Fn CIRCLEQ_INSERT_TAIL CIRCLEQ_HEAD *head TYPE *elm CIRCLEQ_ENTRY NAME Fn CIRCLEQ_REMOVE CIRCLEQ_HEAD *head TYPE *elm CIRCLEQ_ENTRY NAME  

DESCRIPTIONIndex

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 :

  1. Insertion d'un élément en tête de liste ;
  2. Insertion d'un élément après n'importe quel élément existant ;
  3. Suppression de n'importe quel élément ;
  4. 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 :

  1. 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 :

  1. Un élément peut être ajouté en fin de liste.
  2. Des entrées peuvent être ajoutées avant chaque entrée ;
  3. 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, Fa 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é Fa NAME . L'argument Fa 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 SIMPLESIndex

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 Fa LIST_HEAD est déclarée ainsi : 
LIST_HEAD(HEADNAME, TYPE) head;

où Fa HEADNAME est le nom de la structure à définir, et Fa 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 Fa head .
La macro LIST_INSERT_HEAD insère le nouvel élément Fa elm à la tête de la liste.
La macro LIST_INSERT_AFTER insère le nouvel élément Fa elm après l'élément Fa listelm .
La macro LIST_REMOVE supprime l'élément Fa elm de la liste.  

EXEMPLE DE LISTE SIMPLEIndex

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);
                                        /* 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 DOUBLESIndex

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 Fa 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 Fa head .
La macro TAILQ_INSERT_HEAD insère le nouvel élément Fa elm à la fin de la liste double.
La macro TAILQ_INSERT_TAIL insère le nouvel élément Fa elm à la fin de la liste double.
La macro TAILQ_INSERT_AFTER insère le nouvel élément Fa elm après l'élément Fa listelm .
La macro TAILQ_REMOVE supprime l'élément Fa elm de la liste double.  

EXEMPLE DE LISTE DOUBLEIndex

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);
                                        /* Traversée */
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 CIRCULAIREIndex

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 Fa 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 Fa head .
La macro CIRCLEQ_INSERT_HEAD insère le nouvel élément Fa elm au début de la liste circulaire.
La macro CIRCLEQ_INSERT_TAIL insère le nouvel élément Fa elm à la fin de la liste circulaire.
La macro CIRCLEQ_INSERT_AFTER insère le nouvel élément Fa elm après l'élément Fa listelm .
La macro CIRCLEQ_INSERT_BEFORE insère le nouvel élément Fa elm avant l'élément Fa listelm .
La macro CIRCLEQ_REMOVE supprime l'élément Fa elm de la liste circulaire.  

EXEMPLE DE LISTE CIRCULAIREIndex

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ÉIndex

Pas dans POSIX.1-2001. Présentes sur les BSD. Les fonctions de liste queue sont apparues dans BSD 4.4  

TRADUCTIONIndex

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.
La traduction de cette page de manuel est basée sur les traductions disponibles sur http://manpagesfr.free.fr/, mais est gérée par l'équipe francophone de traduction de Debian au travers de la liste de discussion debian-l10n-french.
Veuillez signaler toute erreur de traduction 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> ».

Création : octobre 2007  © Tous droits réservés 2007 linux-perl-c
Valid HTML 4.01 TransitionalValid CSS