Discussion :

[Marmoccelle]

Salut à tous


Je n'avais encore jamais étudié et encore moins travaillé avec des listes chainées, j'ai décidé de combler cette lacune.

A titre d'exercice je me suis donc monté une petite librairie pour les listes simplement chainées, dont voici quelques samples de code:

Dans le .h

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

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
 
/* One node of a Singly linked List */
typedef struct SNode    SNode;
struct SNode
{
    /* The data being stored in the node */
    int16u  Data;
 
    /* A pointer to the next node, NULL if last node */
    SNode*  Next;
};
 
 
/* Pointer to the Linked list (= pointer to the first node) */
typedef SNode*  SListPtr;
 
 
/******************************************************************************
 *  Add a node at the beginning of a list
 *
 * @param   ListPtr     pointer to the linked list
 *          ui16Value   Data to store in the first node
 *
 * @return  the pointer to the modified list if success (= ptr to the 1st node )
 *          NULL if failure
 *****************************************************************************/
SListPtr SLL_InsertNode(SListPtr ListPtr, int16u ui16Value);
 
/******************************************************************************
 *  Add a node after a specified Node
 *
 * @param   Node        Pointer to the node after which the new one will be
 *                      inserted
 *          ui16Value   Data to store in the new node
 *
 * @return  the pointer to the new node if success
 *          NULL if failure
 *****************************************************************************/
SNode* SLL_InsertNodeAfter(SNode* Node, int16u ui16Value);
 
/******************************************************************************
 *  Locate the first occurence of a value in a specified list.
 *
 * @param   LisPtr      pointer to the linked list
 *          ui16Value   The value to find
 *
 * @return  If SUCCESS returns a pointer to the node containing ui16Value
 *          Otherwise it returns a NULL pointer.
 *****************************************************************************/
SNode* SLL_SearchValue(SListPtr ListPtr, int16u ui16Value);
 
/******************************************************************************
 *  Remove the first node of a linked list.
 *
 * @param   ListPtr     pointer to the linked list
 *
 * @return  the pointer to the new list if success (= ptr to the 1st node)
 *          NULL if failure or if list had only 1 node
 *****************************************************************************/
SListPtr SLL_RemoveFirstNode(SListPtr ListPtr);

Dans le .c

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

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
 
SListPtr SLL_InsertNode(SListPtr ListPtr, int16u ui16Value)
{
    SListPtr NewNode = malloc(sizeof(SNode));
 
    if(NewNode != NULL)
    {
        /* If memory correctly allocated:
            - store the value in this new node
            - place this node at the beginning of the list */
        NewNode->Data = ui16Value;
        NewNode->Next = ListPtr;
    }
    return NewNode;
}
 
SNode* SLL_InsertNodeAfter(SNode* Node, int16u ui16Value)
{
    SNode* NewNode = NULL;
 
    if(Node != NULL)
    {
        NewNode = malloc(sizeof(SNode));
        if(NewNode != NULL)
        {
            /* If memory correctly allocated:
                - the previous element now become the next one
                - store value in this new node
                - previous node points to the new one */
            NewNode->Next = Node->Next;
            NewNode->Data = ui16Value;
            Node->Next = NewNode;
        }
    }
    return NewNode;
}
 
SListPtr SLL_SearchValue(SListPtr ListPtr, int16u ui16Value)
{
    /* Read the whole list to find ui16Value in a Node */
    while(ListPtr != NULL && ListPtr->Data != ui16Value)
    {
        ListPtr = ListPtr->Next;
    };
    return ListPtr;
}
 
SListPtr SLL_RemoveFirstNode(SListPtr ListPtr)
{
    SListPtr   TmpPtr = NULL;
 
    if(ListPtr != NULL)
    {
        /* Get the pointer to the second node and delete the 1st node */
        TmpPtr = ListPtr->Next;
        free(ListPtr);
    }
    return TmpPtr;
}

J'aimerais maintenant rendre ma structure "SNode" générique, de façon à pouvoir l'utiliser avec n'importe quel type de donnée (char, int, long, etc.), selon les besoins de l'utilisateur, sachant que toutes mes fonctions qui manipulent le champs "Data" ne réalisent strictement que de la copie (du paramètre de la fonction vers le nouveau noeud) ou de la lecture (recherche d'occurrence ou retour du champs "Data" du noeud N).


Je n'ai vraiment aucune idée de comment y parvenir (j'espère au moins que c'est possible ), je n'ai rien trouvé dans mes notes que j'ai faites sur le C.

Toutes critiques (constructive ) sur le code seront aussi les bienvenues

Merki !

[BainE]

bonjour,

la technique classique c'est un pointeur void* data (apres le nom...) dans ta structure "noeud", et des pointeurs sur fonction pour les travaux sur les données spécifiques (voir qsort par exemple).

exemple bidon mais pour la syntaxe :

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
 
int copyList( SListPtr old, SListPtr* new, int(*copyNode)(const void*, const void*)

ou copyNode sera une fonction hors de ta lib, chargée de recopier les info du pointeur void* data

[Emmanuel Delahaye]

J'aimerais maintenant rendre ma structure "SNode" générique, de façon à pouvoir l'utiliser avec n'importe quel type de donnée (char, int, long, etc.), selon les besoins de l'utilisateur, sachant que toutes mes fonctions qui manipulent le champs "Data" ne réalisent strictement que de la copie (du paramètre de la fonction vers le nouveau noeud) ou de la lecture (recherche d'occurrence ou retour du champs "Data" du noeud N).

Le principe est de séparer les données du chainage. Un nœud 'générique' devrait ressembler à ça :

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
4
5
6
7
8
9
10
 
struct node
{
   /* data */
   void *p_data;
 
   /* link */
   struct node *p_next;
 
};

La bibliothèque de liste chainée générique s'occupe alors exclusivement du chainage. Elle ne fait aucun traitement sur les données (qu'elle ignore), autre que de recevoir ou transmettre une adresse anonyme (void *) si nécessaire.

L'utilisateur a la charge de fournir des blocs de données d'une durée de vie suffisante. C'est lui qui gère les allocations/libérations si nécessaire.

Une couche logicielle intermédiaire gérant les allocations/libérations de données peut simplifier le codage de l'application.

http://emmanuel-delahaye.developpez.com/clib.htm
Module GLL

[Marmoccelle]

@BainE: je n'ai pas encore étudié le fonctionnement des pointeurs de fonction , mais d'après ce que tu dis, il faudra impérativement que l'utilisateur de la librairie se crée sa propre fonction de manipulation du champs void *Data alors?


@Emmanuel Delahaye: OK donc chaque nœud ne doit contenir que des pointeurs. Dans ce cas ça allège le code de la librairie, mais ça alourdit le code de celui qui utilise la librairie, puisque pour chaque nœud ajouté/supprimé, le programmeur devra jouer avec des malloc/free, c'est bien ça?
Donc dans ce type de configuration, je n'ai plus besoin de manipuler des pointeurs de fonction pour effectuer des opérations d'écritures/lectures du champs Data?

Merci pour vos réponses.

[Emmanuel Delahaye]

@Emmanuel Delahaye: OK donc chaque nœud ne doit contenir que des pointeurs. Dans ce cas ça allège le code de la librairie, mais ça alourdit le code de celui qui utilise la librairie, puisque pour chaque nœud ajouté/supprimé, le programmeur devra jouer avec des malloc/free, c'est bien ça?

Oui. L'utilisateur (de la bibliothèque) est responsable des données qu'il manipule. C'est logique, non ? Par nature, la bibliothèque ne sait rien des données manipulées (sinon, elle ne serait pas générique).

Donc dans ce type de configuration, je n'ai plus besoin de manipuler des pointeurs de fonction pour effectuer des opérations d'écritures/lectures du champs Data?

Effectivement, le traitement des données est de la responsabilité de l'utilisateur. Mais dans les actions de type 'traverse' (parcours de la liste), il peut être nécessaire d'utiliser les pointeurs de fonctions pour appeler le traitement utilisateur à chaque tour (callback).

Ca n'a rien de compliqué ni de mystérieux, mais comme c'est du traitement générique (donc non typé), il faut vraiment savoir ce qu'on fait.

Comme je l'ai déjà expliqué, une couche intermédiaire de traitement des données peut aider.

Il existe néanmoins une autre manière de traiter la généricité et s'appuyant sur la taille du bloc de données à traiter. C'est ce que fait qsort().

Le problème est que ça entraine pas mal de copies. Ce n'est donc pas forcément très performant.

Le noeud serait alors comme ceci :

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
4
5
6
7
8
9
10
11
 
struct node
{
   /* data */
   size_t size;
   void *p_data;
 
   /* link */
   struct node *p_next;
 
};

Là, c'est la bibliothèque qui alloue et libère le bloc.

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
 
/* ajout d'un élément */
ll_add(ll *this, void *data, size_t size);

utilisation :

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
4
5
 
{
   T obj;
 
   ll_add (list, &obj, sizeof obj);

il faudrait tester les deux implémentations et voir les performances, la facilité d'utilisation, le code utilisateur etc.

Beau projet de fin d'année...

[Marmoccelle]

Ok super, je pense avoir bien compris la philosophie du truc.

Je vais effectivement me retrouver face "au problème" d'utilisation des pointeurs de fonctions. Mais c'est pas grave, au contraire, cela me permettra de traiter ce sujet plus rapidement que prévu puisque j'ai 2 fonctions qui devraient en nécessiter (La seconde fonction fait appel à la première):

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
 
/******************************************************************************
 *  Locate the first occurence of a value in a specified list.
 *
 * @param   LisPtr      pointer to the linked list
 *          ui16Value   The value to find
 *
 * @return  If SUCCESS returns a pointer to the node containing ui16Value
 *          Otherwise it returns a NULL pointer.
 *****************************************************************************/
SNode* SLL_SearchValue(SListPtr ListPtr, int16u ui16Value);
 
/******************************************************************************
 *  Count the number of occurence(s) of a value in a specified list.
 *
 * @param   ListPtr     pointer to the linked list
 *          ui16Value   The value to find
 *
 * @return  The number of occurence(s) found in the list
 *****************************************************************************/
int16u SLL_CountOccurence(SListPtr ListPtr, int16u ui16Value);

Je n'ai par contre pas compris le but de cette couche intermédiaire dont tu fais mention. Quelle utilité aurait elle? le lien que tu m'a donné ne m'aide pas beaucoup ou plutôt, je ne sais pas comment l'exploiter



Concernant la seconde méthode, j'avais pensé à quelque chose dans ce genre, en ajoutant le champ "SizeOfData" et, dans chaque fonction de manipulation, réaliser X fois la copie/lecture d'un octet (X étant égal à SizeOfData), mais ça présente l'inconvénient de prendre 1 octet de plus en mémoire par nœud et travaillant principalement dans le domaine de l'embarqué, le gaspillage de RAM n'est pas forcément un luxe que l'on peut s'offrir.


D'ailleurs à ce sujet, j'aimerais pouvoir adapter des fonctions "dégradées" malloc/free pour les microcontroleurs. Est ce que je peux l'implémenter de la sorte:

Je réserve en mémoire une zone de X octets (accessible uniquement par les fonctions de la librairie d'allocation dynamique) sachant que 1 octet sera utilisé en tant que variable "compteur d'octets libre".

Puis pour les fonctions malloc/free
- incrémentation/décrémentation de ce compteur en fonction du nombre d'octets réservés/libérés
- pour malloc retour de la première adresse du bloc mémoire réservé si la place était suffisante, sinon NULL

Est ce que le principe de fonctionnement est celui ci, ou est ce beaucoup plus compliqué/complexe que je ne le pense?

Merci

[ram-0000]

En ce qui concerne le malloc/free sur micro controller, je connais 2 implémentations différentes.

• Allouer un grand bloc de mémoire et gérer dedans une liste chainée de bloc libres/occupés. Dans ce type de d'algo, tu peux demander des blocs de taille arbitraire et tu auras la taille que tu demandes (ou un peu plus mais tu ne le sais pas). Par contre, tu sera confronté tôt ou tard au problème de fragmentation de ton bloc de mémoire. C'est pas très b hon pour des applis qui doivent tourner des jours et des jours.
• En général, quand on développe en logiciel embarqué, on connais a peu près la taille des blocs demandés et en gros tu as 3 familles, petit, moyen et gros bloc avec chacun une taille différente. Dans ce cas, ton algo malloc/free peut aussi être de tailler 3 pool de blocs de mémoire et chaque bloc a un flag disant libre ou occupé. Ensuite, quand tu veux allouer, tu donnes le premier bloc libre de taille suffisante. Parcours très rapide pour rechercher un bloc libre et pas de problème fragmentation mais par contre, il faut bien anticiper le focntionnement de ton appli.

Dans les 2 cas, il faut prévoir que l'allocation/libération peut être multi thread donc il faut gérer les lock/unlock sinon, c'est le crash assuré.

[Emmanuel Delahaye]

Je n'ai par contre pas compris le but de cette couche intermédiaire dont tu fais mention. Quelle utilité aurait elle? le lien que tu m'a donné ne m'aide pas beaucoup ou plutôt, je ne sais pas comment l'exploiter

Comme toutes les couches logicielles, ça apporte un dégré d'abstraction qui facilite la manipulation des données, sans entrer dans les détails. Mais on en sent mieux l'utilité quand on a été confronté au problème. Ce n'est pas une priorité, juste un vieux réflexe de professionnel ...

Concernant la seconde méthode, j'avais pensé à quelque chose dans ce genre, en ajoutant le champ "SizeOfData" et, dans chaque fonction de manipulation, réaliser X fois la copie/lecture d'un octet (X étant égal à SizeOfData), mais ça présente l'inconvénient de prendre 1 octet de plus en mémoire par nœud et travaillant principalement dans le domaine de l'embarqué, le gaspillage de RAM n'est pas forcément un luxe que l'on peut s'offrir.

Euh, mal à la tête...

D'ailleurs à ce sujet, j'aimerais pouvoir adapter des fonctions "dégradées" malloc/free pour les microcontroleurs. Est ce que je peux l'implémenter de la sorte:

Je réserve en mémoire une zone de X octets (accessible uniquement par les fonctions de la librairie d'allocation dynamique) sachant que 1 octet sera utilisé en tant que variable "compteur d'octets libre".

Puis pour les fonctions malloc/free
- incrémentation/décrémentation de ce compteur en fonction du nombre d'octets réservés/libérés
- pour malloc retour de la première adresse du bloc mémoire réservé si la place était suffisante, sinon NULL

Est ce que le principe de fonctionnement est celui ci, ou est ce beaucoup plus compliqué/complexe que je ne le pense?

En embarqué, tu as tout à fait le droit d'utiliser le malloc()/free() de tabibliothèquenstandard si elle fournie les fonctions.

Sinon, l'usage est d'allouer statiquement des tabeaux de blocs de taille fixe en fonction de l'usage supposé et de gérer 2 listes par tableau (une 'libre', une 'occupée'.

Par exemple :

100 blocs de 32 bytes
50 blocs de 64 bytes
20 blocs de 128 bytes
10 blocs de 256 bytes

etc.

malloc() prend le premier bloc dans la liste libre de la taille >= à la taille demandé, et le déplace dans la liste 'occupé'.

exemple :

malloc (50) -> chercher dans la liste (64), sinon, 128 etc.

free() remet le bloc dans la liste 'libre'...

une étude statistique des la consommation des blocs (compteurs, fonction de lecture des compteurs) permet d'optimiser l'allocateur à l'usage réel de la mémoire.

[Marmoccelle]

En effet j'avais pas pensé le fonctionnement des fonctions d'allocation/libération en multithread... ce n'est plus simplement une pile que l'on remplit ou vide, ça devient légèrement plus complexe...

En tout cas merci pour toutes ces explications, j'ai de nouveau de quoi avancer


PS: les lib standard de mon µC n'offrent pas les fonctions malloc/free car pas énormément de RAM pour certaines références, c'est pour ça que je pensais les ré-écrire.

[Marmoccelle]

J'ai attaqué la modification de ma librairie, j'ai encore quelques petites questions avant d'aller plus loin.

fichier .h

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

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
 
/* One node of a Singly linked List */
typedef struct GSingleNode GSNode;
struct GSingleNode
{
    /* Data */
    void* Data;
 
    /* Link to the next node, NULL if last node */
    GSNode* Next;
};
 
typedef struct
{
    /* Pointer to the first node of a list */
    GSNode* HeadPtr;
 
}GSList;
 
 
/******************************************************************************
 *  Add a node at the beginning of a list
 *
 * @param   ListPtr     pointer to the linked list
 *
 * @return  the pointer to the new node if success
 *          NULL otherwise
 *****************************************************************************/
GSNode* GSLL_InsertNode(GSList* ListPtr);

fichier.c

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
 
GSNode* GSLL_InsertNode(GSList* ListPtr)
{
    GSNode* NewNode = malloc(sizeof(GSNode));
 
    if(NewNode != NULL)
    {
        /* If memory correctly allocated:
            - place the new node at the beginning of the list
            - Data pointer initialized to NULL */
        NewNode->Next = ListPtr->HeadPtr;
        NewNode->Data = NULL;
        ListPtr->HeadPtr = NewNode;
    }
    return NewNode;
}

Travail sur Data: main.c:

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

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
 
int main()
{
    GSNode* MyNodePtr = NULL;
    GSList MyList;
    int32s  VarTest1 = -245893;
    int32s  VarTest2 = 8459821;
    int32s  VarTest3 = -5478;
 
 
    MyList.HeadPtr = NULL;
 
 
    /* Creation d'un noeud */
    MyNodePtr = GSLL_InsertNode(&MyList);
    if(MyNodePtr != NULL)
        MyNodePtr->Data = &VarTest1;
 
    /* Creation d'un 2eme noeud */
    MyNodePtr = GSLL_InsertNode(&MyList);
    if(MyNodePtr != NULL)
        MyNodePtr->Data = &VarTest2;
 
    /* Creation d'un 3eme noeud */
    MyNodePtr = GSLL_InsertNode(&MyList);
    if(MyNodePtr != NULL)
        MyNodePtr->Data = &VarTest3;
 
    printf("Noeud 1: Data = %d\n",*(int32s*)MyList.HeadPtr->Data);
    printf("Noeud 2: Data = %d\n",*(int32s*)MyList.HeadPtr->Next->Data);
    printf("Noeud 3: Data = %d\n",*(int32s*)MyList.HeadPtr->Next->Next->Data);
 
	return 0;
}

A la compilation je n'ai ni warning ni erreur, cela fonctionne bien, mais j'ai un doute au niveau de la manière dont j'ai casté le champ data sur ces deux lignes:

if(MyNodePtr != NULL)
MyNodePtr->Data = &VarTest3;

et

printf("Noeud 1: Data = %d\n",*(int32s*)MyList.HeadPtr->Data);

Je trouve cette écriture assez lourde pour l'utilisateur, est simplement du fait de la généricité de ma librairie?

Concernant le prototype de la fonction, le format convient il ou vaudrait il mieux opter pour un prototype du style:

void GSLL_InsertNode(GSList* ListPtr, GSNode* NewNode);

plutôt que de retourner un pointeur sur le nouveau nœud?

[Emmanuel Delahaye]

J'ai attaqué la modification de ma librairie, j'ai encore quelques petites questions avant d'aller plus loin.

A la compilation je n'ai ni warning ni erreur, cela fonctionne bien, mais j'ai un doute au niveau de la manière dont j'ai casté le champ data sur ces deux lignes:

Euh, en principe, il n'y a rien à caster.

Concernant le prototype de la fonction, le format convient il ou vaudrait il mieux opter pour un prototype du style:

void GSLL_InsertNode(GSList* ListPtr, GSNode* NewNode);

plutôt que de retourner un pointeur sur le nouveau nœud?

Soit tu fais une étude préalable qui te donne la réponse (méthode classique)
Soit tu vois à l'usage (tests) et tu modifies en cas de problèmes (méthode agile).

Le bout de code que tu as montré fonctionne comme ceci :

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

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
 
#include "gs.h"
 
#include <stdio.h>
 
typedef long int32s;
 
int main (void)
{
   GSNode *MyNodePtr = NULL;
   GSList MyList;
   int32s VarTest1 = 1;
   int32s VarTest2 = 2;
   int32s VarTest3 = 3;
 
   MyList.HeadPtr = NULL;
 
   /* Creation d'un noeud */
   MyNodePtr = GSLL_InsertNode (&MyList);
   if (MyNodePtr != NULL)
      MyNodePtr->Data = &VarTest1;
 
   /* Creation d'un 2eme noeud */
   MyNodePtr = GSLL_InsertNode (&MyList);
   if (MyNodePtr != NULL)
      MyNodePtr->Data = &VarTest2;
 
   /* Creation d'un 3eme noeud */
   MyNodePtr = GSLL_InsertNode (&MyList);
   if (MyNodePtr != NULL)
      MyNodePtr->Data = &VarTest3;
 
/* lecture naive de la liste (préferer une boucle) */
   {
      int32s *a = MyList.HeadPtr->Data;
      int32s *b = MyList.HeadPtr->Next->Data;
      int32s *c = MyList.HeadPtr->Next->Next->Data;
 
      printf ("Noeud 1: Data = %ld\n", *a);
      printf ("Noeud 2: Data = %ld\n", *b);
      printf ("Noeud 3: Data = %ld\n", *b);
   }
   return 0;
}

(éviter les valeurs exotiques... )
A l'évidence, il y a un problème de chainage :

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
4
5
6
7
 
Noeud 1: Data = 3
Noeud 2: Data = 2
Noeud 3: Data = 2
 
Process returned 0 (0x0)   execution time : 0.036 s
Press any key to continue.

Regle #1 quand on manipule une liste chainée : commencer par écrire une fonction de lecture.

Regle #1 quand on fait de la programmation générique : cacher les données internes. L'utilisateur ne doit ni les voir ni les manipuler. Ca évite les âneries (et c'est un des buts de la programmation générique : encapsuler du code à l'épreuve des balles et de la curiosité malsaine de l'utilisateur).

Donc ça commence comme ça :
(visiblement, le nom retenu est "gs", j'espère que ça a un sens pour toi, sinon, le modifier tout de suite...

On commence par écrire le gs.h qui doit contenir des prototypes de fonctions et le minimum pour les définir :

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
 
/* gs.h */
 
/* on pourrait meme se passer de ca... */
struct gs_node;
typedef struct 
{
   struct gs_node *p_head;
   struct gs_node *p_tail;
}
gs_s;
 
/* de quoi demarrer proprement */
void gs_init (gs_s *p_gs);
 
/* ajouter une donne en queue de la liste */
int gs_add_tail (gs_s *p_gs, void *p_data);
 
/* lister */
/* retour callback : 0=stop 1=encore */
typedef int gs_cb_traverse_f (void *user, void *p_data);
void gs_traverse (gs_s *p_gs, gs_traverse_f *pf_callback, void *user);

Ajouter les protections contre les inclusions multiples...

Pose des questions si tu ne comprends pas.

Je propose de démarrer comme ça :

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

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
 
#ifndef H_ED_GS_20081106174138
#define H_ED_GS_20081106174138
 
#ifdef __cplusplus
extern "C"
{
#endif
 
/* gs.h */
 
/* on pourrait meme se passer de ca... */
   struct gs_node;
   typedef struct
   {
      struct gs_node *p_head;
      struct gs_node *p_tail;
   }
   gs_s;
 
/* de quoi demarrer proprement */
   void gs_init (gs_s * p_gs);
 
/* ajouter une donne en queue de la liste */
   void gs_add_tail (gs_s * p_gs, void *p_data);
 
/* lister */
   typedef int gs_traverse_f (void *user, void *p_data);
   int gs_traverse (gs_s * p_gs, gs_traverse_f * pf, void *user);
 
#ifdef __cplusplus
}
#endif
 
#endif                          /* guard */
 
/* Guards added by GUARD (c) ED 2000-2005 Jan 17 2005 Ver. 1.7 */

avec :

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

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
 
/* gs.c */
#include "gs.h"
 
#include <stdlib.h>
 
/* c'est ici qu'on trouve la definition complete de struct node
   l'utilisateur n'y a pas acces
*/
struct gs_node
{
   /* donnees  */
   void *p_data;
 
   /* chainage */
   struct gs_node *p_next;
};
 
/* de quoi demarrer proprement */
void gs_init (gs_s * p_gs)
{
   if (p_gs != NULL)
   {
      p_gs->p_head = NULL;
      p_gs->p_tail = NULL;
   }
}
 
/* ajouter une donne en queue de la liste */
void gs_add_tail (gs_s * p_gs, void *p_data)
{
   if (p_gs != NULL)
   {
      /* creer un noeud */
      struct gs_node *p_new = malloc (sizeof *p_new);
      if (p_new != NULL)
      {
             /* donnes */
         p_new->p_data = p_data;
         p_new->p_next = NULL;
 
         if (p_gs->p_head == NULL)
         {
            p_gs->p_head = p_new;
         }
         else
         {
            p_gs->p_tail->p_next = p_new;
         }
         p_gs->p_tail = p_new;
      }
   }
}
 
/* lister */
int gs_traverse (gs_s * p_gs, gs_traverse_f * pf, void *user)
{
   if (p_gs != NULL)
   {
      /* debut de la liste */
      struct gs_node *p = p_gs->p_head;
      int encore = 1;
      while (p != NULL && encore)
      {
         /* appeler la fonction de CB */
         if (pf != NULL)
         {
            encore = pf (user, p->p_data);
         }
 
         /* element suivant */
         p = p->p_next;
      }
   }
}

Ca gloute :

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
4
5
6
7
 
my list : 1
my list : 2
my list : 3
 
Process returned 0 (0x0)   execution time : 0.027 s
Press any key to continue.

et un peu de lecture pour cette nuit...

http://emmanuel-delahaye.developpez.com/tad.htm

[dj.motte]

Bonjour,

La bibliothèque de liste chainée générique s'occupe alors exclusivement du chainage. Elle ne fait aucun traitement sur les données (qu'elle ignore), autre que de recevoir ou transmettre une adresse anonyme (void *) si nécessaire.

L'utilisateur a la charge de fournir des blocs de données d'une durée de vie suffisante. C'est lui qui gère les allocations/libérations si nécessaire.

Une couche logicielle intermédiaire gérant les allocations/libérations de données peut simplifier le codage de l'application.

Les données comme adresses anonymes dans une liste cela réserve bien des surprises.

Si l'ajout d'un lien avec référence sur une donnée dépasse le cadre d'une fonction locale, le chainage reste intacte, mais pas les données.

Dans ce type de liste l'appelant doit gérer la mémoire allouée pour le stockage des données. Il est obligé de libérer la mémoire locale des données avec la libération de sa liste.

On peut aussi concevoir que le conteneur, une liste par exemple, se charge de la gestion de la mémoire pour les objets stockés, sans intervention de l'appelant, avec sa propre méthode de libération.

Le tout est de savoir si l'on entend stocker dans la liste des références ou des pointeurs. Des variables automatiques ou des zones mémoire.

[matafan]

Pour ce qui est de la libération de la mémoire, le mieux c'est encore que le système de gestion de liste fournisse un itérateur, que l'utilisateur peux utiliser pour libérer ses données si nécessaire.

Ca n'empèche pas si on veut de prévoir un flag dans le "desctucteur" de la liste chainée, pour déclancher si l'utilisateur le souhaite la libération des données elles même. Ca facilite la vie de l'utilisateur si toutes ses données sont allouée dynamiquement.

[Médinoc]

Tout cela peut se décider dans la couche intermédiaire.

[Marmoccelle]

@Emmanuel Delahaye:

En fait j'ai simplement collé quelques bouts de code de mon projet, mais toutes les règles que tu me décris font déjà partie de mes habitudes de programmation (je me suis beaucoup inspiré des conseils de ton site web).

on va reprendre tes remarques une à une:

A l'évidence, il y a un problème de chainage :

En effet, c'est le cas, mais simplement parce que la fonction utilisée est "InsertNode" qui ajoute un nœud en début de liste, donc forcément le premier nœud créé dans la liste se retrouve à la fin lorsque d'autres sont ajoutés.

Regle #1 quand on manipule une liste chainée : commencer par écrire une fonction de lecture.

Regle #1 quand on fait de la programmation générique : cacher les données internes. L'utilisateur ne doit ni les voir ni les manipuler. Ça évite les âneries (et c'est un des buts de la programmation générique : encapsuler du code à l'épreuve des balles et de la curiosité malsaine de l'utilisateur).

En effet, je l'avais fait dans la version précédente de la librairie. Mais étant donné la généricité de la librairie, comment afficher les données contenues dans un noeud ou une liste si l on ne connait pas le type de données pointés par *Data ?

Ta 2nde remarque découle sans doute de l'absence de cette fonction d'affichage qui fait que j'ai utilisé directement le chainage de la liste pour afficher les données pointées par *Data via un simple printf, ceci sera évidemment corrigé/supprimé.

Donc ça commence comme ça :
(visiblement, le nom retenu est "gs", j'espère que ça a un sens pour toi, sinon, le modifier tout de suite...

On commence par écrire le gs.h qui doit contenir des prototypes de fonctions et le minimum pour les définir :

En fait le nom retenu est GSLL (j'essaie en général de trouver un mnémonique de 3 lettres maxi) pour Generic Single Linked List... pas très original, mais c'est un de mes soucis, je manque d'imagination pour les noms de variables/fonctions...

On commence par écrire le gs.h qui doit contenir des prototypes de fonctions et le minimum pour les définir :
Ajouter les protections contre les inclusions multiples...

Tout ça je l'utilise déjà (grâce à ton site), j'ai simplement omis de collé le contenu intégral de mes fichiers dans mon message précédent.


Pour le reste, je vais étudier les bouts de code que tu as écris.


Par contre, la structure du nœud je n'aurais pas pensé la mettre dans le .c pour la dissimuler, je place systématiquement toutes mes définitions de structures dans les .h

[Marmoccelle]

Bon j'ai quand même quelques questions par rapport au code que tu m'as donné


Est il vraiment intéressant d'ajouter un pointeur sur le dernier nœud de la liste? En effet il permet d'accélérer l'exécution de la fonction "AddTail" en particulier en cas de liste longue pour éviter de parcourir tous les nœuds avant de tomber sur le dernier.
Mais si je dois implémenter la fonction "RemoveTail", ce pointeur ne me sera d'aucune utilité, puisque j'ai aussi besoin d'un pointeur sur l'avant dernier nœud, afin de mettre le champ "Next" à NULL et de faire pointer "Tail" sur l'avant dernier noeud, du coup je devrais tout de meme parcourir l'intégralité de la liste n'est ce pas?


Ensuite j'ai vraiment du mal avec ces 2 fonctions, pour être franc j'y comprends rien, mais je me doute qu'il y a du pointeur de fonction la dessous

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

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
 
/* lister */
   typedef int gs_traverse_f (void *user, void *p_data);
   int gs_traverse (gs_s * p_gs, gs_traverse_f * pf, void *user);
 
 
/* lister */
int gs_traverse (gs_s * p_gs, gs_traverse_f * pf, void *user)
{
   if (p_gs != NULL)
   {
      /* debut de la liste */
      struct gs_node *p = p_gs->p_head;
      int encore = 1;
      while (p != NULL && encore)
      {
         /* appeler la fonction de CB */
         if (pf != NULL)
         {
            encore = pf (user, p->p_data);
         }
 
         /* element suivant */
         p = p->p_next;
      }
   }
}

[matafan]

Si tu as besoin d'ajouter (ou supprimer) des éléments par les deux bouts, alors tu devrais utiliser une liste doublement chainée : chaque noeud pointe vers le noeud suivant, mais aussi vers le noeud précédent.

Ensuite tu peux soit garder tes deux références (vers le premier noeud, et vers le dernier noeud), soit n'en garder qu'une (premier noeud) et faire de ta liste un "anneau" : le dernier noeud a le premier noeud pour noeud suivant (et donc le premier noeud a le dernier noeud comme noeud précédent).

[Marmoccelle]

Si tu as besoin d'ajouter (ou supprimer) des éléments par les deux bouts, alors tu devrais utiliser une liste doublement chainée : chaque noeud pointe vers le noeud suivant, mais aussi vers le noeud précédent.

Oui en effet tu as raison, ça correspondrait plus au fonctionnement d'une liste doublement chainée. Donc dans mon cas je ne coderai pas cette fonction vu que je manipule que les listes simples.

Ensuite tu peux soit garder tes deux références (vers le premier noeud, et vers le dernier noeud), soit n'en garder qu'une (premier noeud) et faire de ta liste un "anneau" : le dernier noeud a le premier noeud pour noeud suivant (et donc le premier noeud a le dernier noeud comme noeud précédent).

J'ai justement attaqué l'étude des listes chainées car j'avais besoin d'un buffer circulaire

Merci pour tes commentaires

[Emmanuel Delahaye]

Est il vraiment intéressant d'ajouter un pointeur sur le dernier nœud de la liste? En effet il permet d'accélérer l'exécution de la fonction "AddTail" en particulier en cas de liste longue pour éviter de parcourir tous les nœuds avant de tomber sur le dernier.

Oui, c'est fait pour ça.

Mais si je dois implémenter la fonction "RemoveTail", ce pointeur ne me sera d'aucune utilité, puisque j'ai aussi besoin d'un pointeur sur l'avant dernier nœud, afin de mettre le champ "Next" à NULL et de faire pointer "Tail" sur l'avant dernier noeud, du coup je devrais tout de meme parcourir l'intégralité de la liste n'est ce pas?

Exact. Pour résoudre ce problème, il faut une liste doublement chainée (ce qui devrait être en final ta fameuse 'liste générique". une liste simple est insuffisante, la preuve).

Ensuite j'ai vraiment du mal avec ces 2 fonctions, pour être franc j'y comprends rien, mais je me doute qu'il y a du pointeur de fonction la dessous

Je m'en doutais un peu, bien qu'il y ait quelques commentaires...

déjà dans ce que tu montres, il n'y a qu'une fonction.

Effectivement, en réalité, il y a 2 fonctions. Où est la deuxième ?

Pour le comprendre, il faut se replacer dans le contexte. Ici, on cherche à faire de la programmation générique de liste chainée, c'est à dire que les seules informations que l'on traite sont des informations de chainage. On ne dispose qu'une d'une information minimale sur les données : l'adresse du début du bloc de donnée. on ne sait du contenu, ni de la taille du bloc. Ces informations sont de la responsabilité de l'utilisateur (de la bibliothèque).

Dans l'application, on cherche à lire tous les éléments de la liste chainée et à en afficher le contenu.

On écrit donc une fonction gs_traverse ('to traverse' signifie 'parcourir' en anglais), qui prend en paramètre la liste elle même (on a besoin de la tête de liste) et d'autres paramètre que je décrirais plut tard.

Cette fonction implémente une boucle qui va de nœud en nœud en partant de la tête et en s'arrétant au dernier, selon ce principe bien connu :

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
4
5
 
node p := list.head
WHILE p <> NIL
 p := p.next
WHILE END

Ceci parcours la liste mais ne fait rien de visible... On ne peut rien faire avec les données, car on ne sait pas comment elles sont organisées.

L'idée est alors d'appeler une fonction 'utilisateur' dans la boucle, avec pour paramètre, l'adresse du bloc de données courante :

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
4
5
6
 
node p := list.head
WHILE p <> NIL
 fonction_utilisateur(p.data)
 p := p.next
WHILE END

Évidemment, comme on ne connait pas le nom de la fonction utilisateur, on se contente de son adresse que l'on passe via un pointeur de fonction.

http://emmanuel-delahaye.developpez.....htm#pointeurs

J'a ajouté une fonctionnalité. Le parcours s'arrête si la fonction utilisateur retourne 0. Ca permet de s'arrêter si on fait une recherche par exemple...

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
4
5
6
7
 
node p := list.head
encore := TRUE
WHILE encore AND p <> NIL
 encore := fonction_utilisateur(p.data)
 p := p.next
WHILE END

Je commente un peu plus mon code :

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
 
/* lister */
/* ce typedef définit un alias (gs_traverse_f) qui définit le profile (prototype) de la fonction. Ca permet d'alléger considérablement le codage et de le rendre plus lisible. Le pointeur de fonction est tout simplement de ce type.
 
Ce prototype sert de modèle pour la fonction utilisateur qui doit donc ressembler à :
 
int fonction_utilisateur (void *user, void *p_data)
{
}
 
user est le contexte de l'utilisateur. 
p_data est l'adresse du bloc de données courant.
 
*/
   typedef int gs_traverse_f (void *user, void *p_data);
 
/* on passe l'adresse de la liste, l'adresse de la fonction utilisateur et l'adresse du contexte utilisateur */
   int gs_traverse (gs_s * p_gs, gs_traverse_f * pf, void *user);

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
 
/* lister */
int gs_traverse (gs_s * p_gs, gs_traverse_f * pf, void *user)
{
   if (p_gs != NULL)
   {
      /* debut de la liste */
      struct gs_node *p = p_gs->p_head;
      int encore = 1;
      while (p != NULL && encore)
      {
         /* appeler la fonction de CB */
         if (pf != NULL)
         {
            encore = pf (user, p->p_data);
         }
 
         /* element suivant */
         p = p->p_next;
      }
   }
}

Je ne vois rien à ajouter. Ensuite, consulter l'exemple d'utilisation dans main() ...

[Marmoccelle]

Super! tes explications sont très claires (l'algorithme ça illustre tellement bien les choses) bien que certaines notions sont encore un peu obscures pour moi, mais grâce aux divers interventions et liens de ce fil je devrais pouvoir m'en sortir.

Merci @ tous, en particulier @ -ed-