pointers - inconsistent access to memory location

Question

I am trying to define a simple linked list

#include <stdio.h>


struct node{
  int value;
  struct node* next;
};


typedef struct {
  struct node* root;
} ll;

void add_to_ll(int value, ll* linked_list) {
  struct node new_node = {value, linked_list->root};
  linked_list->root = &new_node;
}

void print_ll(ll* ll2) {
  printf("%p", ll2);
  struct node* temp = ll2->root;
  while (temp->next != NULL) {
    printf("%d ", temp->value);
    temp = temp->next;
  }
}


int main()
{
  printf("Creating a linked list...\n");
  struct node root_node = {1, NULL};
  ll my_linked_list = { &root_node };
  for (int i = 0; i < 10000; i++) {
    add_to_ll(i, &my_linked_list);
  }
  printf("my_linked_list root value %d\n", my_linked_list.root->value);
  printf("my_linked_list root value %d\n", my_linked_list.root->value);
  printf("my_linked_list root value %d\n", my_linked_list.root->value);
  return 0;
}

The output I am getting is:

Creating a linked list...
my_linked_list root value 9999
my_linked_list root value 429391991
my_linked_list root value 429391991

I am able to get the value of the root node correctly the first time. But on trying to read it the second time (and thereafter) the value changes. What am I missing?

`add_to_ll` is *not* allocating any memory. It is adding a dangling pointer to your list (well, it is allocating it temporarily, until exiting).. And you are seeing a nice illustration of *undefined behavior*. — Eugene Sh., Sep 29 '17 at 19:05
The memory allocated for `new_node` is only available until `add_to_ll` returns, so returning a pointer to that memory is undefined behaviour. You need to use `malloc` to allocate the new node somewhere longer lasting. — ikegami, Sep 29 '17 at 19:09
[Useful reading](https://stackoverflow.com/questions/13415321/difference-between-static-auto-global-and-local-variable-in-the-context-of-c-a) — ikegami, Sep 29 '17 at 19:18

score 2 · Answer 1 · edited Sep 29 '17 at 19:12

2

Your problem is with the memory allocation strategy in add.

void add_to_ll(int value, ll* linked_list) {
  struct node new_node = {value, linked_list->root};
  linked_list->root = &new_node;
}

Here you're instatiating new_node as a local variable. Non-static local variables have a lifespan equal to that of their block. After you exit the block, that memory (which is actually the stack) is available for successive allocations that will overwrite your object. Use explicit allocation, that means malloc, to have objects whose lifespan is independent from the scope of allocation.

I would also point out the naming... The most explicit name should be that of the type, not the variable. So struct linked_list ll and not the other way around.

edited Sep 29 '17 at 19:12

ikegami

367,544
15
269
518

answered Sep 29 '17 at 19:10

rzippo

979
12
22

Using `malloc()` is one of several possible techniques that could be used to solve the problem but telling OP to use it without mentioning the lifetime issue is trading a memory leak problem for an undefined behavior problem. And your "naming" comment is totally off topic for this question.. [There-- I feel better and I didn't even have to mention that my, simpler, clearer and pragmatically if not pedantically correct answer was posted before this answer, and before the comments on the issue [grin]] – Dale Wilson Oct 02 '17 at 16:00
I formulated the answer as such assuming OP is a novice to C programming. That's why I talked abundantly about local allocation, pointed the naming, and only casually named `malloc()`, so to suggest the next step in OP's studying and hope that (s)he gets to know about memory leaks before calling the excercise solved. I could always remove the unnecessary parts and provide working and safe code, but that would benefit the question at the expense of OP – rzippo Oct 02 '17 at 16:24

score 0 · Answer 2 · answered Sep 29 '17 at 19:06

0

This function:

void add_to_ll(int value, ll* linked_list) {
  struct node new_node = {value, linked_list->root};
  linked_list->root = &new_node;
}

Constructs a node on the stack and adds it to the list. When you return from this function the stack is popped and the list root points to unallocated memory on the stack that will later be reused.

answered Sep 29 '17 at 19:06

Dale Wilson

9,166
3
34
52

There's no guarantee that a stack is used. The important part is that the memory is only reserved for `new_node` until the end of the block (i.e. until the function returns). /// This answer would be better if it provided a solution to the problem. – ikegami Sep 29 '17 at 19:16
There is a difference between what the standard promises (limited lifetime with nothing to say about location) vs what every compiler I've worked with in 30 years actually does (allocates space for the structure on the stack) vs what is easy for the OP to understand if he wrote this code in the first place. Talking about the structure on the stack is the simplest way to convey the concept. – Dale Wilson Sep 29 '17 at 19:29
Even forgetting correctness, adding irrelevant details doesn't help the OP understand. No reason to mention the storage location at all. – ikegami Sep 29 '17 at 19:29
Yes he should use malloc (or one of it's relatives) to allocate space for the new node, but I'm not about to get into the entire issue of memory management in C. A "solution" to this problem wouldn't fit in the margins of the answer [that's an obscure joke] – Dale Wilson Sep 29 '17 at 19:31

pointers - inconsistent access to memory location

2 Answers2