Shared Variables Between Repeated Calls-CodePudding

I'm learning C , so I'm wrote a linked list implementation with some basic utilities. My insert function takes in a node pointer and iterates to the end of the list to append a newly initialized Node object, p. To my suprise, repeated calls to the insert method appear to share node p!? Thus after many invocations, insert will assign p->next to itself, inducing an infinite loop.

#include <iostream>
#include <string>

using namespace std;

struct Node {
    Node *next; 
    int val;
};

void insert(Node *n, int val) {
    Node * cur = n;
    while (cur->next) {
        cout << "Val " << cur->val << "\n";
        cur = cur->next;
    }
    Node p = {0, val};
    cur->next = &p;
}

int main() {
    Node n1;
    n1.val = 1;
    insert(&n1, 2);
    insert(&n1, 3);
    insert(&n1, 4);
    return 0;
}

I ran this through gdb to look at what is going on in insert. Indeed, in the second call to insert I found that p was already initialized before executing Node p = {0, val}; and that future calls preserved the same value of p->next despite explicitly setting it to 0. I seem to have a gap in my understanding because translating this into C produces the same bug. I was only able to fix with malloc which is not what I want.

Why does it occur? p is allocated onto the stack per invocation no?

CodePudding user response：

After insert function returns, local variables cur and p are destroyed and that memory space is available for reuse. You are not allowed to access a variable after it is destroyed, not even with a pointer, because the memory space can be reused for something else. The compiler isn't smart enough to stop you from doing it anyway.

As you see this is not just a theoretical possibility but actually happens, all the time. If you just call the exact same function again it's quite likely that you'll get the exact same memory arrangement so the variable p the second time will use the exact same memory space it used the first time. If you call a different function like printf (or cout <<) instead of insert, you might find that space is overwritten with some of the variables inside printf.

This is why every single linked list tutorial tells you to use malloc. Apart from global variables, it's basically the only way to create some variable that isn't deleted when the function returns. A "variable" created by malloc isn't ever deleted until you free it. (It also has no name, so pointers are the only way to use that variable and this fact seems to confuse many people.)

CodePudding user response：

@user53751 is quite correct that your problems derive from variable lifetime issues. However, malloc and free are not the proper C tools to use to achieve dynamically allocated memory. Rather you should use new and delete for this purpose, especially as they not only allocate the correct size memory for the object, but also run the default constructor, or as I've written it below, initialize the next pointer to nullptr.

You may also wish to make insert a member function of Node as C will allow you to do so.

struct Node {
    Node *next = nullptr; 
    int val;

    void insert(int val) {
        Node *temp;
        for (temp = this; temp->next; temp = temp->next);

        temp->next = new Node;
        temp->next->val = val;
    }
};

int main() {
    Node *a = new Node;
    a->val = 1;
    
    a->insert(2);
    a->insert(3);

    for (Node *temp = a; temp; temp = temp->next) {
        std::cout << temp->val << std::endl;
    }

    return 0;
}

It would also be advisable to define a destructor so you can easily clean up your dynamically allocated memory. Shown in a simple, naive recursive fashion for demonstration purposes.

struct Node {
    Node *next = nullptr; 
    int val;

    void insert(int val) {
        Node *temp;
        for (temp = this; temp->next; temp = temp->next);

        temp->next = new Node;
        temp->next->val = val;
    }

    ~Node() {
        if (next) delete next;
    }
};