Petite présentation de sys/queue.h

Dans vos programmes C, il arrive très fréquemment d’utiliser des listes chaînée (de toutes sortes), afin de ne pas avoir à recréer le monde à chaque fois vous pouvez utiliser les macros super pratiques de queue(3). Voici une petite introduction à l’utilisation de sys/queue.h avant d’aller se plonger dans le man pour aller plus loin.

Avec sys/queue.h , vous pouvez manipuler facilement quatres sortes de listes :

  • Listes simplement chainées (SLIST) de type pile
  • Listes doublement chainées (LIST) de type pile
  • Listes simplement chainées (STAILQ) de type file
  • Listes doublement chainées (TAILQ) de type file

Voici un exemple de SLIST :

Le header :

#ifndef HEADER_H
#define HEADER_H
#include <sys/queue.h>
typedef struct MaStruct {
/* ici on met nos elements par exemple : */
char *str;
/*
* On déclare notre liste avec SLIST_ENTRY qui est equivalente à
* struct { struct MaStruct *sle_next; } next;
*/
SLIST_ENTRY(MaStruct) next;
} MaStruct;
#endif /* HEADER_H */

Ensuite voyons comment manipuler cette liste :

#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include "header.h"
int
main(void)
{
/* SLIST_HEAD crée une variable pour acceder à notre liste */
SLIST_HEAD(, MaStruct) head;
/* on crée un element MaStruct */
MaStruct *p;
/* On l'initialise à NULL */
SLIST_INIT(&head);
p = malloc(sizeof(*p));
p->str = malloc(sizeof(char) * 10);
strcpy(p->str, "blah");
/* On insere p dans la SLIST */
SLIST_INSERT_HEAD(&head, p, next);
/* On empile un deuxième element */
p = malloc(sizeof(*p));
p->str = malloc(sizeof(char) * 10);
strcpy(p->str, "blu");
SLIST_INSERT_HEAD(&head, p, next);
/*
* Il est très facile de parcourir la liste
* que ce soit pour du traitement ou de
* la libération de mémoire
*/
SLIST_FOREACH(p, &head, next) {
/* ici p est l'element courant */
printf("element : %s\n", p->str);
}
/* exemple de libération */
while (!SLIST_EMPTY(&head))
{
p = SLIST_FIRST(&head);
SLIST_REMOVE_HEAD(&head);
free(p->str);
free(p);
}
return 0;
}

Parmis les macros interessantes pour les SLIST il y a :

SLIST_FIRST(&head);                /* renvoie la tête de liste */
SLIST_REMOVE_HEAD(&head, next);    /* supprime la tete de liste */
SLIST_EMPTY(&head); /* renvoie vrai si la liste est vide */

Ben entendu, il y a beaucoup plus de possibilités avec LIST et TAILQ… Mais globalement vous devriez avoir compris le principe.

La lecture de sys/queue.h devrait vous éclairer pour comprendre comment marchent toutes ces macros, c’est assez facile à comprendre si vous avez (comme moi) un niveau moyen en C.

Voyez aussi ce papier d’iMil.