Utilisation générique des listes chaînées

Version imprimable

12/02/2008, 23h07
Haze.

Utilisation générique des listes chaînées
Bonjour,

J'ai quelques questions sur l'utilisation des listes chaînées, ou plutôt de la bonne utilisation des types abstraits.

Dans tous les exemples que j'ai lu, la structure qui représente le maillon d'une liste n'est composée que de deux éléments.
Par exemple, la déclaration du type Node dans le header du composant de liste :
Code:

1 2 3 4 5 typedef struct s_Node { int valeur; struct s_Node* next; } Node;
Mais en cours, la réutilisation des composants techniques (dits « abstraits », par opposition aux composants techniques) est fortement encouragée.
On ajoute alors un header Item.h, qui se limite à un simple :
typedef MonTypeMetier Item;
puis le header Item.h est inclu dans le header du composant liste (ce que j'appelle composant est le code des fonctions .c et son header .h associé).
Il suffit alors de modifier le typedef dans le header Item.h pour obtenir un semblant de généricité :
Code:

1 2 3 4 5 6 7 #include "Item.h" typedef struct s_Node { Item valeur; struct s_Node* next; } Node;
Bon, j'en viens aux faits : je travaille sur un projet qui fait une utilisation importante des listes chaînées, et j'ai quelques problèmes d'organisation de code :

1) Mes « items » sont alloués dynamiquement et sont très nombreux (plusieurs dizaines de milliers).
Déjà ça m'ennuyait un peu de faire un typedef sur un type pointeur (pas de raison particulière, c'est juste que j'aime conserver le symbole * sur les pointeurs), et par soucis d'optimisation, j'ai choisi de « fusionner » les types Node et Item.
Ça me permet de réduire le nombre d'allocations :
Code:

1 2 3 4 5 6 7 8 typedef struct s_Item { /* une demi-douzaine d'éléments « métiers » */ struct s_Item* next; } Item;
Le header de mon composant Item est alors inclu dans le header de mon composant liste, ce dernier n'ayant plus besoin du type Node.

Ce mélange des éléments n'est-il pas un peu crade ?
Comment garder une disctinction entre les composants métiers et techniques, sans augmenter le nombre d'allocations mémoire ?
Est-ce que cette pratique est courante ? Ou bien au contraire, les maillons des listes chaînées ne contiennent toujours que deux éléments, la valeur et le pointeur « next » ?

2) Autre question, plus axé technique :
Imaginons que je veuille utilisé mon composant de liste avec des types « items » différents (c'est à dire manipuler une liste d'items A (issu d'un composant A) et une liste d'items B (issu d'un composant B).
Je fais comment ?! :?

Merci d'avance.
12/02/2008, 23h42
aoyou
Déjà, c'est un très bon réflexe de séparer métier et technique.
Je trouve peu propre de changer le type manipulé par la liste par un typedef bien placé dans un autre header. T'es-tu penché sur les listes génériques avec utilisation de void* ? C'est ce qui est le plus souvent fait.
Code:

1 2 3 4 5 typedef struct s_Node { void * data; struct s_Node * suite; } Node;
Ceci répond du coup à ta seconde question... Je te laisse creuser.

Par conséquent, il paraît difficile de ne faire qu'une allocation (réponse à ta première question). Pour les listes doublement chaînées, on rencontre aussi un pointeur "précédent" en plus du pointeur suite.

Voici un exemple d'école:

Code:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
/* -tc- fichier slist.h */
#ifndef H_TC_SLIST_20080213103210
#define H_TC_SLIST_20080213103210
 
#ifdef __cplusplus
extern "C" {
#endif
 
typedef struct Node Node_s;
typedef struct SList SList_s;
 
/* -tc- constructeur */
SList_s *slist_new(void);
/* -tc- destructeur */
void slist_delete(SList_s **self);
/* -tc- ajoute un element en queu de liste */
int slist_add(SList_s *self, void *data, size_t size);
/* -tc- affiche la liste */
void slist_display(SList_s *self, void (*cb_display)(void *));
 
#ifdef __cplusplus
}
#endif
 
#endif /* guard H_TC_SLIST_20080213103210 */

Code:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
/* -tc- fichier slist.c */
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include "slist.h"
 
struct Node {
    void *data;
    Node_s *next;
};
 
struct SList {
    Node_s *first;
    Node_s *last;
};
 
SList_s *slist_new(void)
{
    SList_s *this = NULL;
 
    this = malloc(sizeof *this);
    if (this != NULL)
    {
        /* -tc- initialisation */
        static SList_s tmp = {NULL, NULL};
        *this = tmp;
    }
    return this;
}
 
void slist_delete(SList_s **self)
{
    if (self != NULL && *self != NULL)
    {
        SList_s *this = *self;
        Node_s *current = this->first;
        Node_s *tmp = NULL;
        /* -tc- liberation de chaque noeud et de la donnee associee */
        while (current != NULL)
        {
            tmp = current;
            current = current->next;
            free(tmp);
        }
        /* -tc- liberation de la liste */
        free(this);
        *self = NULL;
    }
}
 
int slist_add(SList_s *self, void *data, size_t size)
{
    int err = 0;
 
    if (self != NULL && data != NULL && size != 0)
    {
        Node_s *new = NULL;
 
        new = malloc(sizeof *new + size);
        if (new != NULL)
        {
            static Node_s tmp = {NULL, NULL};
            *new = tmp;
 
            new->data = new + 1;
            memcpy(new->data, data, size);
 
            if (self->first == NULL) /* -tc- la liste est vide */
            {
                self->first = new;
                self->last = self->first;
            }
            else /* -tc- la liste contient au moins 1 element */
            {
                self->last->next = new;
                self->last = new;
            }
        }
        else
        {
            /* -tc- impossible d'allouer la memoire demandee */
            err = 2;
        }
    }
    else
    {
        /* -tc- Erreur: argument invalide */
        err = 1;
    }
 
    return err;
}
 
void slist_display(SList_s *self, void (*cb_display)(void *))
{
    if (self != NULL)
    {
        Node_s *current = NULL;
 
        for (current = self->first; current != NULL; current = current->next)
        {
            /* -tc- appel de la fonction de rappel destinee a l'affichage */
            cb_display(current->data);
        }
        printf("\n");
    }
}

et un exemple d'utilisation:

Code:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
#include <stdio.h>
#include <stdlib.h>
#include "slist.h"
 
#define LENGTH(array) ( sizeof (array) / sizeof *(array) )
 
typedef struct Point Point_s;
 
struct Point {
    double x;
    double y;
};
 
void display_points(void *self)
{
    if (self != NULL)
    {
        Point_s *pt = self;
        printf("Pt(%.1f, %.1f) ", pt->x, pt->y);
    }
}
 
void display_int(void *self)
{
    if (self != NULL)
    {
        int *data = self;
        printf("%d ", *data);
    }
}
 
int main(void)
{
    SList_s *list = NULL;
    Point_s points[] = {{1,2},{10,20},{100,200},{1000,2000}};
    int integers[] = {1,2,3,4,5};
 
    /* -tc- construction d'une liste de points */
    list = slist_new();
    if (list != NULL)
    {
        size_t i;
 
        for (i = 0; i < LENGTH(points); i++)
        {
            slist_add(list, points + i, sizeof *points);
        }
        slist_display(list, display_points);
        slist_delete(&list);
    }
 
    /* -tc- construction d'une liste d'entiers */
    list = slist_new();
    if (list != NULL)
    {
        size_t i;
 
        for (i = 0; i < LENGTH(integers); i++)
        {
            slist_add(list, integers + i, sizeof *integers);
        }
        slist_display(list, display_int);
        slist_delete(&list);
    }
 
    return 0;
}

J'ai pas testé à fond et j'espère ne pas avoir trop fait d'erreur, mais le principe est là.

Thierry

Merci à vous deux pour vos réponses très complètes :)

Citation:

Envoyé par aoyou

T'es-tu penché sur les listes génériques avec utilisation de void* ?

Oui, j'avais un peu cherché de ce côté là, mais j'avais des difficultés avec les pointeurs de fonctions.
Heureusement, Thierry a anticipé mes questions et ses exemples sont très clairs.
L'idée des fonctions qui respectent un « patron » me fait un peu penser aux fonctions de callback, en GTK+ par exemple...

D'ailleurs je pense plutôt les mettre dans la structure Liste, ça me permet de mémoriser les pointeurs de fonctions une fois pour toutes :
Code:

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 typedef struct { /* compare les données des nodes (pour un tri par insertion) */ int (*f_cmp)(void *, void*); /* destructeur */ void (*f_del)(void *); Node* p_head; /* tête de liste */ } Liste; void l_init(Liste* self, int (*f_cmp)(void *, void *), void (*f_del)(void *)) { self->p_head = NULL; self->f_cmp = f_cmp; self->f_del = f_del; }
Et avoir ainsi un ersatz de polymorphisme pour mes fonctions l_insert et l_delete.

Citation:

Envoyé par aoyou

on rencontre aussi un pointeur "précédent" en plus du pointeur suite.

Oui effectivement, je n'aurais pas du généraliser en parlant de « seulement deux éléments ».

@Thierry Chappuis : j'ai regardé attentivement ton composant de liste, mais il y a quelques points que je ne comprends pas :

1) Pourquoi utiliser l'allocation dynamique pour SList_s ?
Je ne vois pas ce que ça apporte pour le code client, il me semble que celui-ci aurait pu directement déclarer une variable de type SList_s.

2) Ce passage :
Code:

1 2 3 4 5 6 7 8 this = malloc(sizeof *this); if (this != NULL) { /* -tc- initialisation */ static SList_s tmp = {NULL, NULL}; *this = tmp; }
qui se trouve dans la fonction slist_new, m'intrigue.
Pourquoi ne pas faire tout simplement :
Code:

1 2 3 4 5 6 7 this = malloc(sizeof *this); if (this != NULL) { this->first = NULL; this->last = NULL; }
Même remarque pour le nouveau Node dans la fonction slist_add.
Et pourquoi le mot-clef static ? Je n'en comprends pas l'intérêt.

Encore merci.

14/02/2008, 07h47
Thierry Chappuis
Citation:

Envoyé par Haze.

@Thierry Chappuis : j'ai regardé attentivement ton composant de liste, mais il y a quelques points que je ne comprends pas :

1) Pourquoi utiliser l'allocation dynamique pour SList_s ?
Je ne vois pas ce que ça apporte pour le code client, il me semble que celui-ci aurait pu directement déclarer une variable de type SList_s.

Cela me permet d'utiliser des types opaques avec une encapsulation complète de mon type abstrait de donnée.
Citation:
Envoyé par Haze.

2) Ce passage :

Code:

1 2 3 4 5 6 7 8 this = malloc(sizeof *this); if (this != NULL) { /* -tc- initialisation */ static SList_s tmp = {NULL, NULL}; *this = tmp; }

qui se trouve dans la fonction slist_new, m'intrigue.
Pourquoi ne pas faire tout simplement :

Code:

1 2 3 4 5 6 7 this = malloc(sizeof *this); if (this != NULL) { this->first = NULL; this->last = NULL; }

Même remarque pour le nouveau Node dans la fonction slist_add.
Et pourquoi le mot-clef static ? Je n'en comprends pas l'intérêt.

Encore merci.
En général, je fais:
Code:

1 2 3 4 5 6 7 8 this = malloc(sizeof *this); if (this != NULL) { /* -tc- initialisation */ static SList_s tmp = {0}; *this = tmp; }
Ce code est tout à fait valide mais il faut désactiver une option d'avertissement de gcc qui gueule car certains membres de la structure tmp ne sont pas initialisés explicitement.

Il n'y a pas de réel gain ici, car SList_s ne possède que deux champs, mais lorsqu'il y en a beaucoup plus, c'est une technique portable pour initialiser tous les champs d'une structure à la valeur nulle correspondante (on pourrait utiliser memset(), mais la norme ne garantit pas que 0.0 ou NULL sont représentés avec tous les bits à zéro). J'utilise cette technique systématiquement dans mes constructeurs.

En ce qui concerne les pointeurs de fonctions que tu encapsule dans la structure de type Liste, je ne pense pas que c'est la bonne méthode. Si on veut quelque chose qui ressemble à du "Duck Typing" à la Python, c'est plutôt le type des éléments que tu stockes dans ta liste (par exemple Point_s dans mon exemple) et non la liste elle-même qui devrait encapsuler un pointeur de fonction afficher(), compare(), copier().

Thierry
14/02/2008, 09h23
Emmanuel Delahaye
Citation:
Envoyé par Haze.

2) Ce passage :

Code:

1 2 3 4 5 6 7 8 this = malloc(sizeof *this); if (this != NULL) { /* -tc- initialisation */ static SList_s tmp = {NULL, NULL}; *this = tmp; }

qui se trouve dans la fonction slist_new, m'intrigue.
Pourquoi ne pas faire tout simplement :

Code:

1 2 3 4 5 6 7 this = malloc(sizeof *this); if (this != NULL) { this->first = NULL; this->last = NULL; }

Même remarque pour le nouveau Node dans la fonction slist_add.
Et pourquoi le mot-clef static ? Je n'en comprends pas l'intérêt.
Détails ici :

http://emmanuel-delahaye.developpez.com/tad.htm
14/02/2008, 13h16
Haze.

Citation:

Envoyé par Thierry Chappuis

Il n'y a pas de réel gain ici, car SList_s ne possède que deux champs, mais lorsqu'il y en a beaucoup plus, c'est une technique portable pour initialiser tous les champs d'une structure à la valeur nulle correspondante (on pourrait utiliser memset(), mais la norme ne garantit pas que 0.0 ou NULL sont représentés avec tous les bits à zéro). J'utilise cette technique systématiquement dans mes constructeurs

D'accord.
Emmanuel, j'avais déjà lu ton article sur les TAD, mais une relecture s'impose :)
Si je comprends bien, le mot-clef static est là uniquement pour éviter de redéclarer une variable SList_s à chaque appel de la fonction-constructeur ?
La zone mémoire de cette variable est-elle réservée avant le premier appel de la fonction ?

Citation:

Envoyé par Thierry Chappuis

En ce qui concerne les pointeurs de fonctions que tu encapsule dans la structure de type Liste, je ne pense pas que c'est la bonne méthode.

En quoi ma méthode n'est pas bonne ? Je trouve ça plutôt pratique, tout est défini dès l'appel du constructeur, et je n'ai plus à m'embêter avec un pointeur de fonction reçu en paramètre à chaque fois que je veux manipuler ma liste. Le code client n'en sera que plus clair.
Mais d'un autre côté, ma maigre expérience ne me permet pas d'avoir un jugement avisé, disons juste que j'essaie d'expérimenter différentes solutions et cette trouvaille me plaisait bien.

Citation:

Envoyé par Thierry Chappuis

du "Duck Typing" à la Python

Oui ! :mrgreen:

Citation:

Envoyé par Thierry Chappuis

c'est plutôt le type des éléments que tu stockes dans ta liste

Stocker un type de données dans un élément d'une structure ?
Je ne vois vraiment pas comment réaliser une telle chose (un type pourrait être traiter comme une valeur ?!), un exemple serait le bienvenu.