C Doppelt Verkettete Liste

[Sponny]

Hallo Leute,

ich habe soeben ein Programm geschrieben, das eine doppelt verkettete Liste implementiert.

Meine Frage bezieht sich auf die Funktion free_list. Habe ich hier die Deallokierung des Speichers im Heap mit der free() Funktion aus der stdlib.h korrekt angewendet?

Vielen Dank im Voraus.

/*
* main.c
*
* Created on: 20.01.2015
* Author: Sponny
*/
#include <stdio.h>
#include <stdlib.h>

typedef struct dl_list_t{
struct dl_list_t *prev;
int value;
struct dl_list_t *next;
}dl_list_t;

int sumlist(dl_list_t *a){
int sum = 0;
dl_list_t *h;
h = a;
while(h->next != NULL){
sum = sum + h->value;
h = h->next;
}
sum = sum + h->value;
return sum;
}

void free_list(dl_list_t *a){
dl_list_t *h;
h = a;
while(h->next != NULL){
free(h);
h = h->next;
}
free(h);
}

int main (){

dl_list_t *l1;
dl_list_t *l2;
dl_list_t *l3;

l1 = calloc (1, sizeof(dl_list_t));
l2 = calloc (1, sizeof(dl_list_t));
l3 = calloc (1, sizeof(dl_list_t));

l1->prev = NULL;
l1->value = 12;
l1->next = l2;

l2->prev = l1;
l2->value = 4;
l2->next = l3;

l3->prev = l2;
l3->value = 2014;
l3->next = NULL;

dl_list_t *anfang = l1;
printf("%d", sumlist(anfang));
free_list(anfang);
return 0;
}

 

[togepi]

free(h);
h = h->next;

Über diese zwei Zeilen solltest du noch einmal nachdenken.

Außerdem bitte Code-Tags nutzen, ist schwer lesbar.

 

[HominiLupus]

Nein hast du nicht, Stichwort "Use after free()".

Es ist auch schlicht sehr schlechtes Design eine fixe Anzahl von mallocs in main() zu machen und dann die free() Aufrufe dynamisch in einer Funktion. Das ist sehr unübersichtlich und lädt zu Fehlern gerade zu ein.

 

[dcc22]

Bau dir doch zwei Funktionen, eine hängt links etwas dran, eine rechts.
Dann kannst gemütlich mit einer Schleife beliebig viele structs verketten.
Eine eigenständige Operation gehört in eine eigenständige Funktion.

Beim free machst es ja fast richtig, nur was soll a=h ?
Benutz doch direkt was übergeben wird ?

Und wie schon gesagt wurde, machst ein free(h), dann greifst du wieder auf h->next zu.
Das ist falsch da es dieses h nicht mehr gibt.

Ob du das mit free und malloc korrekt gemacht hast, lässt sich mit valgrind überprüfen, das zeigt dir dann an wenn du mehr mallocs als frees hast. Gibt es für die shell und auch für Eclipse mit CDT + Valgrind Plugin in grafischer Version.

 

[Sponny]

#include <stdio.h>
#include <stdlib.h>

typedef struct list{
	struct list*pre;
	int value;
	struct list*next;
}list;

int sum(list *l) {
	int sum = 0;
	while(l != NULL) {
		sum += l->value;
		l = l->next;
	}
	return sum;
}

list*  createlist(int x, list* mylist){
	list *neu;
	if((neu = malloc(sizeof(list))) != NULL){
		neu->value = x;
		neu->next = NULL;
		neu->pre = NULL;
		mylist = neu;
		return mylist;
	}
	else {
		printf("Fehler");
	}
	return NULL;
}

list* vorne(int x, list* l){
	list *new;
	if((new = malloc(sizeof(list))) != NULL) {
		new->value = x;
		new->pre = NULL;
		new->next = l;
		l = new;
		return l;
	}
	else {
		printf("Fehler");
	}
	return NULL;
}

list* hinten(int x, list* l){
	list *new;
	list *h = l;
	if((new = malloc(sizeof(list))) != NULL) {
		while(h->next != NULL){
			h = h->next;
		}
		h->next = new;
		new->value = x;
		new->next = NULL;
		new->pre = h;
		return l;
	}
	else {
		printf("Fehler");
	}
	return NULL;
}

void freelist(list* l){
	list* next;
	while (l->next != NULL) {
	      next = l->next;
	      printf("%d\n", l->value);
	      free(l);
	      printf("%d\n", l->value);
	      l = next;
	}
	printf("%d\n", l->value);
	free(l);
	printf("%d\n", l->value);
}

int main(){

	list* mylist = NULL;
	mylist = createlist(2015, mylist);
	mylist = vorne(1, mylist);
	mylist = vorne(29, mylist);
	mylist = hinten(22, mylist);
	printf("%d\n", sum(mylist));
	freelist(mylist);
	return 0;
}

Nochmal zu der "freelist" Funktion. Ich habe mit printf'ss versucht diese Funktion dezubuggen.
Jetzt klappt es nahezu fast. Bis auf das letzte Element in der Liste wird alles freigegeben.
Ich habe so das Gefühl, dass dies an meiner "hinten" Funktion liegt.

Kann mir jemand weiterhelfen. Ich finden den Fehler leider nicht. :'/
Vielen Dank im Voraus.

 

[Harzerkas]

Du prüfst erst ob das Element einen Nachfolger hat und gibst danach erst frei.
Edit: Dein printf nach free() ist wieder use-after-free

 

[Sponny]

void freelist(list* l){
	list* next;
	while (l != NULL) {
	      next = l->next;
	      free(l);
	      l = next;
	}
}

Wird so das Element am Ende auch korrekt freigegeben?

 

[VikingGe]

Klar. Die Schleife endet ja erst, wenn der l-Pointer null ist, also wirklich kein Element mehr existiert.

Sowas kann man am besten auch an Trivialbeispielen durchgehen. Was passiert bei einer leeren Liste? Offensichtlich gar nichts. Was passiert bei einer einelementigen Liste? Die Schleife wird einmal durchlaufen. Und so weiter.

 

[Harzerkas]

Ja das ist richtig!

 

[Sponny]

Cool, vielen Dank! (-

Eine kleine Frage habe ich noch dazu.
Wie kann es sein, wenn ich es mit Printf's wie folgt teste

void freelist(list* l){
	list* next;
	while (l != NULL) {
	      next = l->next;
	      printf("%d\n", l->value);
	      free(l);
	      printf("%d\n", l->value);
	      l = next;
	}
}

,dass ich dann folgende Werte bekomme:

29
5246352
1
5246352
2015
5246352
22
22

Das sieht für mich so aus, als würde das letzte Element nicht korrekt freigegeben werden?
Aber wie vorhin schon erwähnt, ist die printf ja eine use after free...

 

[VikingGe]

Aber wie vorhin schon erwähnt, ist die printf ja eine use after free...

Damit beantwortest du deine Frage doch selbst. Nach einem free auf die Region ist der Inhalt dieser Region aus deiner Sicht undefiniert und darf eben nicht mehr benutzt werden, weil da sonstwas drin stehen kann.

 

[Sponny]

Alles klar. Vielen Dank nochmal.
War nur etwas verunsichert, wegen der Ausgabe. :O

 

[black90]

Free löscht es nur aus Verwaltungstabellen, aber nicht im Speicher.
Was im Speicher steht bleibt auch dort, bis es nicht von irgendetwas überschrieben wird.

Das ist das tückische an C, es sagt dir nicht viel, scheint zu gehen und stürzt dann ab wenn es nicht soll

 

[antred]

Free löscht es nur aus Verwaltungstabellen, aber nicht im Speicher.
Was im Speicher steht bleibt auch dort, bis es nicht von irgendetwas überschrieben wird.

Das ist vollkommen implementierungsabhängig. Soweit es den C-Standard betrifft, kann sich durch ein free sehr wohl auch der Inhalt des freigegebenen Speichers ändern (auch wenn das in der Praxis wahrscheinlich kaum vorkommt). Das einzige, was zählt, ist dass Zugriff nach free immer undefined behavior nach sich zieht, sprich, es könnte funktionieren, es könnte manchmal funktionieren und manchmal nicht, oder es könnte auch deine lokale Pornosammlung zippen und an die Email-Adresse deiner Oma versenden.

 

[Sponny]

Stimmt. Das habe ich doch schon wo gehört.

 

[antred]

Stimmt. Das habe ich doch schon wo gehört.

Dein Teil mit dem Porno verschicken, habe ich mal irgendwo auf stackoverflow gelesen. Ein klitze-kleines bißchen Plagiarismus hat noch keinem was geschadet.