Editer un article - Informaticien.be

Editer un article

Titre
Mots Clés
Texte	[size=18] [b]Nom[/b] [/size] 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. [size=18] [b]Résumé[/b] [/size] [b]#include <sys/queue.h>[/b] [b][/b] [b][i]LIST_ENTRY ( TYPE );[/i][/b] [b][i]LIST_HEAD ( HEADNAME , TYPE );[/i][/b] [b][i]LIST_INIT ( LIST_HEAD * head );[/i][/b] [b][i]LIST_INSERT_AFTER ( LIST_ENTRY listelm , TYPE elm , LIST_ENTRY NAME );[/i][/b] [b][i]LIST_INSERT_HEAD ( LIST_HEAD head , TYPE elm , LIST_ENTRY NAME );[/i][/b] [b][i]LIST_REMOVE ( TYPE elm , LIST_ENTRY NAME );[/i][/b] [b][i]TAILQ_ENTRY ( TYPE );[/i][/b] [b]TAILQ_HEAD ( HEADNAME TYPE );[/b] [b][i]TAILQ_INIT ( TAILQ_HEAD head );[/i][/b] [b][i]TAILQ_INSERT_AFTER ( TAILQ_HEAD head , TYPE listelm , TYPE elm , TAILQ_ENTRY NAME );[/i][/b] [b][i]TAILQ_INSERT_HEAD ( TAILQ_HEAD head , TYPE elm , TAILQ_ENTRY NAME );[/i][/b] [b][i]TAILQ_INSERT_TAIL ( TAILQ_HEAD head , TYPE elm , TAILQ_ENTRY NAME );[/i][/b] [b][i]TAILQ_REMOVE ( TAILQ_HEAD head , TYPE elm , TAILQ_ENTRY NAME );[/i][/b] [b][i]CIRCLEQ_ENTRY ( TYPE );[/i][/b] [b][i]CIRCLEQ_REMOVE ( CIRCLEQ_HEAD head , TYPE elm , CIRCLEQ_ENTRY NAME );[/i][/b] [b][i]CIRCLEQ_INIT ( CIRCLEQ_HEAD head );[/i][/b] [b][i]CIRCLEQ_INSERT_AFTER ( CIRCLEQ_HEAD head , TYPE listelm , TYPE elm CIRCLEQ_ENTRY NAME );[/i][/b] [b][i]CIRCLEQ_INSERT_BEFORE ( CIRCLEQ_HEAD head , TYPE listelm , TYPE elm CIRCLEQ_ENTRY NAME );[/i][/b] [b][i]CIRCLEQ_INSERT_HEAD ( CIRCLEQ_HEAD head , TYPE elm , CIRCLEQ_ENTRY NAME );[/i][/b] [b][i]CIRCLEQ_INSERT_TAIL ( CIRCLEQ_HEAD head , TYPE elm , CIRCLEQ_ENTRY NAME );[/i][/b] [b][i]CIRCLEQ_REMOVE ( CIRCLEQ_HEAD head , TYPE elm , CIRCLEQ_ENTRY NAME );[/i][/b] [size=18] [b]Description[/b] [/size] 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 :[table][row][col]    [/col][col] [table][row][col]    [/col][col]Insertion d'un élément en tête de liste ;[/col][/row][/table] [table][row][col]    [/col][col]Insertion d'un élément après n'importe quel élément existant ;[/col][/row][/table] [table][row][col]    [/col][col]Suppression de n'importe quel élément ;[/col][/row][/table] [table][row][col]    [/col][col]Traversée séquentielle de la liste.[/col][/row][/table] Les listes simples ne supportent que les fonctionnalités ci-dessus.[/col][/row][/table] Les listes doubles ajoutent les fonctionnalités suivantes :[table][row][col]    [/col][col] [table][row][col]    [/col][col]Un élément peut être ajouté en fin de liste ;[/col][/row][/table] Toutefois :[table][row][col]    [/col][col][/col][/row][/table] [table][row][col]    [/col][col]Toutes les insertions et suppressions doivent mentionner la tête de la liste ;[/col][/row][/table] [table][row][col]    [/col][col]L'élement de tête nécessite deux pointeurs au lieu d'un seul ;[/col][/row][/table] [table][row][col]    [/col][col]La taille du code est environ 15% plus grande, et l'exécution environ 20% plus lente que les listes.[/col][/row][/table][/col][/row][/table] Les listes ciculaires ajoutent les fonctionnalités suivantes :[table][row][col]    [/col][col] [table][row][col]    [/col][col]Un élément peut être ajouté à la fin de la liste ;[/col][/row][/table] [table][row][col]    [/col][col]Un élément peut être ajouté avant n'importe quel autre élément ;[/col][/row][/table] [table][row][col]    [/col][col]On peut parcourir la file en sens inverse.[/col][/row][/table] Toutefois :[table][row][col]    [/col][col][/col][/row][/table] [table][row][col]    [/col][col]Toutes les insertions et suppressions doivent indiquer la tête de la liste ;[/col][/row][/table] [table][row][col]    [/col][col]L'élément de tête nécessite deux pointeurs au lieu d'un seul ;[/col][/row][/table] [table][row][col]    [/col][col]La condition de terminaison pour le parcours est plus compliquée ;[/col][/row][/table] [table][row][col]    [/col][col]La taille du code est environ 40% plus grande et l'exécution 45% plus lente que les listes simples.[table][row][col]    [/col][col][/col][/row][/table] Dans les définitions de macros, [i]TYPE[/i] est le nom d'une structure définie par l'utilisateur, qui doit contenir un champ de type [b]LIST_ENTRY ,[/b] [b]TAILQ_ENTRY ,[/b] ou [b]CIRCLEQ_ENTRY ,[/b] nommé [b]NAME .[/b] L'argument [i]HEADNAME[/i] est le nom d'une structure définie par l'utilisateur qui doit être déclarée en utilisant les macros [b]LIST_HEAD ,[/b] [b]TAILQ_HEAD ,[/b] ou [b]CIRCLEQ_HEAD .[/b] Voir les exemples plus bas pour une explication sur l'utilisation de ces macros. [size=18] [b]Listes simples[/b] [/size] Une liste débute par une structure définie par la macro [b]LIST_HEAD .[/b] 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 [b]LIST_HEAD[/b] est déclarée ainsi : .nf [b][i]LIST_HEAD( HEADNAME , TYPE ) head ;[/i][/b] .fi où [i]HEADNAME[/i] est le nom de la structure à définir, et [i]TYPE[/i] le type d'élément à lier dans la liste. Un pointeur sur la tête de la liste peut ensuite être déclaré ainsi : .nf [b][i]struct HEADNAME * headp ;[/i][/b] .fi (Les noms .Li head et .Li headp sont choisis par l'utilisateur). La macro [b]LIST_ENTRY[/b] déclare une structure qui connecte les éléments dans la liste. La macro [b]LIST_INIT[/b] initialise la liste référencée par [b]head .[/b] La macro [b]LIST_INSERT_HEAD[/b] insère le nouvel élément [i]elm[/i] à la tête de la liste. La macro .Nm LIST_INSERT_AFTER insère le nouvel élément [i]elm[/i] après l'élément [i]listelm .[/i] La macro .Nm LIST_REMOVE supprime l'élément [i]elm[/i] de la liste. [b]Exemple de liste simple[/b] .nf 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); .fi [size=18] [b]Listes doubles[/b] [/size] La tête d'une liste double est désignée par une structure définie par la macro [b]TAILQ_HEAD .[/b] 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 : .nf [b][i]TAILQ_HEAD( HEADNAME , TYPE ) head ;[/i][/b] .fi où [i]HEADNAME[/i] est le nom de la structure à définir, et .Li 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 : .nf [b][i]struct HEADNAME headp ;[/i][/b] .fi (Les noms [i]head[/i] et [i]headp[/i] sont choisis par l'utilisateur). La macro [b]TAILQ_ENTRY[/b] déclare une structure qui connecte les éléments dans la liste double. La macro [b]TAILQ_INIT[/b] initialise la liste double référencée par [b]head .[/b] La macro [b]TAILQ_INSERT_HEAD[/b] insère le nouvel élement [i]elm[/i] à la fin de la liste double. La macro [b]TAILQ_INSERT_TAIL[/b] insère le nouvel élément [i]elm[/i] à la fin de la liste double. La macro [b]TAILQ_INSERT_AFTER[/b] inssère le nouvel élément [i]elm[/i] après l'élément [b]listelm .[/b] La macro [b]TAILQ_REMOVE[/b] supprime l'élément [i]elm[/i] de la liste double. [size=18] [b]Exemple de liste double[/b] [/size] .nf 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); .fi [size=18] [b]Liste circulaire[/b] [/size] La tête d'une liste circulaire est désignée par une structur définie par la macro [b]CIRCLEQ_HEAD .[/b] 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 [b]CIRCLEQ_HEAD[/b] est déclarée ainsi : .nf [b][i]CIRCLEQ_HEAD( HEADNAME , TYPE ) head ;[/i][/b] .fi où [i]HEADNAME[/i] est le nom de la structure à définir, et [i]TYPE[/i] 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 : .nf [b][i]struct HEADNAME headp ;[/i][/b] .fi (Les noms .Li head et .Li headp sont choisis par l'utilisateur). La macro [b]CIRCLEQ_ENTRY[/b] déclare une structure qui connecte les éléments dans la liste circulaire. La macro [b]CIRCLEQ_INIT[/b] initialise la liste circulaire référencée par [b]head .[/b] La macro [b]CIRCLEQ_INSERT_HEAD[/b] insère le nouvel élément [i]elm[/i] au début de la liste circulaire. La macro [b]CIRCLEQ_INSERT_TAIL[/b] insère le nouvel élément [i]elm[/i] à la fin de la liste circulaire. La macro [b]CIRCLEQ_INSERT_AFTER[/b] insère le nouvel élément [i]elm[/i] après l'élément [b]listelm .[/b] La macro [b]CIRCLEQ_INSERT_BEFORE[/b] insère le nouvel élément [i]elm[/i] avant l'élément [b]listelm .[/b] La macro [b]CIRCLEQ_REMOVE[/b] supprime l'élément [i]elm[/i] de la liste circulaire. [size=18] [b]Exemple de liste circulaire[/b] [/size] .nf 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); .fi [size=18] [b]Historique[/b] [/size] Les fonctions de liste sont apparues dans BSD 4.4 [size=18] [b]Traduction[/b] [/size] Christophe Blaess, 2003.
Fichier