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.

Tags: C
comments powered by Disqus