Free double linked List

[Sepp Meyer]

Hey alle miteinander,

ich habe eine doppelt verkettete liste mit folgendem Aufbau:

struct Info
{
	CHAR *Arr1;
	CHAR *Arr2;
};
struct Element
{
	Info *Data;

	Element *next;
	Element *previous;
};
struct List
{
	Element *Head;
	Element *Tail;
};

Die Liste hat immer ungefähr 30000 Einträge, sodass die Arbeitsspeicherauslastung immer sehr hoch ausfällt. Leider schaffe ich es nicht, den mit malloc() beanspruchten Platz wieder freizugeben.

Bereits versucht (und nicht geklappt):

Element *Pointer;
Pointer = Liste->Head;

while(Pointer != NULL)
{
	Element *Temp1 = Pointer;
	Pointer = Pointer->next;
	Info *Temp2 = Temp1->Data;
	CHAR *Temp3 = Temp1->Data->Path;
 	CHAR *Temp4 = Temp1->Data->Title;
        free(Temp1);
        Temp1 = NULL;
	free(Temp2);
	Temp2 = NULL;
	free(Temp3);
	Temp3 = NULL;
	free(Temp4);
	Temp4 = NULL;
}

Ich bin langsam am verzweifeln Ich würde mich sehr freuen wenn ihr mir weiter helfen könntet.

PS: Was vielleicht noch wichtig ist ist, dass sich das ganze in einer Klasse abspielt. Die Strukturen sind privat. Allerdings habe ich gerade festgestellt, dass delete der Klasse auch zu keiner Freigabe des Arbeitsspeichers führt

[SeppJ]

Was genau funktioniert nicht und wie stellst du das fest? Wie werden die Elemente überhaupt erzeugt?

Es fallen jedenfalls schon einige gravierende technische Fehler auf:
-Du benutzt free auf Pointer, deren Pointee später noch benutzt wird. Deine Freigabereihenfolge muss genau umgekehrt sein.
-Wenn du glaubst, deine =NULL; würden auch nur irgendetwas bewirken, liegst du falsch. Du änderst da ein paar lokale Variablen, die wenige Zeilen später verworfen werden.

Es fallen auch ein paar dicke Desingmängel auf, die teilweise direkt für die technischen Fehler verantwortlich sind:
-Du scheinst keinen Plan zu haben, was du mit dem =NULL; erreichen möchtest. Du musst genau wissen, wann und vor allem warum du einen Pointer auf NULL setzen möchtest. Planlos alles auf das free angewandt wurde auf NULL zu setzen ist falsch.
-Wenn dein struct Info selber Speicher verwaltet, dann soll es den auch selber verwalten. Die Freigabefunktion deiner Liste hat davon nichts zu wissen. Die Freigabefunktion soll bloß eine Art "Destruktor" (wenn du den begriff aus anderen Sprachen kennst) des Elementes aufrufen. Also eine für das Element geschriebene Funktion, die deren Speicher sauber freigibt.
Ähnliche Funktionen wirst du für das Kopieren, Erzeugen und Zuweisen von Elementen benötigen, wenn die Elemente ihren eigenen Speicher verwalten. Deine Liste hat es nichts anzugehen, wie ihre Elemente intern arbeiten.
( wenn ich von "Elementen" rede dann meine ich die Nutzdaten, also das was in deinem Programm struct Info ist. Dein struct Element entspricht in seiner Funktion eher einem Knoten )
-Apropos struct Element: Wieso nutzt dies dynamischen Speicher für das Datenelement? Das hat doch überhaupt keinen Vorteil, es macht bloß alles eine Indirektion komplexer und langsamer.

Vorschlag: Schreib erst einmal eine funktionierende Liste für ints. Diese zu verallgemeinern sollte wesentlich einfacher sein, als gleich mit der komplexen Problemstellung zu beginnen.

[Sepp Meyer]

Hallo SeppJ,
vielen Dank für deine Antwort. Ich habe deinen Rat befolgt und das ganze vorerst an einem vereinfachten Projekt versucht. Da habe ich dann gemerkt, dass bei mir ein grundsätzliches, logisches Problem vorliegt, da ich es auch dort nicht geschafft habe die Liste zu freen.

#include <stdio.h>
#include <Windows.h>

struct Element
{
	int Wert1;
	int Wert2;

	Element *next;
	Element *previous;
};
struct List
{
	Element *Head;
	Element *Tail;
};

void ListInsert(List *Liste, int Wert1, int Wert2)
{
	Element *Pointer;

	if(Liste->Head == NULL)
	{
		Liste->Head = (Element*)malloc(sizeof(Element));
		Liste->Tail = Liste->Head;
		Liste->Head->Wert1 = Wert1;
		Liste->Head->Wert2 = Wert2;
		Liste->Head->next = NULL;
		Liste->Head->previous = NULL;
	}
	else
	{
		Pointer = Liste->Tail;
		Pointer->next = (Element*)malloc(sizeof(Element));
		Pointer->next->Wert1 = Wert1;
		Pointer->next->Wert2 = Wert2;
		Pointer->next->next = NULL;
		Pointer->next->previous = Pointer;
		Liste->Tail = Pointer->next;
	}
}

void ListDelete(List *Liste)
{
	Element *Pointer = Liste->Head;

	while(Pointer)
	{
		Element *Temp = Pointer;
		Pointer = Pointer->next;
		if(Temp->next && Temp->previous)
		{
			Temp->next->previous = Temp->previous;
			Temp->previous->next = Temp->next;
			free(Temp);
		}

		if(!Temp->next && Temp->previous)
		{
			Temp->previous->next = Temp->next;
			free(Temp);
		}

		if(Temp->next && !Temp->previous)
		{
			Temp->next->previous = Temp->previous;
			free(Temp);
		}
	}
}

int main()
{
	List *Liste = (List*)malloc(sizeof(List));
	Liste->Head = NULL;
	Liste->Tail = NULL;

	printf("To malloc press Enter: ");
	fflush(stdin);
	getchar();

	for(int i = 0; i < 10000000; i++)
	{
		ListInsert(Liste, i, i + i);
	}

	printf("To free press Enter: ");
	fflush(stdin);
	getchar();

	ListDelete(Liste);

	fflush(stdin);
	getchar();
	return 0;
}

Könntest du mir sagen, wo genau mein Fehler liegt? Ich komme einfach nicht weiter.

[SeppJ]

Das kann in C nicht einmal compilieren. Benutzt du etwa einen C++-Compiler?

Auf den allerersten Blick fehlt ein #include<stdlib.h>, was du aber nicht merkst, da du vor allen deinen mallocs völlig sinnlose Casts hast, die diesen Fehler vertuschen und dann zur Laufzeit Probleme machen. Also erst einmal alle diese Casts weg. Dann würdest du auch merken, falls du einen C++-Compiler benutzt (denn in C++ ist das ohne Cast nicht erlaubt, aber da nutzt man auch kein malloc). Dann stdlib.h einbinden. Dann C-Compiler nutzen. Dann die ganzen dadurch entstehenden Fehler ausbessern (die ganzen Typennamen von structs funktionieren in C anders als in C++. Nochmal Grundlagen zu structs angucken).

Mehr kann ich dir erst sagen, nachdem ich selber diese Fehler beseitigt habe, um dein Programm mal durch den Debugger jagen zu können. Das könntest du übrigens auch mal tun. Debugger sind das wichtigste Werkzeug des Programmierers. Gerade in einem Fall wie diesem sind sie sehr nützlich.

P.S.: Wenn du den unter Windows verbreiteten Compiler von Microsoft benutzt, dann kann der übrigens kein C99. Sprich deine for-Schleifen wären ungültig. Ein weiterer Hinweis, dass du fälschlicherweise einen C++-Compiler benutzt hast.

P.P.S.: Überleg mal, ob du auch wirklich alle Fälle berücksichtigt hast. Was passiert denn, wenn deine Liste nur noch ein Element hat?

P.P.P.S: Überleg mal, ob du die ganzen Unterscheidungen wirklich brauchst. Vielleicht gibt es da ja eine elegantere Lösung...

[Sepp Meyer]

Ich arbeite mit Visual Studio 2010 von Microsoft und das Compilieren klappt soweit. Allerdings verlässt mein Programm nie die while Schleife ( while(Pointer){...} ) was mich schon stutzig macht. Hättest du vielleicht einen ganz simplen beispielcode der bei dir klappt?

[SeppJ]

Sepp Meyer schrieb:

Ich arbeite mit Visual Studio 2010 von Microsoft und das Compilieren klappt soweit.

Dann übersetzt du im C++-Modus. Tu das nicht.

Allerdings verlässt mein Programm nie die while Schleife ( while(Pointer){...} ) was mich schon stutzig macht.

Sollte es eigentlich nicht.

Hättest du vielleicht einen ganz simplen beispielcode der bei dir klappt?

Wenn man den Code soweit berichtigt, dass er compiliert, dann sollte er wenigstens durchlaufen. Und natürlich ein paar dicke Speicherlöcher hinterlassen, da es, wie in meinem PPS gesagt, falsch ist. Aber nicht Endlosschleifenfalsch. Wartest du vielleicht einfach nicht lange genug? 10000000 ist ganz schön viel, besonders wenn man es in einer IDE mit fettem Debugmodus laufen lässt. Als ich den Code bei mir getestet habe (mit valgrind (auch eine Art fetter Debugger) unter Linux) habe ich die Anzahl der Elemente erst einmal auf 10 gesetzt.

[Sepp Meyer]

So, ich hab es jetzt mit deinen Tipps geschafft den Arbeitsspeicher freizugeben. Nachdem ich das ganze gerüst extrem vereinfacht habe ist mir aufgefallen, dass er den Arbeitsspeicher nun freigibt, das aber extrem langsam geschieht.

struct Element
{
	CHAR Path[MAX_PATH];
	CHAR Title[MAX_PATH];

	Element *next;
	Element *previous;
};
struct List
{
	Element *Head;
	Element *Tail;
};

Die verkettete Liste hat in etwa 300000 Einträge, wobei jedes Element nun nach meiner Rechnung ca. 528 Bytes wegnehmen müsste.

Gefreed wird jetzt mit folgender Funktion.

ListReset()
{
Element *Pointer, *Temp;

Pointer = Liste->Head;

while(Pointer)
{
	Temp = Pointer;
	Pointer = Pointer->next;
	free(Temp);
}
}

Dabei gab es nun 1 Phänomen (zumindest für mich) zu beobachten.

1. Bei 300000 Elementen (wie oben beschrieben) nimmt die Kette bei einer Elementgröße von etwa 528 Bytes: 528 * 300000 = 158400000 Bytes = 154687 Kilobytes = 151 Megabytes ein. Wenn ich nun den Spieß umdrehe und sage, ich erzeuge nicht eine Liste mit 300000 Elementen wobei jedes Element die Größe von 528 Bytes hat, sondern ich erzeuge eine liste mit 528 Elementen bei denen jedes Element die Größe von 300000 Bytes hat dann geht das freen durchaus schneller.

Auswertung: Viele Elemente mit wenig Speicher (18689 MS zum freen)
Auswertung: Wenige Elemente mit viel Speicher (110 MS zum freen)

In meinem Fall (im Sachzusammenhang führe ich eine Pfadanalyse durch) kann ich mir aber schlecht vorstellen es andersherum zu programmieren, bin aber für alles offen

Nachdem ich bemerkt habe, dass erfolgreich freigegeben wird und ich mal genau nachgerechnet habe ist mir aufgefallen, dass durch die VKL nur etwa 150 MB draufgehen dürften. Bei mir werden jedoch ca. 550 MB Arbeitsspeicher durch folgende Funktion aufgefressen:

PathAnalyse(CHAR *Path)
{
	WIN32_FIND_DATA FD = {0};
	HANDLE hFind = FindFirstFile(Path, &FD);
	UINT Size = strlen(Path);

	do
	{
		if(FD.dwFileAttributes & FILE_ATTRIBUTE_DIRECTORY)
		{
			CHAR Pfad[MAX_PATH] = {0};

			strcpy(Pfad, Path);
			Pfad[Size - 1] = 0;
			strcat(Pfad, FD.cFileName);
			strcat(Pfad, "\\*");

			PathAnalyse(Pfad);
		}
		else
		{
			Element *Data = (Element*)malloc(sizeof(Element));

			strcpy(Data->Path, Path);
			Data->Path[Size - 1] = 0;
			strcat(Data->Path, FD.cFileName);
			strcpy(Data->Title, FD.cFileName);

			// ListInsert(Data);
			free(Data);
		}
	}while(FindNextFile(hFind, &FD));
}

Die Funktion wird aufgerufen und sie beendet sich auch wieder. Daher bin ich fest davon ausgegangen, dass alle Variablen, die innerhalb der Funktion (nicht dynamisch) erzeugt wurden, am Ende wieder anderen Programmen als Arbeitsspeicher zur Verfügung stehen. Das ist jedoch nicht der Fall, da mir die 550 MB abhanden bleiben. Könntet ihr mir an dieser Stelle bitte auch noch einmal weiterhelfne?

[SeppJ]

Zur ersten Frage:
Ja, malloc und free sind extrem langsam. Außerdem solltest du natürlich eine Releaseversion ansehen, wenn du sehen möchtest, wie schnell das Programm wirklich wäre.

Moment! Das ist keine Übungsaufgabe? Dann hör auf deine Zeit zu verplempern. Verkettete Listen sind praktisch unbrauchbar, weil sie viel zu langsam sind. Was willst du erreichen? Wieso nutzt du keine fertigen Bibliotheken?

Zur zweiten Frage: Da ist mir zu viel Winapi drin, außerdem verstehe ich deine Frage nicht.