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.