[C]: Struct in einer 'Unter'funktion mit realloc() vergrößern klappt nicht

[mf_2]

Hallo,

hier mal ein wenig Code für die anschließende Problembeschreibung:


typedef struct
{
int uid;
char login[51];
} NUTZER;

int bla(NUTZER nutzerdb[])
{

nutzerdb = (NUTZER*) realloc(nutzerdb,2*sizeof(NUTZER));
// hier stand zeile y
return 1;

}

void main()
{

NUTZER *nutzerdb;
int erg;

nutzerdb = (NUTZER*) calloc(1,sizeof(NUTZER));
// Zeile x stand hier
erg=bla(nutzerdb);
//zeile z stand hier
}


Folgender Ablauf:
'nutzerdb' wird angelegt mit Platz für eine Struktur NUTZER.
In Zeile x wird diese Struktur (nutzerdb[0] sozusagen) mit Werten belegt und alles ausgegeben. Das passt auch wunderbar.
bla() wird aufgerufen.
Darin wird 'nutzerdb' vergrößert und kann nun noch ein zweites Element der Struktur NUTZER aufnehmen.
In Zeile ywird nun das zweite Element (nutzerdb[1]) mit Daten befüllt und ausgegeben. Das klappt auch noch!
ABER:
Wenn es nun in der main() weitergeht und dann wieder nutzerdb[1] ausgegeben werden soll (Zeile z), klappt es plötzlich nicht mehr.
Woran liegt das?
Die Ausgabe in Zeile z zeigt nur zufälligen Müll an, was für mich darauf schließen lässt, dass es nutzerdb[1] da schon nicht mehr gibt.

Ist so eine Verwendung von realloc() überhaupt korrekt? Ich denke schon.
Das Problem habe ich nun schon seit einer Woche und weder ich, noch mein Programmierdozent haben da eine Lösung finden können.
Vllt. sehen wir aber auch den Wald vor lauter Bäumen nicht.

Wisst ihr weiter?

Gruß,
mf_2

P.S.: Ich habe versucht, den Code auf das Wesentliche zu beschränken, aber wenn ihr mehr Infos braucht, dann gebt einfach Bescheid.

[Berni]

Das Problem liegt glaub ich hier weniger am realloc sondern daran, wie du nutzerdb übergibst. Du müsstest die Speicheradresse übergeben ("&") und dementsprechend die bla-Funktion anpassen mit entsprechenden "*"-chen. Alternativ dazu könntest du auch das neue nutzerdb als return-value übergeben. Ich bin mir aber jetzt gerade nicht sicher, ob dann nicht möglicherweise ein Speicherleck entstehen könnte (ich glaube aber eher nicht).

[mf_2]

Vielen Dank für die schnelle Antwort.
Ich habe den Code wie folgt überarbeitet:



typedef struct
{
int uid;
char login[51];
} NUTZER;

int bla(NUTZER *nutzerdb[])
{

*nutzerdb = (NUTZER*) realloc(nutzerdb,2*sizeof(NUTZER));
// hier stand zeile y
return 1;

}

void main()
{

NUTZER *nutzerdb;
int erg;

nutzerdb = (NUTZER*) calloc(1,sizeof(NUTZER));
// Zeile x stand hier
erg=bla(&nutzerdb);
//zeile z stand hier
}



Das kompiliert zwar, schmiert bei der Ausführung von bla() aber ab.
Leider kenne ich mich mit Zeigern noch nicht so wahnsinnig gut aus.
Was mache ich falsch?

[Gnafoo]

Der fehlende "*" ist es nicht, denn jedes Array ist in C schon implizit ein Pointer. "NUTZER test[]" ist in diesem Fall das selbe wie "NUTZER* test".

Das Problem ist denke ich eher, dass du in bla zwar das Argument nutzerdb mit dem Rückgabewert von realloc überschreibst, der neue Pointer aber nicht in der Variable nutzerdb in main landet. Da realloc die Freiheit hat, den Speicherbereich (und damit den Pointer) zu ändern, greifst du in der main mit dem Pointer noch auf den alten Speicherbereich zu, während du in bla auf den neuen Speicherbereich schreibst.


The function may move the memory block to a new location, in which case the new location is returned. The content of the memory block is preserved up to the lesser of the new and old sizes, even if the block is moved. If the new size is larger, the value of the newly allocated portion is indeterminate.

(http://www.cplusplus.com/reference/clibrary/cstdlib/realloc.html)

Edit: vielleicht habe ich Berni falsch verstanden. Du kannst natürlich auch einen Pointer auf den Pointer übergeben und direkt die Variable in der main überschreiben, wie du es in deinem Beispiel gemacht hast. Finde ich allerdings etwas unschön ;). Außerdem weiß ich gerade nicht, warum es bei dir nicht geht. Benutzt du in "Zeile y" dann auch überall *nutzerdb statt nutzerdb?

Edit2: ja nach erneutem Durchlesen stelle ich fest: ich hab ihn falsch verstanden :D. Ich sollte genauer lesen.

[mf_2]

Der fehlende "*" ist es nicht, denn jedes Array ist in C schon implizit ein Pointer. "NUTZER test[]" ist in diesem Fall das selbe wie "NUTZER* test".

Das Problem ist denke ich eher, dass du in bla zwar das Argument nutzerdb mit dem Rückgabewert von realloc überschreibst, der neue Pointer aber nicht in der Variable nutzerdb in main landet. Da realloc die Freiheit hat, den Speicherbereich (und damit den Pointer) zu ändern, greifst du in der main mit dem Pointer noch auf den alten Speicherbereich zu, während du in bla auf den neuen Speicherbereich schreibst.


(http://www.cplusplus.com/reference/clibrary/cstdlib/realloc.html)

Kann ich die neue Adresse irgendwie an main() übergeben? 'return' scheidet leider aus, weil ich bereits eine andere Zahl zurückgeben muß.

[Berni]

Müsste es nicht eigtl. so heißen:
int bla(NUTZER **nutzerdb)
{

*nutzerdb = (NUTZER*) realloc(*nutzerdb,2*sizeof(NUTZER));
// hier stand zeile y
return 1;

}

[Funky Bob]

Kann ich die neue Adresse irgendwie an main() übergeben? 'return' scheidet leider aus, weil ich bereits eine andere Zahl zurückgeben muß.


Du könntest beim Aufruf der Funktion nen Charpointer übergeben, in den du dann die Adresse reinschreibst, da du den Pointer übergibst, schreibst du ja in die Adresse des Chars.

Damit steht dann nach dem Aufruf die Adresse in dem Char drinne.

Alternativ würde ich ne verkettete Liste vorschlagen, musste ich vor einigen Wochen im C-Praktikum proggen, kann dir den Code später zukommen lassen, falls du da mal drüberschauen möchtest.

[Gast]

Ich würde das auch eher mit einer verketteten Liste machen. Wenn ich mich recht entsinne muss realloc() immer einen zusammenhängenden Speicherbereich zurückgeben - wenn du das jedesmal aufrufst wenn du einen Benutzer hinzufügst dann gute Nacht. So oft wie da Speicher herumverschoben wird.... Außerdem dürftest du bei ein bisschen mehr Benutzern recht schnell an die Grenze des Speichers kommen.
Mit einer Liste bist du diese Probleme alle los.

[mf_2]

Ich habe mir das Konzept der verketteten Listen mal angesehen.
Nun habe ich der NUTZER Struktur noch ein next Element hinzugefügt.

Ich erstelle nun ein neues Element der verketteten Liste (via calloc() in bla()) und habe nun wieder das Problem: Wie verhindere ich, dass mir dieses Element wieder abhanden kommt sobald ich bla() verlasse?

[Gnafoo]

Indem du next benutzt um den Pointer zu halten. Pseudocode. Keine Garantie für Fehlerfreiheit :D.


typedef struct
{
int uid;
char login[51];
NUTZER* next;
} NUTZER;

void nutzerEinfuegen(NUTZER* vorgaenger, NUTZER* neuerNutzer)
{
neuerNutzer->next = vorgaenger->next;
vorgaenger->next = neuerNutzer;
}

void listeLoeschen(NUTZER* nutzer)
{
NUTZER* tmp;
while (nutzer != NULL)
{
tmp = nutzer;
nutzer = nutzer->next;
free(tmp);
}
}

int bla(NUTZER* ersterNutzer)
{
NUTZER* neuerNutzer = (NUTZER*)calloc(1, sizeof(NUTZER));
nutzerEinfuegen(ersterNutzer, neuerNutzer);

// hier stand zeile y
return 1;
}

void main()
{

NUTZER* ersterNutzer;
int erg;

ersterNutzer = (NUTZER*) calloc(1, sizeof(NUTZER));
ersterNutzer->next = NULL; // Falls mal jemand auf malloc umschwenkt ;).

// Zeile x stand hier
erg=bla(ersterNutzer);
//zeile z stand hier

listeLoeschen(ersterNutzer);
}


Davon abgesehen hat eine verkettete Liste auch ihre Nachteile. Z. B. dass du kein Element direkt per Index adressieren kannst, sondern dich immer per next durchhangeln musst (siehe listeLoeschen).

Ein Array hätte auch funktioniert, indem du der Funktion bla einen Pointer auf den Pointer der main-Funktion mitgibst und den Pointer in der main direkt von bla aus überschreibst. Genau das hast du ja schon versucht, siehe Bernis Korrekturvorschlag. Du kannst natürlich auch ein struct zurückgeben. Siehe auch http://www.forum-3dcenter.org/vbulletin/showthread.php?t=444920.

Edit: im Beispiel oben ist die Reihenfolge der Elemente am Ende nicht die Einfügereihenfolge (ist aber mit einem weiteren Pointer durchaus machbar).

[mf_2]

Ich habe jetzt wieder ein Problem, und zwar bereits im typedef für die neue Struktur:

typedef struct
{
int uid;
char login[51];
NUTZER* next;
} NUTZER;


Da sagt mir das Visual Studio in der Zeile 'NUTZER* next;' folgendes:
syntax error : identifier 'NUTZER'

Ich habe es auch schon einmal mit 'NUTZER *next;' probiert, kein Erfolg.
Ich habe dann mal nach Strukturdefinitionen gesucht und die sehen von der Syntax her auch so aus. Daher sehe ich den Fehler nicht. Wüsstet ihr da weiter?

Ich bin eher für verkettete Listen, da das Argument vom Gast durchaus sinnvoll erscheint: Wenn bei realloc() immer der ganze Speicher neu allokiert wird, ist das irgendwie nicht so elegent.

EDIT: Notepad++ zeigt auch keine unsichtbaren Zeichen am Zeilenende.

[robobimbo]

typedef struct
{
int uid;
char login[51];
struct NUTZER* next;
} NUTZER

[Gnafoo]

Da haben mir die kleinen aber feinen Unterschiede zwischen C++ und C mal wieder einen Streich gespielt :D.

Ich bin eher für verkettete Listen, da das Argument vom Gast durchaus sinnvoll erscheint: Wenn bei realloc() immer der ganze Speicher neu allokiert wird, ist das irgendwie nicht so elegent.

Wenn man es richtig macht, dann kann man mit einem Array trotzdem einen amortisiert konstanten Aufwand für das Einfügen hinbekommen (afair, indem man die Größe immer verdoppelt) und erhält den direkten Zugriff per Index und die bessere Cache-Effizienz dazu. Dafür geht Einfügen und Löschen an beliebigen Stellen in einer Linked-List effizienter.

Hat eben beides seine Vor- und Nachteile.

[mf_2]

So, jetzt klappt es mit den verketteten Listen! *freu*
Aber leider hat die Liste nun immer ein leeres Element am Anfang. Wie kann ich das ändern?
Ich habe mal das Folgende entfernt:

ersterNutzer = (NUTZER*) calloc(1, sizeof(NUTZER));
ersterNutzer->next = NULL; // Falls mal jemand auf malloc umschwenkt ;).

Aber dann geht es nicht mehr. Dann verendet das Programm zur Laufzeit beim Aufruf von bla(), da 'ersterNutzer' nicht initialisiert ist.

[Gnafoo]

Du machst aus der Liste selbst ein struct, in welchem der Pointer auf das erste Element steht und passt beim Einfügen auf, ob der Pointer NULL ist. Rein logisch ist die Liste an sich ja schon ein Objekt, auch wenn sie leer ist. Mal als (ausführliches :D) Startbeispiel:


// Listeneintrag mit Pointer auf Datenobjekt.
struct list_entry
{
void* obj;
struct list_entry* next;
};

// Die Liste selbst mit Pointer auf Anfang und Ende.
// (Zum schnelleren Zugriff auf das letzte Objekt.)
struct linked_list
{
struct list_entry* first;
struct list_entry* last;
};

// Eintrag am Ende der Liste einfügen.
void list_add_last(struct linked_list* list, void* object)
{
struct list_entry* entry = (list_entry*)calloc(1, sizeof(list_entry));
entry->next = NULL;
entry->obj = object;

if (list->last == NULL)
{
// Ersten Eintrag einfügen.
list->first = list->last = entry;
}
else
{
// Eintrag an letzter Stelle einfügen.
list->last->next = entry;
list->last = entry;
}
}

// Eintrag am Anfang der Liste einfügen.
// Fast identisch mit list_add_last.
void list_add_first(struct linked_list* list, void* object)
{
struct list_entry* entry = (list_entry*)calloc(1, sizeof(list_entry));
entry->next = NULL;
entry->obj = object;

if (list->first == NULL)
{
// Ersten Eintrag einfügen.
list->first = list->last = entry;
}
else
{
// Eintrag an erster Stelle einfügen.
entry->next = list->first;
list->first = entry;
}
}

// Lösche ersten Eintrag mit gegebenem Objekt.
void list_remove(struct linked_list* list, void* obj)
{
struct list_entry* last = NULL;
struct list_entry* current = list->first;

// Durchsuche die Liste.
while (current != NULL)
{
// Objekt gefunden?
if (current->obj == obj)
{
// Beim ersten Eintrag list->first anpassen.
if (current == list->first)
list->first = current->next;

// Beim letzten Eintrag list->last anpassen.
if (current == list->last)
list->last = last;

// Beim vorigen Eintrag next neu setzen.
if (last != NULL)
last->next = current->next;

free(current);
return;
}
else
{
last = current;
current = current->next;
}
}
}

struct linked_list* list_create()
{
struct linked_list* list = (linked_list*)calloc(1, sizeof(linked_list));
list->first = list->last = NULL;
return list;
}

void list_destroy(struct linked_list* list)
{
list_entry* tmp;
list_entry* entry = list->first;

// Lösche alle Einträge.
while (entry != NULL)
{
tmp = entry;
entry = entry->next;
free(tmp);
}

// Lösche die Liste selbst.
free(list);
}

void show_list(struct linked_list* list)
{
list_entry* entry = list->first;
while (entry != NULL)
{
printf("%s\n", (char*)entry->obj);
entry = entry->next;
}
}

int main(int argc, char* argv[])
{
char* first = "Hallo";
char* second = "Welt";
char* third = "Test";
char* fourth = "123";

linked_list* list = list_create();

list_add_last(list, second);
list_add_last(list, second);
list_add_last(list, third);
list_remove(list, second);
list_add_first(list, first);
list_add_last(list, fourth);

show_list(list);
list_destroy(list);

return 0;
}


Statt der char* kannst du natürlich auch jeden anderen Pointer für die Elemente der Liste verwenden, z. B. dein NUTZER*. Oder du integrierst NUTZER direkt in list_entry. Dann ist es aber nicht mehr so flexibel einsetzbar.

Wenn du durch die Liste durchgehst kannst du das Entfernen eines Eintrages (dessen list_entry du schon hast) natürlich auch schneller erledigen, indem du einfach die next-Pointer entsprechend verbiegst. Allerdings musst du dann bei first und last aufpassen.

Ich habe jetzt nicht alle Extremfälle überprüft, aber auf den ersten Blick funktioniert das Beispiel.

[MikeB]

Müsste es nicht eigtl. so heißen:
int bla(NUTZER **nutzerdb)
{

*nutzerdb = (NUTZER*) realloc(*nutzerdb,2*sizeof(NUTZER));
// hier stand zeile y
return 1;

}

Natürlich ist das die richtige Lösung...
Was soll das jetzt plötzlich mit den ganzen verketteten Listen?

[Gast]

Natürlich ist das die richtige Lösung...
Was soll das jetzt plötzlich mit den ganzen verketteten Listen?
Weil
Wenn ich mich recht entsinne muss realloc() immer einen zusammenhängenden Speicherbereich zurückgeben

Ich hoffe es ist einigermaßen einsichtig dass bei einer Datenstruktur die ständig ihre Größe ändert realloc() nicht das sinnvollste ist... außer man steht drauf dauernd sinnlos spiecher durch die gegend geschoben wird. ;)

[Gnafoo]

Ich hoffe es ist einigermaßen einsichtig dass bei einer Datenstruktur die ständig ihre Größe ändert realloc() nicht das sinnvollste ist... außer man steht drauf dauernd sinnlos spiecher durch die gegend geschoben wird. ;)

Naja im gegebenen Fall ist es vermutlich relativ egal. Wie gesagt: wenn das sinnvoll implementiert ist, ist das Umkopieren der Daten nicht allzu schlimm, weil es mit steigender Array-Größe zunehmend seltener passiert. Und die Fragmentierung ist wirklich nur dann ein Problem, wenn das Programm insgesamt sehr viel Speicher benötigt.

Trotzdem kann es nicht schaden, sowohl dynamische Arrays und Linked-Lists zu kennen. Schließlich haben beide ihre jeweiligen Anwendungsfelder. Ich nehme an, mf_2 reicht realloc völlig aus, aber ich dachte ein Beispiel zu Linked-Lists kann nicht schaden :D. Hatte mich gerade etwas in den Fingern gejuckt, mal wieder ein wenig C-Code zu schreiben.

[MikeB]

Find ich schön zu sehen, dass es noch Programmierer gibt, die verkettete Listen ohne std::list hinkriegen. :smile:
Ist ja heute keine Selbstverständlichkeit mehr... Zumal die "modernen" Sprachen ja keine Pointer mehr kennen.

[Ectoplasma]

Find ich schön zu sehen, dass es noch Programmierer gibt, die verkettete Listen ohne std::list hinkriegen. :smile:
Ist ja heute keine Selbstverständlichkeit mehr... Zumal die "modernen" Sprachen ja keine Pointer mehr kennen.

Dein Statement hinterläßt bei mir diverse Fragezeichen. Was ist denn an einer Verketteten Liste so schwierig?

[MikeB]

Es gibt genügend "Programmierer" die bei einer hierarchischen doppelt verketteten Liste verzweifeln würden wenn sie denn wenigstens wüssten was das ist.
Ist halt meine traurige Erfahrung.

[Gast]

Naja im gegebenen Fall ist es vermutlich relativ egal. Wie gesagt: wenn das sinnvoll implementiert ist, ist das Umkopieren der Daten nicht allzu schlimm, weil es mit steigender Array-Größe zunehmend seltener passiert. Und die Fragmentierung ist wirklich nur dann ein Problem, wenn das Programm insgesamt sehr viel Speicher benötigt.

Hmmm, irgendwie komm ich jetzt grad nicht mit.
Gerade bei steigender Arraygröße wird es doch erst zum Problem, weil die Chance dass der aktuelle Block vergrößert werden kann immer kleiner wird -> realloc() muss das ganze Zeuch durch die Gegend schieben an eine neue Position.
Mit einer Liste hast du dieses Problem schonmal nicht.

Was man verwendet ist natürlich eine Designfrage - gehts um ein Betriebssystem mit max. 10-20 Nutzern oder um eine Webapp mit gleich einmal ein paar zehntausend?
Ich persönlich würde jedoch aus oben geannten Gründen unabhängig davon die Liste nehmen, das scheint mir bei so Sachen die ständig ihre Größe ändern einfach angebrachter.


Trotzdem kann es nicht schaden, sowohl dynamische Arrays und Linked-Lists zu kennen. Schließlich haben beide ihre jeweiligen Anwendungsfelder. Ich nehme an, mf_2 reicht realloc völlig aus, aber ich dachte ein Beispiel zu Linked-Lists kann nicht schaden :D. Hatte mich gerade etwas in den Fingern gejuckt, mal wieder ein wenig C-Code zu schreiben.

[Berni]

In dem Fall wirds aber wohl um ein paar wenige Nutzer gehen. Für mehrere tausend Nutzer wird man wohl kaum mehr heutzutage reines C verwenden und außerdem wäre dann wohl auch eine Datenbank oder eine andere persistente Speicherung eher angebracht weil sonst beim Programmneustart alle Accounts wieder weg sind.
Wenn man das Array gleich um mehr Speicher erweitert als nötig (z.B. immer auf die doppelte Größe oder aber z.B. 100 Elemente mehr), dann braucht man auch nicht bei jedem User eine Vergrößerung vornehmen (man muss die wahre Größe natürlich als separates Integer mitspeichern und beim Löschen muss man mitunter einiges an Daten im Array verschieben). Gnafoo hatte das schon angsprochen und so würde ich es imho lösen. Man muss auch bedenken, dass die Referenzen in der verketteten Liste auch RAM brauchen (zwar sehr wenig aber wenn es wirklich um x-tausende Elemente gehen sollte kann es schon signifikant werden) und es somit wohl kaum Szenarien geben wird, in denen die verkettete Liste noch funktioniert, ein Array mit realloc aber nicht mehr.

@MikeB: Ich kenne nur normale doppelt verkettete Listen. Wofür steht denn das hierarchisch? Google wollte mir auch nicht wirklich weiterhelfen...

[MikeB]

@MikeB: Ich kenne nur normale doppelt verkettete Listen. Wofür steht denn das hierarchisch? Google wollte mir auch nicht wirklich weiterhelfen...
Kann man für Windows/UIs gut brauchen, Elemente in der Verketteten Liste haben dann nicht nur Next/Prev, sondern auch noch Parent/ChildFirst/ChildLast.

[Funky Bob]

Rein theoretisch könnte man es auch kombinieren und in den scructs entsprechende Arrays anlegen. Wenn das eine Array voll ist wird per Struct ein neues angelegt....

Das erfordert mehr Entwicklungsaufwand, aber vemindert Speicherverschiebungsaktionen und hunderttausende von überflüssigen Next-Pointern.

[Abraxus]

Kann man für Windows/UIs gut brauchen, Elemente in der Verketteten Liste haben dann nicht nur Next/Prev, sondern auch noch Parent/ChildFirst/ChildLast.
Das nennt man dann einen Baum

[Aquaschaf]

Hmmm, irgendwie komm ich jetzt grad nicht mit.
Gerade bei steigender Arraygröße wird es doch erst zum Problem, weil die Chance dass der aktuelle Block vergrößert werden kann immer kleiner wird -> realloc() muss das ganze Zeuch durch die Gegend schieben an eine neue Position.

Je größer das Array, desto mehr insert-Operationen sind nötig damit es wieder voll wird. Das umkopieren wird teurer, aber seltener.

In diesem Fall ist es vermutlich ziemlich egal, was man verwendet. Und wenn Laufzeit & Speicherverbrauch kritisch werden, dann hängt es davon ab welche Operationen man braucht.

Wie bereits gesagt kann man es auch hybrid machen. Mit einer Mischung aus directory und cyclic arrays bekommt man sogar konstanten random access und insert/delete in O(sqrt(n)) hin..