Structures de données en C/Les itérateurs

Cours

Les itérateurs permettent un parcours élégant d'une collection d'objet. Ils doivent obéir à des règles strictes; ils permettent de :

parcourir une collection,
savoir s'il existe un élément suivant dans la collection,
récupérer le prochain élément de la collection.

Certains itérateurs :

ne permettent pas de modification de la collection pendant leur utilisation,
permettent l'insertion ou le retrait d'élément avant ou après l'élément courant

Type des itérateurs en C

Un itérateur est composé :

d'une collection,
d'un état courant,
d'une fonction de destruction de la mémoire occupée par l'état courant,
d'une fonction permettant de savoir s'il existe encore un élément dans l'itérateur,
d'une fonction permettant de récupérer l'élément courant de l'itérateur,
d'une fonction permettant de passer à l'élément suivant.

Dans le fichier iterator.c les types sont déclarés de la manière suivante :

typedef void *(*IteratorCreateStateFunc) (const void *, va_list);
typedef void (*IteratorDestroyStateFunc) (void *);
typedef int (*IteratorHasDataFunc) (const void *);
typedef void *(*IteratorDataFunc) (void *);
typedef void *(*IteratorNextFunc) (void *);

typedef struct s_Iterator Iterator;
struct s_Iterator
{
    const void *collection;
    void *state;
    IteratorDestroyStateFunc destroy;
    IteratorHasDataFunc has_data;
    IteratorDataFunc data;
    IteratorNextFunc next;
};

/*
 * Définition de la taille réelle de la structure Iterator
 */
const size_t iterator_size = sizeof(Iterator);

Dans l'entête iterator.h, la vision n'est pas la même. C'est une technique répandue pour ne montrer dans l'entête que ce que l'utilisateur de la bibliothèque de fonctions doit voir.

typedef void *(*IteratorCreateStateFunc) (const void *, va_list);
typedef void (*IteratorDestroyStateFunc) (void *);
typedef int (*IteratorHasDataFunc) (const void *);
typedef void *(*IteratorDataFunc) (void *);
typedef void *(*IteratorNextFunc) (void *);

typedef struct s_Iterator Iterator;
struct s_Iterator
{
    const void *collection;
};

extern const size_t iterator_size;

Création d'un itérateur

Deux fonctions classiques pour initialiser le contenu d'une structure en C.

iterator_init permet d'initialiser le contenu de la mémoire pointée par iterator
iterator_create alloue de la mémoire, fait appel à iterator_init et retourne l'itérateur ainsi créé.

void
iterator_init (Iterator * iterator,
 	       IteratorDestroyStateFunc destroy,
 	       IteratorHasDataFunc has_data,
               IteratorDataFunc data,
               IteratorNextFunc next,
               const void *collection,
               void *state)
{
   iterator->destroy = destroy;
   iterator->has_data = has_data;
   iterator->data = data;
   iterator->next = next;
   iterator->collection = collection;
   iterator->state = state;
}

Iterator *
iterator_create (IteratorCreateStateFunc create,
 		 IteratorDestroyStateFunc destroy,
 		 IteratorHasDataFunc has_data,
                 IteratorDataFunc data,
                 IteratorNextFunc next,
                 const void *collection,
                 ...)
{
    Iterator *iterator = malloc(sizeof(*iterator));
    if (iterator != null)
    {
        va_list ap;
        void *state;
        va_start (ap, collection);
        state = create(collection, ap);
        va_end (ap);
        if (state)
        {
 	    iterator_init(iterator, destroy, has_data, data, next, collection, state);
        }
        else
        {
 	    free(iterator);
 	    iterator = NULL;
 	}
    }
    return iterator;
}

Destruction d'un itérateur

Deux fonctions de destructions :

iterator_erase permet de libérer la mémoire utilisée par l'état de l'itérateur
iterator_destroy fait appel à iterator_erase et libère la mémoire utilisée par l'itérateur (celle allouée dans iterator_create)

void
iterator_erase (Iterator * iterator)
{
    if (iterator->destroy)
    {
       iterator->destroy(iterator->state);
    }
}
 
void
iterator_destroy (Iterator * iterator)
{
    iterator_erase(iterator);
    free(iterator);
}

Savoir si l'itérateur a encore un élément

La fonction iterator_has_data retourne un booléen et fait simplement appel au pointeur de fonction has_data stocké dans la structure de l'itérateur avec comme argument l'état courant de l'itérateur.

int
iterator_has_data(const Iterator * iterator)
{
    return iterator->has_data(iterator->state);
}

Récupérer la donnée courante de l'itérateur

La fonction iterator_data permet de récupérer la donnée courante de l'itérateur. Elle fait simplement appel au pointeur de fonction data stocké dans la structure de l'itérateur avec comme argument l'état courant de l'itérateur.

void *
iterator_data(Iterator * iterator)
{
    return iterator->data(iterator->state);
}

Passer à la donnée suivante

La fonction iterator_next calcule l'état suivant de l'itérateur

Iterator *
iterator_next (Iterator * iterator)
{
    void *state = iterator->next(iterator->state);
    if (state)
    {
     iterator->state = state;
    }
    else
    {
     iterator = NULL;
    }
    return iterator;
}

Exemple d'utilisation des itérateurs

 /*
  * test-array-iterator.c un programme de test pour illustrer l'utilisation des itérateurs en C
  *
  * Copyright (C) 2006  Christophe Demko contact@chdemko.com
  *
  * This library is free software; you can redistribute it and/or
  * modify it under the terms of the GNU Lesser General Public
  * License as published by the Free Software Foundation; either
  * version 2 of the License, or (at your option) any later version.
  *
  * This library is distributed in the hope that it will be useful,
  * but WITHOUT ANY WARRANTY; without even the implied warranty of
  * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the GNU
  * Lesser General Public License for more details.
  *
  * You should have received a copy of the GNU Lesser General Public
  * License along with this library; if not, write to the
  * Free Software Foundation, Inc., 59 Temple Place - Suite 330,
  * Boston, MA 02111-1307, USA.
  */
#include <stdlib.h>
#include <stdio.h>
#include <stdarg.h>

#include "iterator.h"

/*
 * La structure d'état de l'itérateur contient
 *   - la taille des éléments du tableau,
 *   - le pointeur sur l'élément courant
 *   - le pointeur juste après le tableau
 */
typedef struct s_ArrayIteratorState ArrayIteratorState;
struct s_ArrayIteratorState
{
    size_t size;
    void *current;
    void *end;
};

/*
 * la fonction array_iterator_state_create crée l'état initial de l'itérateur
 */
ArrayIteratorState *
array_iterator_state_create (void *array, va_list ap)
{
    ArrayIteratorState *state = malloc(sizeof(*state));
    if (state != NULL)
    {
        state->size = va_arg (ap, size_t);
        state->current = array;
        state->end = array + va_arg (ap, int) * state->size;
    }
    return state;
}

/*
 * la fonction array_iterator_has_data teste simplement si la donnée courante est valide
 */
int
array_iterator_has_data(ArrayIteratorState * state)
{
    return (state->current != state->end);
}

/*
 * la fonction array_iterator_data retourne la donnée courante de l'itérateur
 */
void *
array_iterator_data(ArrayIteratorState * state)
{
    return state->current;
}

/*
 * la fonction array_iterator_next modifie et retourne l'état courant de l'itérateur
 */
ArrayIteratorState *
array_iterator_next(ArrayIteratorState * state)
{
    state->current += state->size;
    return state;
}

int
main(void)
{
    /*
     * déclaration et initialisation d'un tableau de 7 entiers
     */
    int a[] = { 1, 2, 3, 4, 5, 6, 7 };
    /*
     * déclaration et initialisation d'un itérateur sur tableau (Array)
     */
    Iterator *it = iterator_create ((IteratorCreateStateFunc) array_iterator_state_create,
 				  (IteratorDestroyStateFunc) free,
 				  (IteratorHasDataFunc) array_iterator_has_data,
 				  (IteratorDataFunc) array_iterator_data,
 				  (IteratorNextFunc) array_iterator_next,
 				  a,
 				  sizeof (*a),
 				  sizeof (a) / sizeof (*a));

    /*
     * Tant que l'itérateur possède un élément
     */
    while (iterator_has_data(it))
    {
        /*
         * afficher l'élément courant
         */
        printf("%d ", *(int *) iterator_data(it));
        /*
         * passer à l'élément suivant
         */
        it = iterator_next(it);
    }
    /*
     * afficher les pointeurs de a et it->collection (ils devraient être égaux)
     */
    printf("\nCollection is %p\na is %p\n", it->collection, a);
    /*
     * destruction de l'itérateur
     */
    iterator_destroy(it);
    return 0;
}

Ce programme produit sur la console la sortie suivante

1 2 3 4 5 6 7
Collection is 0xbfa2ed5c
a is 0xbfa2ed5c

Liens

Itérer sur les listes