CODEWITHSUNDEEP
cstructnestedsegmentation-faultfree
naike
naike

Reputation: 33

How to free more complex nested structs

Solution in comments.

typedef struct Vertex {
    int i;
    int color;
} vertex;

typedef struct Edge {
    vertex v1;
    vertex v2;
} edge;

typedef struct Node {
    void *p;
    struct Node *next;
} node;

Basically this is a linked list (of nodes). In my program I know if a node array holds edges or vertices.

I'm not sure how to free a list of edges properly, I've tried the following:

static void freeEdgeList(node *list) {
    if (list == NULL) return;
    node *ptr = list;
    node *tmp;
    do {
        tmp = ptr->next;
        free(&((*((edge *)(ptr->p))).v1));
        free(&((*((edge *)(ptr->p))).v2));
        free(ptr->p);
        free(ptr);
    } while ((ptr = tmp) != NULL);
}

Because my struct Edge doesn't store pointers, is it enough to free the edge struct, without freeing the vertices stored in the edge? I'm a little confused.

Edit:

static int addEdge(edge *e, node **list) {
    if ((*list) == NULL) {
        (*list) = malloc(sizeof(node));
        if ((*list) == NULL) return -1;
        (*list)->p = malloc(sizeof(edge));
        if ((*list)->p == NULL) return -1;
        memcpy(&((*list)->p), &e, sizeof(edge));
        (*list)->next = NULL;
    } else {
        node *tmp = (*list);
        while (tmp->next != NULL) {
            tmp = tmp->next;
        }
        tmp->next = malloc(sizeof(node));
        if (tmp->next == NULL) return -1;
        tmp = tmp->next;
        tmp->p = malloc(sizeof(edge));
        if (tmp->p == NULL) return -1;
        tmp->next = NULL;
        memcpy(&(tmp->p), &e, sizeof(edge));
    }
    return 0;
}

This is the function that adds edges to a list (initially the list passed in is NULL). It seems to add the edges correctly because I can output the list to the console just fine. But if I try to free with:

static void freeEdgeList(node *list) {
    while (list) {
        node *tmp = list;
        list = list->next;
        free(tmp->p);
        free(tmp);
    }
}

I get different error (segfault, invalid pointer)

Upvotes: 0

Views: 3422

Answers (5)

Craig Estey
Craig Estey

Reputation: 33621

As others have mentioned freeEdgeList needs a fix [so follow their responses].

In addEdge, your memcpy calls are incorrect. You are copying to/from the address of a pointer and not what the pointer points to.

You want: memcpy((*list)->p, e, sizeof(edge)) and memcpy(tmp->p, e, sizeof(edge))

Also, in addEdge, if *list == NULL, you don't set it to the first/new element.

Also, the code can be simplified a bit. For example, using *list everywhere is a bit cumbersome.

Here's a refactored version with the memcpy and *list bugs fixed:

static int
addEdge(edge *e, node **list)
{
    node *head = *list;
    node *cur;
    node *prev;
    int ret = -1;

    // find the end of the list
    prev = NULL;
    for (cur = head;  cur != NULL;  cur = cur->next)
        prev = cur;

    do {
        // allocate new node
        cur = malloc(sizeof(node));
        if (cur == NULL)
            break;
        cur->next = NULL;

        // add pointer to new edge
        cur->p = malloc(sizeof(edge));
        if (cur->p == NULL) {
            free(cur);
            break;
        }

        // copy in the edge data
        memcpy(cur->p,e,sizeof(edge);

        // link in new node
        if (prev != NULL)
            prev->next = cur;
        else
            head = cur;

        // adjust list pointer
        *list = head;

        ret = 0;
    } while (0);

    return ret;
}

Upvotes: 0

dbush
dbush

Reputation: 224377

You can only pass to free exactly what was returned from malloc and family. Since you presumably called malloc to allocate a node, you only need to free a node.

Neither vertex nor edge contain fields that are pointers, so there is nothing else to free. All you need to do is:

static void freeEdgeList(node *list) {
    while (list) {
        node *tmp = list;
        list = list->next;
        free(tmp->p);
        free(tmp);
    }
}

EDIT:

In the code where you add an edge, you incorrectly do this:

memcpy(&((*list)->p), &e, sizeof(edge));
...
memcpy(&(tmp->p), &e, sizeof(edge));

Since e is a edge *, what this is doing is copying the pointer value e to the field p instead of what it points to. That results in the edge object pointed to by p having invalid values. You instead want:

memcpy((*list)->p, e, sizeof(edge));
...
memcpy(tmp->p, e, sizeof(edge));

This will copy the values contained in the edge that e points to.

Upvotes: 2

naike
naike

Reputation: 33

Edit: Seems I didn't quite get it yet..

Thanks for your help, many thanks! That makes it clear to me.

while (list) {
    node *tmp = list;
    list = list->next;
    free(&(tmp->p));
    free(tmp);
}

This solution worked, I needed to pass the address of the pointer to free, not the pointer itself, I don't quite understand why though.

Upvotes: 1

Sami Kuhmonen
Sami Kuhmonen

Reputation: 31173

The rule is if you don’t allocate it you don’t free it. The struct Edge doesn’t contain any dynamic memory allocation or pointers, as you said, so you don’t free them yourself. The memory is allocated as part of Edge and be freed when you free it.

So remove the free()s from v1 and v2 and only use free(ptr->p).

Upvotes: 1

Ass3mbler
Ass3mbler

Reputation: 3915

Yes, it's correct. Since you are not malloc()ing the vertex (they aren't pointers, but variables allocated inside the Edge structure) a simple free() for the Edge structure will suffice

Upvotes: 0

Related Questions