Memory write exception when creating a graph

Question

I am working on a program on C++ that's dealing with graphs.

I store graph as an adjacency list of nodes, and I have the corresponding structures declared in .h file as follows:

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

typedef struct Graph {
    int v;
    node ** arr;
    node ** arr2; // reserved list for a reversed directed graph.
} graph;

I have a function for initializing a graph defined as follows:

graph * creategraph(int v) { // v == number of vertices
    int i;
    graph * temp = (graph*)malloc(sizeof(graph));
    temp->v = v;
    for(i = 0; i < v; i++) {
        temp->arr = (node**)malloc(v*sizeof(node*));
    }
    for(i = 0; i < v; i++) {
        temp->arr[i] = NULL;
    }
    return temp;
}

I call the function as shown below to create a graph with number of vertices being equal to num_vertices:

graph * g = creategraph (num_vertices);

With num_vertices being equal to 200000, the "Access Violation Writing Location" exception is raised in graph * createGraph on the first execution of temp->arr[i] = NULL;.

Could anyone tell me what's the problem here? Thank you.

Please provide more details. I tried your code and it runs with no problem even with num_vertices = 999999 (though the app consumed around 10 Gb of RAM). How much RAM do you have? Maybe you run out of ram? Also, you need to check what malloc returns (if 0 is returned then the memory is not allocated and you must stop your loops). — Phantom Lord, Nov 04 '17 at 15:26

score 3 · Answer 1 · 2017-11-04T16:08:59.930

3

The problem is that you're needlessly allocating temp->arr v times, and leaking all of the previous allocations, so you use v times as much memory as you need to. You only need to allocate it once, so get rid of the loop.

Don't cast the return value of malloc(), while you're at it.

edited Nov 04 '17 at 16:08

answered Nov 04 '17 at 15:27

klutt · Accepted Answer · 2017-11-04T16:12:37.403

3

Here is a big problem:

for(i = 0; i < v; i++) {
    temp->arr = (node**)malloc(v*sizeof(node*));
}

This allocates space for v nodes, but you only have a pointer to the last one you allocated. This is a memory leak. What you need to do is this:

temp->arr = (node**)malloc(v*sizeof(*temp->arr));
for(i = 0; i < v; i++) {
    temp->arr[v] = (node*)malloc(sizeof(*temp->arr[0]));
}

Explanation:

arr is pointer to pointer to Node. First we need to allocate memory for v pointers. Then we need to allocate memory for a Node for each of these pointers.

Also note that it is unnecessary (and therefore bad) to cast malloc in C. If you're coding C++ it is necessary, so if you code "C" but are using a C++ compiler, you will need to cast the result.

Sidenote:

It's good practice to write int arr = malloc(n*sizeof(*arr)) or int arr = malloc(n*sizeof(arr[0])) instead of int arr = malloc(n*sizeof(int)). The reason is that if you in the future decides that you want to use long instead of int you will not have to change it on more than one place.

edited Nov 04 '17 at 16:12

answered Nov 04 '17 at 15:36

klutt

30,332
17
55
95

Minor detail: `temp->arr = malloc(v*sizeof(temp->arr));` -->> `temp->arr = malloc(v * sizeof *temp->arr);` (you could argue that a pointer has the same size as a pointer to pointer, but still...) – wildplasser Nov 04 '17 at 15:41
@klutt @Martin if I try to remove casting than it won't compile saying that it can not assign `void*` to node (or `graph*`)... – Indie_Cube Nov 04 '17 at 15:44
1

In that case you're compiling C as C++. – Nov 04 '17 at 15:45
@Indie_Cube Then compile it with a C compiler instead of C++. But since you seem to code for C++ I'll change the answer. – klutt Nov 04 '17 at 15:47
@klutt I dont think you should rewrite the answer. I think we should rollback thequestion to its original version instead. – wildplasser Nov 04 '17 at 15:56
@wildplasser I'm not 100% sure what I think. But it's obvious that OP THOUGHT he coded C and used a C compiler, which was not the case. – klutt Nov 04 '17 at 15:58
Plus, in the C++ case one should not use malloc/free, but new/delete, IIRC. (but that *could* be a matter of style...) – wildplasser Nov 04 '17 at 16:01
@klutt the correction is fine, you can leave it. It is working on my PC now. However, when I evaluate the code online in GCC compiler, on some tests it gives out a segmentation error. How's that possible? – Indie_Cube Nov 04 '17 at 16:21
@Indie_Cube Could be a million reasons. I recommend posting a new question about that. However, remember to provide a [Minimal, Complete, and Verifiable example](https://stackoverflow.com/help/mcve) – klutt Nov 04 '17 at 16:27

Memory write exception when creating a graph

2 Answers2