CODEWITHSUNDEEP
cmemory-managementvalgrind
Semi
Semi

Reputation: 448

Too many frees when freeing graph

I have created a graph datastructure using linked lists. With this code:

typedef struct vertexNode *vertexPointer;
typedef struct edgeNode *edgePointer;

void freeGraph(vertexPointer); /* announce function */

struct edgeNode{
    vertexPointer connectsTo;
    edgePointer next;
};

struct vertexNode{
    int vertex;
    edgePointer next;
};

Then I create a graph in which I have 4 nodes, lets say A, B, C and D, where: A connects to D via B and A connects to D via C. With linked lists I imagine it looks like this:

what the graph looks like

Finally, I try to free the graph with freeGraph(graph).

void freeEdge(edgePointer e){
    if (e != NULL) {
        freeEdge(e->next);
        freeGraph(e->connectsTo);
        free(e);
        e = NULL;
    }
}

void freeGraph(vertexPointer v){
    if (v != NULL) {
        freeEdge(v->next);
        free(v);
        v = NULL;
    }
}

That's where valgrind starts complaining with "Invalid read of size 4", "Address 0x41fb0d4 is 4 bytes inside a block of size 8 free'd" and "Invalid free()". Also it says it did 8 mallocs and 9 frees.

I think the problem is that the memory for node D is already freed and then I'm trying to free it again. But I don't see any way to do this right without having to alter the datastructure.

What is the best way to prevent these errors and free the graph correctly, if possible without having to alter the datastructure? Also if there are any other problems with this code, please tell. Thanks!

greets, semicolon

Upvotes: 2

Views: 1655

Answers (5)

Sebastian
Sebastian

Reputation: 1889

Instead of allocating the nodes and edges on a global heap, maybe you can allocate them in a memory pool. To free the graph, free the whole pool.

Upvotes: 2

Sebastian
Sebastian

Reputation: 1889

Yes, the problem is that D can be reached over two paths and freed twice.

You can do it in 2 phases: Phase 1: Insert the nodes you reached into a "set" datastructure. Phase 2: free the nodes in the "set" datastructure.

A possible implementation of that set datastructure, which requires extending your datastructure: Mark all nodes in the datastructure with a boolean flag, so you don't insert them twice. Use another "next"-pointer for a second linked list of all the nodes. A simple one.

Another implementation, without extending your datastructure: SOmething like C++ std::set<>

Another problem: Are you sure that all nodes can be reached, when you start from A? To avoid this problem, insert all nodes into the "set" datastructure at creation time (you won't need the marking, then).

Upvotes: 0

Dave Rager
Dave Rager

Reputation: 8160

I would approach this problem by designing a way to first cleanly remove each node from the graph before freeing it. To do this cleanly you will have to figure out what other nodes are referencing the node you are about to delete and remove those edges. Once the edges are removed, if you happen to come around to another node that had previously referenced the deleted node, the edge will already be gone and you won't be able to try to delete it again.

The easiest way would be to modify your data structure to hold a reference to "incoming" edges. That way you could do something like:

v->incoming[i]->next = null; // do this for each edge in incoming
freeEdge(v->next);
free(v);
v = NULL;

If you didn't want to update the data structure you are left with a hard problem of searching your graph for nodes that have edges to the node you want to delete.

Upvotes: 1

Clinton Pierce
Clinton Pierce

Reputation: 13189

It's because you've got two recursions going on here, and they're stepping on each other. freeGraph is called once to free D (say, from B) and then when the initial call to freeGraph comes back from freeEdge, you try freeing v -- which was already taken care of deeper down. That's a poor explanation without an illustration, but there ya go.

You can get rid of one recursions so they're not "crossing over", or you can check before each free to see if that node has already been taken care of by the other branch of the recursion.

Upvotes: 0

WhozCraig
WhozCraig

Reputation: 66244

The lack of knowing all the references makes this a bit difficult. A bit of a hack, but faced with the same issue I would likely use a pointer set (a list of unique values, in this case pointers).

  • Walk the entire graph, pushing nodes pointers into the set only if not already present (this the definition of 'set')
  • Walk the set, freeing each pointer (since they're unique, no issue of a double-free)
  • Set graph to NULL.

I'm sure there is an elegant recursive solution to this, but faced with the task as stated, this seems doable and not overtly complicated.

Upvotes: 2

Related Questions