liste chainée et pointeur générique ?

Bonjour,

J'essaie de coder une liste chainée dont la valeur à stockée est matérialisé par un
pointeur sur void de façon rendre mon code générique:

typedef void* PVOID; //définit un pointeur générique

typedef struct{

    PVOID data; //pointeur générique
    struct ELEMENT *next;//pointe sur l'élément suivant
    struct ELEMENT *prev;//pointe sur l'élément précédent
} ELEMENT;

typedef ELEMENT*  PELEMENT; //définit un pointeur sur une structure ELEMENT

typedef struct{

   PELEMENT head; //pointe sur le 1er élément
   PELEMENT tail;   //pointe sur le dernier élément
   PELEMENT curr; //pointe sur l'élément courant
   UINT nbElem;  //nombre d'éléments dans la liste
} LIST;

//Fonctions relatives à la gestion de la liste add, remove etc......
//  code.............

Supposons que je veuille créer une liste chainée qui manipulerait des int.
Imaginons que la fonction addElem(PVOID data) ajoute un nouvel élément à la liste
et y stocke la valeur 'data' (donc un int dans mon cas).
Comment faire pour passer ma valeur à placer dans la liste ?

Y a bien ça:

int a = 25;
addElem(&25);

mais ça n'a aucun interêt puisqu'il faut créer une variable int pour chaque élément
de la liste.

Ce que j'aimerais faire c'est une utilisation simple du genre:
addElem(25);
mais bien sûr ça ne peut pas marcher.

Aussi, j'aimerais savoir quel est la méthode pour utiliser des liste chainée génériques.
(j'ai regardé comment était conçues les listes dans GTK+ mais j'ai pas tout compris)

Merci d'avance

Tintin 72

Bas en C++, on pourrait faire une fonction template
template <class U>
void addElement(const U & object)

Mais en C, je pense pas que tu es une solution relativement propre. Tu peux toujours créer une fonction pour chaque type.
addElement(int);
addElement(float);
...

Oui j'y avais pensé, mais ça fait vraiment beaucoup de code.
Je sais qu'il y a une solution (complexe!) avec des macros, mais j'ai pas encore tout compris.

Ce que je pige pas avec l'histoire du pointeur générique c'est que, ok, il pointe sur n'importe quel type (char, int etc....)  mais comment il stocke cette valeur ?
Il fais une allocation dynamique ? (comment il fait pour le sizeof() selon si c'est un int un char ou une structure qui est passé en paramètre ?)

Tintin 72

Ton type generique est tres bien.  Cependant il ne faut pas faire &25 mais &a.
Comme tu as choisi (et tu as raison) d'implementer les listes generiquement, il faut faire une allocation memoire pour ton int :
int *data;
data = malloc(sizeof(int));
*data = 25;
addElement(data);

puis pour la liberation :
free(delElement(list));

L'inconvenient ici c'est que tu alloue un int pour rien, comme un int (32 bits) tient en memoire dans un pointeur (32 bits aussi) il tu suffit de faire :

addElement((void*)25);
en fait tu enregistres le pointeur qui pointe a l'adresse 25 de la memoire.

Pourquoi faire simple quand on peut faire compliqué ?

Merci beaucoup pour ta réponse

Je ne savais pas qu'on pouvait passer une valeur littérale à un pointeur générique.
Par contre comment ferais tu pour récupérer cette valeur ?

Tintin 72

En fait tu utilise la memoire que tu a alloué pour le champs data de la structure ELEMENT, donc tu te donnes la convention que le pointeur qui pointe a l'adresse 25 est en fait le nombre 25, je dis bien que c'est une convention, i.e. que pour apres recupere la valeur il faut suivre cette convention, donc si tu a l'element <elem>, tu peux avoir la valeur du "PVOID data" correspondant a l'element <elem> par <elem->data>, ensuite si tu veux le nombre, il te suffit donc de faire <nombre=(int)(elem->data)>

 

 

Pourquoi faire simple quand on peut faire compliqué ?

C'est franchement pas une bonne solution.
Si la structure possède un attribut de type void* c'est au code de la liste de se charger de l'allocation lors de l'insertion d'une cellule et de la désallocation lors de la suppression de cellule. Il faut dans ce cas ajouter un attribut qui stocke la taille d'un élément.
Sinon il y a aussi la solution avec une macro pour faire générer le code parametrable selon le type, mais c'est pas super au niveau de la maintenance.

alors ca c'est absolument pas vrai du tout, car la plupart du temps <data> pointe sur une structure (par exemple TOTO), donc l'allocation de TOTO est faite a l'exterieur, et on peut utiliser 10 fois la liste, sans a avoir a chaque fois besoin de reallouer TOTO. D'ailleurs c'est pas deleteElem, mais plutot removeElem, on enleve seulement l'element, et surtout on ne le supprime pas a coup de free(data). (en revanche il faut faire free(elem)).
Le gestionnaire des listes n'a pas a s'occuper de ce qu'est en realite <data>, en plus <data> peut pointer sur un tableau de la pile, ou quelque chose d'autre , et alors il ne faudra surtout pas faire free(data)


Pourquoi faire simple quand on peut faire compliqué ?

Tu n'as pas compris, c'est infiniment plus simple à l'utilisation si le conteneur "semble" stocker des valeurs plutot que des "references", sinons il faut tenir compte de la durée de vie de chaque objet contenue et ca devient trés vite ingérable.
Pour chaque insertion on alloue et on copie, indépendamment du type d'allocation de l'objet.

Eh ben il y en a qui aime bien se prendre la tete ....

Comme steve l'a fait remarquer, c'est au gestionnaire de liste de gérer les allocations. Je suis d'avis pour utiliser un deuxième paramètre indiquant la taille de la variable utilisé.
Allouer en dohors du gestionnaire, puis passé ensuite le pointeur sur cette allocation ne peut etre que source d'erreur et de bug!
Mieux vaut privilégier un code simple et sure, qu'un code qui risque d'etre ingérable par la suite.

Shell