Ich habe eine generische Verkettungslistenimplementierung mit einer Knotenstruktur, die void * zu Daten enthält, und einer Listenstruktur, die einen Verweis auf head enthält. Jetzt ist hier mein Problem, dass ein Knoten in der verknüpften Liste einen Verweis auf eine andere verknüpfte Liste über sein void * enthalten kann. Dies führt zu Speicherverlusten, wenn ich die größere Liste mit kleineren Listen freilasse. Also frage ich mich, ob es eine Möglichkeit gibt zu überprüfen, ob das void * auf eine andere Liste verweist, also folge ich und befreie das auch oder nur zu Daten.
Wenn ich einen Schlüssel am Anfang meiner Struktur anfüge, eine magische Zahl, die ich überprüfen kann, indem ich das void * dereferenziere und herausfinde, dass es sich um eine Liste handelt?
BEARBEITEN: Anrufer fügen nicht die kleineren Listen ein, die sie durch meine Funktionen eingefügt haben. Ich möchte nicht, dass die Anrufer sich damit beschäftigen, mehrere Listen zu veröffentlichen, nur denjenigen, an den sie einen Zeiger halten.
Diese Frage hängt wirklich davon ab, wessen Verantwortung es ist, die Einträge in der Liste zu bereinigen. Wenn Ihre Struktur für das Bereinigen des Speichers zuständig ist, auf den die void * -Felder verweisen, dann haben Sie hier ein viel größeres Problem, nämlich dass bei einem void * , das auf einen beliebigen Speicherblock verweist, Sie nie wissen, was der richtige Weg ist es zu entziehen ist. Wenn Sie zum Beispiel eine Implementierung eines dynamischen Arrays in den Zeilen von C ++ std::vector haben, kann Ihre void * auf eine Struktur zeigen, die selbst einen Zeiger enthält, und Ihre Liste muss wissen, dass sie absteigen muss in diese Struktur, um ihren dynamisch zugewiesenen Block rekursiv freizugeben. Der Fall, den Sie beschreiben, wo Sie eine geschachtelte Liste durchlecken, ist nur ein Spezialfall dieses allgemeineren Problems.
Wenn andererseits die Liste nicht dafür verantwortlich ist, den Speicher zu bereinigen, auf den das von ihr gespeicherte void * s verweist, sollten Sie sich über dieses Problem überhaupt keine Gedanken machen.
Wenn Ihre Liste Eigentümersemantik hat und den Speicher für die darin gespeicherten Elemente bereinigen muss, rate ich Ihnen dringend davon ab, eine magische Zahl zu verwenden, um festzustellen, ob Sie eine verschachtelte Liste haben. Stattdessen sollte der Client Ihnen wahrscheinlich einen Funktionszeiger zur Verfügung stellen, der eine Deallokationsroutine enthält, die auf den in die Liste eingefügten Elementen ausgeführt wird. Auf diese Weise kann Ihr Code den vom Benutzer bereitgestellten Bereinigungscode verwenden, um sicherzustellen, dass alle in der Liste gespeicherten Elemente bereinigt werden.
Es kann nicht nur sein void* auf eine Liste zeigen. Es könnte auf dynamisch zugewiesenen Speicher zeigen.
Die Art und Weise, wie GLib dieses Problem behandelt, besagt, dass der Anrufer dafür verantwortlich ist, sicherzustellen, dass alles, auf das die void *data einer Liste verweist, freigegeben wird. Siehe Ссылка .
Die Alternative (die GLib ebenfalls bereitstellt) besteht darin, eine Funktion zu erstellen, die einen Funktionszeiger annimmt und diese bei jedem void *data aufruft, während sie die Liste durchläuft. Nachschlagen g_list_free_full .
Mein Rat wäre, die Dinge ein wenig zu vereinfachen und einfach sicherzustellen, dass eine verknüpfte Liste nur einen Objekttyp enthält.
Wenn Sie das nicht können, hätte ich wahrscheinlich jeden Knoten in der Liste nicht nur einige Daten, sondern auch einen Zeiger auf eine Funktion, die weiß, wie man Elemente dieses Typs freigibt. Zwangsläufig, zwei Wochen, nachdem Sie Ihren speziellen Code für eine verknüpfte Liste geschrieben haben, entscheiden Sie, dass Sie auch eine andere magische Zahl benötigen, um ein dynamisches Array usw. Zu halten.
Um die Frage zu beantworten, was ist die Weisheit von "Wenn ich einen Schlüssel am Anfang meiner Struktur hinzufüge eine magische Zahl, die ich überprüfen kann, indem ich die void * deneferenziere und herausfinde, dass es eine Liste ist?"
Ja, Sie können dies tun, aber nur wenige würden es empfehlen. Seien Sie einfach wirklich sicher, dass der "magische" Wert sonst nicht auftreten kann. Das ist eine ziemlich große Frage. Sie möchten prüfen, auf was Sie sonst noch zeigen und welche Werte es annehmen könnte, wenn es als etwas wie eine vorzeichenlose Ganzzahl dargestellt wird. Denken Sie daran, dass, wenn Sie sich entscheiden, dass es eine Liste ist, Sie es befreien werden und folglich wahrscheinlich abstürzen und brennen werden, wenn Sie falsch liegen.
Die einfachste effektive Lösung besteht darin, dass Sie, wenn Sie einen Knoten wissen müssen, dass er auf eine Liste zeigt, im Knoten eine Markierung angeben.
Wenn Sie wirklich wollen, dass die Liste die Verantwortung für die Freigabe aller Inhalte übernimmt, brauchen Sie mehr als eine Flagge, Sie müssen wissen, wie jeder frei ist. Das könnte eine ID oder etwas wie ein Zeiger auf die Funktion sein, die ihren Inhalt freigibt.
Tags und Links c pointers data-structures linked-list void-pointers