Does malloc assign memory in the same location if you use the same variable name again on every iteration of a loop?

Question

I am writing code to take in a weighted adjacency list in C. Each edge is stored in the form of a struct. I created an array of pointers where each pointer leads to the list for a node. Here's what I did:

#include <stdio.h>
#include <stdlib.h>

struct edge {
    int u;
    int v;
    int w;
};

// taking a weighted adjacency list 
int main() {
    int n; // number of nodes
    scanf("%d ", &n);
    struct edge **list[n];
    int p = n;
    while (p) {
        struct edge *n_list = (struct edge *)malloc(n * sizeof(struct edge));
        int num = 1;
        for (int i = 0; i < n; i++) {
            n_list[i].u = n - p;
            scanf("%d ", &n_list[i].v);
            if (n_list[i].v == -1) {
                n_list[i].w = -1;
                break;
            } else {
                num++;
                scanf("%d ", &n_list[i].w);
            }
        }
        
        n_list = (struct edge *)realloc(n_list, num * sizeof(struct edge));
        list[n - p] = &n_list;
        struct edge *ptr = *list[n - p];
        for (int j = 0; j < num - 1; j++) {
            printf("%d %d %d\n", ptr[j].u, ptr[j].v, ptr[j].w);
        }
        p--;
    }
}

The problem is that the edges get printed correctly but after the whole iteration over p (number of nodes), every element in the array of pointers (list) has the same address stored. I'm guessing that everytime I use malloc for n_list, it is allocating memory in the same location, thereby erasing the list for the previous node when I start taking input. How can I ensure this does not happen? Also any easier methods to go about this task are welcome.

In this line list[n-p]=&n_list; what is &n_list? WIll it ever change between nodes? You must allocate memory for list[x], not only for list. BTW: malloc does not know what you do with the result. Your assumption to return same address is wrong. — Gerhardh
– Gerhardh, Commented Oct 17, 2024 at 9:39
In your code, there is no risk that malloc allocates memory in the same location, since you do not free the allocated memory. — CGi03
– CGi03, Commented Oct 17, 2024 at 9:45
"Yes, n_list is specific to each node" You missed the point. I asked about &n_list. n_list is a local variable which only exists once. If you take the address of it, it will always be the same. That means, in each iteration of overwrite previous content and all list[x] entries will point to the same address. Additionally, that address will become invalid as soon as you leave the while(p) loop. — Gerhardh
– Gerhardh, Commented Oct 17, 2024 at 10:10
There is a fundamental misunderstanding of C concepts here. Look at the malloc call, malloc(n*sizeof(struct edge)). Do you see the name n_list anywhere in there? It is not. Since malloc is not passed the name that its return value will be assigned to, there is no way it could make any decision based on the name. — Eric Postpischil
– Eric Postpischil, Commented Oct 17, 2024 at 12:49

JeremyP · Accepted Answer · 2024-10-17 10:49:11Z

4

Here's your problem

    list[n-p]=&n_list;
    //        ^ address of

That puts the address of n_list into list[n-p]. This will be an address on the stack - the location of n_list and it won't change while n_list is in scope during the loop iteration. It will almost certainly have the same address on the stack on each iteration.

The elements of list are of type struct edge** but you should be putting items in them of type struct edge*. You have too much indirection. Fortunately, you also dereference the pointer to do the printing out before the end of the iteration and n_list is malloc'd for the next time around.

    struct edge* ptr=*list[n-p];
    //               ^ dereference

To fix this, declare list as follows

struct edge* list[n];

And remove the "address of"/dereferencing

    list[n-p] = n_list;
    struct edge* ptr = list[n-p];

Edit

Just realised that the suggestion above isn't completely correct because you realloc each element of list to be only as large as needed. This is problematic because you can't tell how many edges are in each list[i]. You need to either

store the count along with the n_list
have a fixed size for each element of list (don't do the realloc) and use some "doesn't exist" value for the unused ones. It might be enough to set the weightings to 0.

edited Oct 17, 2024 at 10:49

answered Oct 17, 2024 at 10:34

JeremyP

87.4k15 gold badges129 silver badges164 bronze badges

Sign up to request clarification or add additional context in comments.

4 Comments

Gerhardh Over a year ago

Shouldn't n_list[i].v==-1 do the trick to detect the end?

Jennie Over a year ago

Ok I get it now, n_list is already a pointer to the list of a node, so we simply need to say list[n-p]=n_list to store the address of the first edge of that node's list. But "the location of n_list and it won't change while n_list is in scope during the loop iteration.", what you' re saying here is that even when we declare n_list pointer again in the start of the next iteration, malloc allocated space for the pointer in the same location?

JeremyP Over a year ago

@Jennie No. n_list is a local variable (automatic in C terminology) which holds the address of the first struct edge that you malloc'd. If you take n_list's address &n_list you will get a location on the stack where its value is stored. This won't change until it goes out of scope.

Jennie Over a year ago

It won't change even if we declare n_list again (like we do in the next iteration of the while loop)?

Collectives™ on Stack Overflow

Does malloc assign memory in the same location if you use the same variable name again on every iteration of a loop?

1 Answer 1

4 Comments

Your Answer

Hot Network Questions

Collectives™ on Stack Overflow

1 Answer 1

4 Comments

Your Answer

Sign up or log in

Post as a guest

Related