Discussion :

[econym]

Bonjour,

J'ai rencontré un problème d'allocation mémoire lors de l'implémentation de la liste simplement chaînée.
J'ai résolu le problème en utilisant l'allocation dynamique (avec malloc) au lieu de l'allocation statique (lors de la déclaration des variables).

Voici la définition des types et une partie des opérations disponibles dessus :

Code :

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

1
2
3
4
5
6
7
8
typedef struct { int valeur; } Element;
typedef struct noeud {
	Element element;
	struct noeud * suivant;	
} Noeud;
typedef Noeud * Liste;
int longueur(const Liste * l); // renvoie la longueur de la liste l
void ajouterAuDebut(Liste * l, const Element e); // ajouter l'élément e au début de la liste l

Version non fonctionnelle : allocation statique, appeler longueur(&l) engendre un seg fault

Code :

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

1
2
3
4
5
6
7
void ajouterAuDebut(Liste * l, const Element e) {
	Noeud n;
 
	n.element = e;
	n.suivant = *l;
	*l = &n;
}

Version fonctionnelle : allocation dynamique

Code :

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

1
2
3
4
5
6
7
void ajouterAuDebut(Liste * l, const Element e) {
	Liste p = malloc(sizeof(Noeud));
 
	p->element = e;
	p->suivant = *l;
	*l = p;
}

La fonction longueur est correcte (son corps n'est pas très intéressant mais je peux le fournir).

Ma question : pourquoi cela ne fonctionne pas avec la version en allocation statique ? Après tout, la variable est bien allouée puis référencée par la liste.

Merci d'avance.

[Invité]

C'est très simple.

Une variable créé statiquement à une portée bien définie : la fonction dans laquelle elle a été créé. Quand tu sors d'une fonction, toutes les variables créés localement sont détruite.
De ce fait, quand tu quittes ta fonction, ton Noeud "n" est détruit, ce qui fait que tu te retrouves avec une adresse pointant vers... "rien", d'où le plantage.

Quand on déclare une variable dynamique, concrètement, on va réserver en mémoire un espace référencé par le pointeur renvoyé par malloc. Cet espace mémoire reste "actif" tant que l'on n'a pas explicitement indiqué que l'on ne souhaitais plus utilisé cet espace mémoire ( avec un free() ). Du coup, quand tu alloues dynamiquement une variable, elle n'est pas détruites en sortant de ta fonction, et donc tu ne rencontres plus de problème.

[Ilphrin]

Bnjour champidead,

Pour compléter la réponse de archMqx lorsque tu sors de ta fonction, *l pointe toujours vers une adresse, mais cette adresse ne contient plus ta variable crée dans ta fonction, mais quelque chose d'autre qui ne t'appartient plus. De ce fait lorsque ton code essaie d'y accéder il va renvoyer un signal pour indiquer que tu essaie d'accéder à une case mémoire qui ne t'appartient pas.
C'est pour cela qu'on fait toujours une liste chainée en allouant par le biais de malloc() chaque élément de la liste

[econym]

Re,

Merci à vous deux On peut dire que c'est lié à la portée de la variable alors.
Par curiosité, est-ce que cela signifie que ça peut fonctionner avec une variable globale Noeud (même si c'est moche) ?

C'est toutefois étonnant que ceci, avec la version en allocation statique, semble donner des valeurs cohérentes :

Code :

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

1
2
3
4
5
6
7
8
9
10
11
12
13
14
int main() {
	Liste l;
	Element e1 = {10};	
	Element e2 = {20};
 
	ajouterAuDebut(&l, e1);
	printf("l->element = %d, l->suivant = %p\n", l->element.valeur, l->suivant);
	printf("@l = %p\n", l);
 
	ajouterAuDebut(&l, e2);
	printf("l->element = %d, l->suivant = %p\n", l->element.valeur, l->suivant);
 
	printf("longueur(&l) = %d\n", longueur(&l));
}

Code :

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

1
2
3
4
l->element = 10, l->suivant = (nil)
@l = 0x7ffd1279fd40
l->element = 20, l->suivant = 0x7ffd1279fd40
Segmentation fault (core dumped)

L'appel de longueur(&l) (ou tout autre fonction effectuant un parcours de la liste) produit le seg fault.

[radium]

Bonjour,

Un petit complément :
Allocation statique = utilisation de la pile mémoire (stack) qui est dépilée/effacée en sortie de fonction.
Allocation dynamique (via malloc) = utilisation du tas mémoire (heap - https://fr.wikipedia.org/wiki/Tas_%2...n_dynamique%29), il faut également libérer la mémoire via un free.

[Vincent PETIT]

Salut,

Un petit complément :
Allocation statique = utilisation de la pile mémoire (stack) qui est dépilée/effacée en sortie de fonction.

Hum... oui et non, je dirai plutôt :
Allocation statique d'une variable globale = le tas (heap)
Allocation statique d'une variable locale = la pile (stack)

[Sve@r]

Bonjour

Par curiosité, est-ce que cela signifie que ça peut fonctionner avec une variable globale Noeud (même si c'est moche) ?

Absolument pas pour la simple raison qu'une variable globale est unique alors qu'une liste chainée implique plusieurs noeuds distincts...

C'est toutefois étonnant que ceci, avec la version en allocation statique, semble donner des valeurs cohérentes :

C'est le problème des comportements indéterminés: quand tu effectues une action interdite tu génères un comportement indéterminé dans la plus pure définition de ce mot => totalement imprévisible. Tu ne peux donc pas prévoir comment se comportera ton programme. Ca peut aller du crash immédiat (ce qui est une chance car au-moins tu sais qu'il y a un soucis que tu peux allors corriger) jusqu'à un résultat qui "semble" correct. Ce dernier état est alors absolument catastrophique car tu n'as alors aucun moyen de te rendre compte que tu as fait une connerie qui peut alors rester en place durant des semaines. Pire, tu rajoutes 3 mois plus tard un simple printf() et là ton programme crashe et tu galèreras à chercher en quoi un simple printf() fait crasher alors que la raison profonde du crash vient d'ailleurs...

[BufferBob]

Hum... oui et non, je dirai plutôt :
Allocation statique d'une variable globale = le tas (heap)
Allocation statique d'une variable locale = la pile (stack)

hmm non pas que je sache, tout ce qui est global va dans .data si c'est initialisé ou .bss quand ça ne l'est pas si je me souviens bien, donc c'est mappé en même temps que le reste du binaire en mémoire dans ces sections respectives, ça va pas dans le heap, les allocations dynamiques via malloc oui par contre, ça va bien dans le heap

[econym]

Absolument pas pour la simple raison qu'une variable globale est unique alors qu'une liste chainée implique plusieurs noeuds distincts...

Ah oui, c'est évident maintenant que tu le dis...

C'est le problème des comportements indéterminés

C'est ce que je m'étais dit mais sans conviction...merci d'avoir confirmé.

Sujet résolu, merci aux intervenants

[Vincent PETIT]

hmm non pas que je sache, tout ce qui est global va dans .data si c'est initialisé ou .bss quand ça ne l'est pas si je me souviens bien, donc c'est mappé en même temps que le reste du binaire en mémoire dans ces sections respectives, ça va pas dans le heap, les allocations dynamiques via malloc oui par contre, ça va bien dans le heap

Autant pour moi, tu as raison, j'avais oublié que le segment données était divisé en 3 (data, bss et tas). Desolé !