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.

struct mastruct {
	char *truc;
	int bidule;
	SLIST_ENTRY(mastruct) next;
};

SLIST_ENTRY n'est en realite qu'un #define de :
struct {
	struct type *sle_next;  /* prochain element */
}

on pourrait donc parfaitement l'ecrire de cette facon :
struct mastruct {
	char *truc;
	int bidule;
	struct { struct mastruct *sle_next } next;
};

Ce qui equivaut a l'ecriture habituelle d'une structure de type liste chainee.

Poursuivons :

SLIST_HEAD(slisthead, mastruct) head = SLIST_HEAD_INITIALIZER(head);

qu'on peut plus simplement ecrire :

SLIST_HEAD(, mastruct) head = SLIST_HEAD_INITIALIZER(head);

Derriere cette affectation se cache une bete initialisation, en effet,
sys/queue.h nous montre :

#define SLIST_HEAD(name, type) struct name { struct type *slh_first; }

ou slh_first est le 1er element de la liste, et :

#define SLIST_HEAD_INITIALIZER(head) { NULL }

Finalement l'affectation peut s'ecrire :

struct { struct mastruct *slh_first; } head = { NULL }

On aurait pu egalement utiliser cette methode

SLIST_INIT(&head);

ou SLIST_INIT correspond a :

(head)->slh_first = NULL;

Maintenant que notre liste est initialisee, on peut y inserer des elements,
par exemple comme ceci :

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)

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

SLIST_FOREACH(element_courant, &head, next) {
	/* 
	 * dans cette boucle, on traverse la liste et on travaille 
         * sur "element_courant"
	 */
}

On pourrait également passer SLIST_FIRST(&head), le 1er élément de la liste
donc, en paramètre à une fonction de cette facon :

err = fonction(SLIST_FIRST(&head));

puis dans la fonction appelée

int
fonction(struct mastruct *premier)
{
	struct mastruct *p = premier;
	...
	for (; p != NULL; SLIST_NEXT(p, next)) {
		...
	}
	...
}

Finalement, on libere tres facilement la liste en faisant :

while (!SLIST_EMPTY(&head)) {
	element_courant = SLIST_FIRST(&head);
	SLIST_REMOVE_HEAD(&head, next);
	free(element_courant->truc);
	free(element_courant);
}

NB, la lecture rapide de sys/queue.h vous eclairera certainement quand a
certaines macros pour lesquelles vous trouveriez le man trop laconique.

iMil