Differences

This shows you the differences between two versions of the page.

Link to this comparison view

codaz:c:sys_queue.h [2010/01/12 13:29] (current)
Line 1: Line 1:
 +Utilisation de <​sys/​queue.h>​ pour travailler avec des listes chainees
 +=====================================================================
 +iMil - 08/2004
 +
 +Dans cet exemple on utilsera les macros SLIST qui decrivent des operations
 +sur des listes simplement chainees, l'​utilisation des macros LIST, TAILQ et 
 +STAILQ sont similaires. Pour plus d'​informations,​ reportez-vous au man 3 queue.
 +
 +
 +On declare tout d'​abord une structure de type liste chainee de maniere -presque-
 +habituelle.
 +<code c>
 +struct mastruct {
 + char *truc;
 + int bidule;
 + SLIST_ENTRY(mastruct) next;
 +};
 +</​code>​
 +SLIST_ENTRY n'est en realite qu'un #define de :
 +<code c>
 +struct {
 + struct type *sle_next; ​ /* prochain element */
 +}
 +</​code>​
 +on pourrait donc parfaitement l'​ecrire de cette facon :
 +<code c>
 +struct mastruct {
 + char *truc;
 + int bidule;
 + struct { struct mastruct *sle_next } next;
 +};
 +</​code>​
 +Ce qui equivaut a l'​ecriture habituelle d'une structure de type liste chainee.
 +
 +Poursuivons :
 +<code c>
 +SLIST_HEAD(slisthead,​ mastruct) head = SLIST_HEAD_INITIALIZER(head);​
 +</​code>​
 +qu'on peut plus simplement ecrire :
 +<code c>
 +SLIST_HEAD(,​ mastruct) head = SLIST_HEAD_INITIALIZER(head);​
 +</​code>​
 +Derriere cette affectation se cache une bete initialisation,​ en effet,
 +sys/queue.h nous montre :
 +<code c>
 +#define SLIST_HEAD(name,​ type) struct name { struct type *slh_first; }
 +</​code>​
 +ou slh_first est le 1er element de la liste, et :
 +<code c>
 +#define SLIST_HEAD_INITIALIZER(head) { NULL }
 +</​code>​
 +Finalement l'​affectation peut s'​ecrire :
 +<code c>
 +struct { struct mastruct *slh_first; } head = { NULL }
 +</​code>​
 +On aurait pu egalement utiliser cette methode
 +<code c>
 +SLIST_INIT(&​head);​
 +</​code>​
 +ou SLIST_INIT correspond a :
 +<code c>
 +(head)->​slh_first = NULL;
 +</​code>​
 +Maintenant que notre liste est initialisee,​ on peut y inserer des elements,
 +par exemple comme ceci :
 +<code c>
 +struct mastruct *element = malloc(sizeof(struct mastruct));
 +
 +/*
 + * tests et remplissage de "​element"​
 + * ...
 + */
 +
 +/* on insere maintenant l'​element en tete de liste */
 +
 +SLIST_INSERT_HEAD(&​head,​ element, next);
 +
 +Cette macro est definie comme ceci :
 +
 +#define SLIST_INSERT_HEAD(head,​ elm, field) do {                        \
 +        (elm)->​field.sle_next = (head)->​slh_first; ​                     \
 +        (head)->​slh_first = (elm); ​                                     \
 +} while (/​*CONSTCOND*/​0)
 +</​code>​
 +- on attache le 1er element de head au "​next"​ de "​element"​
 +- la nouvelle tete de liste est l'​element cree
 +
 +On peut parcourir la liste grace a la macro SLIST_FOREACH,​ elle s'​utilise de
 +cette facon :
 +<code c>
 +SLIST_FOREACH(element_courant,​ &head, next) {
 + /* 
 + * dans cette boucle, on traverse la liste et on travaille ​
 +         * sur "​element_courant"​
 + */
 +}
 +</​code>​
 +On pourrait également passer SLIST_FIRST(&​head),​ le 1er élément de la liste
 +donc, en paramètre à une fonction de cette facon :
 +<code c>
 +err = fonction(SLIST_FIRST(&​head));​
 +</​code>​
 +puis dans la fonction appelée
 +<code c>
 +int
 +fonction(struct mastruct *premier)
 +{
 + struct mastruct *p = premier;
 + ...
 + for (; p != NULL; SLIST_NEXT(p,​ next)) {
 + ...
 + }
 + ...
 +}
 +</​code>​
 +Finalement, on libere tres facilement la liste en faisant :
 +<code c>
 +while (!SLIST_EMPTY(&​head)) {
 + element_courant = SLIST_FIRST(&​head);​
 + SLIST_REMOVE_HEAD(&​head,​ next);
 + free(element_courant->​truc);​
 + free(element_courant);​
 +}
 +</​code>​
 +NB, la lecture rapide de sys/queue.h vous eclairera certainement quand a
 +certaines macros pour lesquelles vous trouveriez le man trop laconique.
 +
 +iMil
  
codaz/c/sys_queue.h.txt · Last modified: 2010/01/12 13:29 (external edit)