Segmentation fault in double linked list in C

Question

This has been driving me crazy. When I run my test program on this doubly linked list it gives me a Segmentation fault when I try and free my list. I know there is a memory leak due to not freeing the allocated memory correctly but no matter what I try it doesn't seem to fix it. Any help as to where I need free the memory to avoid a memory leak and the seg fault would be appreciated

struct list { 

    char *value;
    struct list *next;
    struct list *prev;
};

const char *list_node_value(list_t *node) {

    return node->value;
}

list_t *list_first(list_t *list) {

    return list;
}

list_t *list_last(list_t *list) {

    return list->prev;
}

list_t *list_next(list_t *node) {

    return node->next;
}

list_t *list_previous(list_t *node) {

    return node->prev;

}

static void failed_allocation(void) {

    fprintf(stderr, "Out of memory.\n");
    abort();
}

static list_t *new_node(const char *value) {

    list_t *node = malloc(sizeof(list_t));
    if (!node) failed_allocation();
    node->value = malloc(strlen(value));
    if (!node->value) failed_allocation();
    strcpy(node->value, value);
    return node;
}

list_t *list_insert_before(list_t *list, list_t *node, const char *value) {

    list_t *insert_node = new_node(value);
    insert_node->prev = node->prev;
    insert_node->next = node;
    insert_node->next->prev = insert_node;
    insert_node->prev->next = insert_node;
    if (list == node) {
        return insert_node;
    } else {
        return list;
    }
}

list_t *list_append(list_t *list, const char *value) {

    if (list) {

        (void) list_insert_before(list, list, value);
        return list;
    } else {

        list_t *node = new_node(value);
        node->prev = node->next = node;
        return node;
    }
}

list_t *list_prepend(list_t *list, const char *value) {

    if (list) {

        return list_insert_before(list, list, value);
    } else {

        list_t *node = new_node(value);
        node->prev = node->next = node;
        return node;
    }
}

list_t *list_remove(list_t *list, list_t *node) {

    (node->prev)->next = node->next;
    (node->next)->prev = node->prev;
    if (list != node) {

    return list;
    } else {

        return list->next == list ? NULL : list->next;
    }   
}

void list_free(list_t *list) {

    while (list_remove(list, list_last(list)) != NULL) { }

    }



void list_foreach(list_t *list, void (*function)(const char*)) {

    if (list) {

        list_t *cur = list_first(list);
        do {

            function(cur->value);
            cur = cur->next;
        } while (cur != list_first(list));
    }
}

Serge · Accepted Answer · 2012-09-22 18:09:38Z

1

Your problem is heap corruption. you have:

   node->value = malloc(strlen(value));

it should be:

   node->value = malloc(strlen(value)+1);

answered Sep 22, 2012 at 18:09

Serge

6,09520 silver badges29 bronze badges

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

3 Comments

quantum Over a year ago

You beat me by a few seconds.

quantum Over a year ago

Sorry I didn't ask the question. :)

Serge Over a year ago

@xiaomao sorry, I missed this :)

Scott Hunter · Accepted Answer · 2012-09-22 18:11:01Z

1

You are not freeing anything at all; disconnecting it from the list doesn't free it.
It's not just a doubly-linked list; it is a circular list.
I don't see code to initialize a list, which may be the source of your problem.

answered Sep 22, 2012 at 18:11

Scott Hunter

50k12 gold badges64 silver badges107 bronze badges

Comments

Gung Foo · Accepted Answer · 2012-09-22 18:07:34Z

0

Run your program linked to efence or with valgrind.

This should tell you where memory is lost or pointers dereferenced, etc...

answered Sep 22, 2012 at 18:07

Gung Foo

13.6k5 gold badges35 silver badges39 bronze badges

Comments

quantum · Accepted Answer · 2012-09-22 18:09:53Z

0

if (!node) failed_allocation();
node->value = malloc(strlen(value));

Problem is you didn't allocate space for the '\0' NUL byte. Try:

if (!node) failed_allocation();
node->value = malloc(strlen(value)+1);

answered Sep 22, 2012 at 18:09

quantum

3,8881 gold badge31 silver badges51 bronze badges

Comments

Rost · Accepted Answer · 2012-09-22 18:10:17Z

0

I see at least one defect here:

node->value = malloc(strlen(value));

It shall be strlen(value) + 1 to keep zero terminator char, otherwise next strcpy() call will lead to buffer overrun and can damage heap:

node->value = malloc(strlen(value) + 1);

answered Sep 22, 2012 at 18:10

Rost

9,10932 silver badges55 bronze badges

5 Comments

Scott Hunter Over a year ago

Why would this cause a problem when FREEING the list?

user1691282 Over a year ago

As mentioned I can see where this would cause problems with the memory but how would I go about freeing the list? if I put a free(node) in the list_remove function I just get a seg fault

Rost Over a year ago

@user1691282 Where exactly you put free() call and what cause seg fault after that? free() call ifself? You shall read data from deleted node before freeing it.

Rost Over a year ago

@ScottHunter It could cause problems on free() in case when buffer overrun corrupts the heap

user1691282 Over a year ago

@Rost I am putting the free() such that list_t *list_remove(list_t *list, list_t *node) { (node->prev)->next = node->next; (node->next)->prev = node->prev; if (list != node) { free(node); return list; } else { return list->next == list ? NULL : list->next; } } but I am still not freeing all the memory and Im not sure how to fix it

Collectives™ on Stack Overflow

Segmentation fault in double linked list in C

5 Answers 5

3 Comments

Comments

Comments

Comments

5 Comments

Your Answer

Hot Network Questions

Collectives™ on Stack Overflow

5 Answers 5

3 Comments

Comments

Comments

Comments

5 Comments

Your Answer

Sign up or log in

Post as a guest

Related