Differenzieren zwischen Stack und Heap-Speicher

Question

Lassen Sie uns sagen, dass ich eine Liste Implementierung haben, die listnode_t folgende Verwendungen:

typedef struct ListNode { 
    struct ListNode *next; 
    struct ListNode *prev; 
    void *value; 
} listnode_t; 

Dies ist eine doppelt verknüpfte Liste, wie Sie sehen können. Ich habe auch eine list_t, die zwei Zeiger auf listnode_t als erster und letzter Knoten und Größe der Liste haben. Jetzt asume Ich habe folgende in meinem Haupt

int main(int argc, char *argv[]){ 
    ... 
    // Create two empty lists 
    list_t *list1 = make_list(); 
    list_t *list2 = make_list(); 

    // Populate one with ints 
    int x = 4; 
    int y = 5; 
    list_push(list1, &x); 
    list_push(list1, &y); 

    // Populate other with strings 
    string_t *str1 = make_string("foo"); 
    string_t *str2 = make_string("bar"); 
    list_push(list2, str1); 
    list_push(list2, str2); 
    ... 

    // Delete at the end 
    destroy_list(list1); 
    destroy_list(list2); 
} 

Ich habe ein Problem mit destroy_list implementieren. Hier ist was ich versucht habe;

void destroy_list(list_t *list) 
{ 
    listnode_t *cur = list -> first; 
    for(cur = list -> first; cur != NULL; cur = cur -> next){ 
     if(cur -> prev){ 
      free(cur -> prev); 
     } 
    } 

    free(list -> last); 
    free(list); 
    list = NULL; 
} 

Mein Problem ist, dass ich versuche, void * im listnode_t zu verwenden, um der Lage sein, die allgemein diese Liste zu verwenden. Aber wenn ich Dinge lösche, scheint die Anwendung free(cur -> prev) problematisch. Wenn ich eine Liste von Dingen wie Ints wie oben verwende, da diese auf dem Stack zugewiesen sind, geht es gut, denke ich. Aber wenn ich eine String-Liste wie oben hatte, muss ich, da ich die dynamische Zuweisung in meiner String-Implementierung verwende, zuerst free(cur -> prev -> value) anwenden. Ich weiß nicht, wie kann ich das tun, weil, wenn ich es addiere, dann bekomme ich ein anderes Problem des Versuchens, einen Stapel zu befreien, der Gedächtnis auf dem Haupt zugeteilt wird.

Was soll ich tun, ich bekomme dieses generische Listenverhalten nicht.

Answer 1

// Populate one with ints 
int x, y = 4, 5; 
list_push(list1, &x); 
list_push(list1, &y); 

Tun Sie dies nicht.

Die Schnittstelle, die Sie für Ihre list Struktur etabliert haben, so effektiv, dass „Eigentum“ des Zeigers auf die Liste gelangt, wenn list_push genannt wird, und dass der Zeiger free() d von der Liste in destroy_list sein. Das Übergeben eines Zeigers an eine Stapelvariable verstößt gegen diese Schnittstelle. Wenn Sie eine Ganzzahl übergeben möchten, müssen Sie eine Kopie für die Liste erstellen, für die die Besitzerschaft übernommen werden soll.

Eine alternative Schnittstelle für die list Struktur könnte sein, einen Zeiger und eine Länge an list_push zu übergeben, und diese Funktion eine Kopie der Struktur nehmen lassen, anstatt sie zu behalten. Ob dies angemessen ist, hängt von dem Anwendungsfall ab, den Sie für diese Struktur berücksichtigen.

(.. Auch dann, wenn int x, y = 4, 5 nicht tun, was Sie denken, es tut Sie wahrscheinlich int x = 4, y = 5 bedeuten)

Answer 2

int x, y = 4, 5;

Ich glaube nicht, dass dies tut, was Sie denken, dass es tut.

Aber wenn ich Dinge löschen, scheint die Anwendung cur -> prev problematisch.

"problematisch" ist kein technologischer Begriff. Beschreiben Sie genau, was Sie erwartet haben und was genau passiert.

Wenn ich eine Liste von Dingen wie ints wie oben verwende, da diese auf Stapel zugeordnet sind, geht es gut, denke ich.

Nein, sie sind alles andere als in Ordnung. Wenn Sie die Adresse einer Variablen auf dem Stack übernehmen, stellen Sie sich für große Enttäuschung auf, denn sobald Ihre Funktion zurückkehrt, ist der Stack Müll.

Aber wenn ich Liste von Strings, wie oben, da ich die dynamische Zuordnung in meinen String Implementierung verwende ich cur -> prev -> value erste

Was anwenden müssen, meinen Sie „apply“? Und was meinst du mit "zuerst"?

Ich weiß nicht, wie ich das tun kann, denn wenn ich es hinzufügen,

Was meinst du mit „add“? Was ist es"? Hinzufügen zu was? In technischen Texten verwenden wir niemals Präpositionen wie "es" und "das". Sprich es aus.

dann bekomme ich ein weiteres Problem zu versuchen, einen Stapel zugewiesenen Speicher auf Main zu befreien.

Wieder sagt "Problem" nicht viel. In jedem Fall, wenn ich bin erraten was Ihr Problem ist, ist die Lösung einfach: immer Platz für value zuweisen, so dass Sie es immer frei.

if(cur -> prev){ 
     free(cur -> prev); 
    } 

, die nicht, wie Sie Knoten aus einer doppelt verknüpften Liste löschen ist. Um den Knoten Y aus einer doppelt verketteten Liste zu löschen, müssen Sie zunächst den Knoten Y aufheben, so dass der Knoten 0 auf den Knoten X zeigt und der Knoten next auf den Knoten Z zeigt. Anschließend können Sie den Knoten Y freigeben. (Nach dem Freigeben seines Wertes.) Und natürlich muss man immer im Auge behalten, dass Knoten Y der erste oder der letzte Knoten in der Liste sein kann, in diesem Fall hat er keinen vorherigen oder nächsten Knoten und stattdessen müssen Sie beides ändern der Kopf oder das Ende der Liste strukturieren sich selbst.

Answer 3

Der Benutzer muss eine Funktion zur Verfügung stellen, um value zu zerstören, da nur der Benutzer der Liste weiß, was gespeichert ist und was zu tun ist.

Damit Ihre Liste generisch ist, muss make_list als Parameter die Funktion haben, den Wert zu zerstören. Als Teil Beispiel:

struct LISTROOT { 
    listnode_t list; 
    void (*freeitem)(void * value); 
}; 
struct LISTROOT myList; 

struct MYTYPE { 
    char *buffer; 
    int *whatever; 
}; 
void myFreeItem(struct MYTYPE *item) 
{ 
    if (item) { 
     if (item->buffer) free(item->buffer); 
     ... 
     free(item); 
    } 
    } 

myList.list= make_list(myFreeItem); 

und in Ihrem Code:

if(cur -> prev){ 
     if (myList.freeitem) mylist.freeitem(cur->value); 
     free(cur -> prev); 

Beachten Sie, dass die Liste freeitem definiert myFreeItem einen void * Wert und den Benutzer nehmen nimmt einen Zeiger auf eine komplexere struct. Der Compiler akzeptiert dies und ermöglicht es Ihnen, die Komplexität dessen, was in der Liste gespeichert ist, zu verbergen.

Answer 4

Ein sehr allgemeines Modell ist für den Aufrufer Ihrer Schnittstelle, um anzugeben, ob Dinge durch den Container freigegeben werden sollen oder nicht. dh

list_t *list1 = make_list(0); // dont free items 
list_t *list1 = make_list(1); // free items 

und wenn sie ‚bitte frei‘ sagen, dann rufen Sie einfach free für sie.Dies ist einfacher als der generische 'hier ist ein kostenloser Rückruf', den der Anrufer liefern muss (Vorgeschlagen von einer anderen Antwort)

Answer 5

Eine einfache und eher sichere Lösung wäre, die Liste Kopien der übergebenen Werte verwalten zu lassen Die Liste ist verantwortlich für das Zuweisen und Freigeben des Speichers ordnungsgemäß. Siehe den folgenden Code, der die struct ListNode und die list_push-Funktion entsprechend anpasst. Beachten Sie, dass die Struktur keinen Zeiger mehr auf den Wert enthält. Stattdessen speichert es den Wert im Element value[] mit variabler Länge und weist genügend Speicher für die Struktur selbst zu. Wenn Sie das struct-Objekt später freigeben, wird automatisch auch der Speicher für die Kopie des Werts freigegeben.

typedef struct ListNode { 
    struct ListNode *next; 
    struct ListNode *prev; 
    char value[]; 
} listnode_t; 

void list_push(list_t *t, void *value, size_t valueSize) { 

    listnode_t *newNode = malloc(sizeof(listnode_t) + valueSize); 
    memcpy (newNode->value, value, valueSize); 

    // ... any code necessary for attaching the new node to the list goes here 
}