freeing memory in Circular Doubly Linked List

Question

valgrind tells me that I have XX bytes in XX blocks that are definitely lost record blah blah

and the source is in malloc, however, I think it's because I am not freeing up enough memory for malloc. Anyway, i have provided the code that I believe is causing the heap error.

I am aware that I am not freeing up the memory in list_remove, which I am pretty sure is the only source of the problem. It probably requires some shifting around of temps, but I don't know if that is the only problem.

list_t *list_remove(list_t *list, list_t *node) {
    list_t *oldnode = node;
    node->prev->next = node->next;
    node->next->prev = node->prev;
    if (list != oldnode) {
        free(oldnode);
        return list;
    } else {
         list_t *value = list->next == list ? NULL : list->next;
     free(oldnode);
        return value;
    }
}

void list_free(list_t *list) {
    if (list) {
       while (list_remove(list, list_last(list)) != NULL) {}
    } 
}

list last simply gives the last node of the list.

EDIT: I am sorry about not providing enough information, Kerrek SB, alk. Here is the rest of the code, as you can see the malloc occurs in newnode, where I can start creating new lists. the struct is pretty simple, with a value and a prev, next:

#include <stdlib.h>
#include <string.h>
#include <stdio.h>
#include "ll.h"

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)+1);
    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) {
    list_t *oldnode = node;
    node->prev->next = node->next;
    node->next->prev = node->prev;
    if (list != oldnode) {
        free(oldnode);
        return list;
    } else {
         list_t *value = list->next == list ? NULL : list->next;
     free(oldnode);
        return value;
    }
}

void list_free(list_t *list) {
    if (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));
    }
}

Please help! It still gives me a memory leak error in the heap...

Answer 1

If you're concerned with list_free() I suggest you harden the deletion chain at the source The following assumes, when all is finished, that you want *list to be NULL (because the entire list was just deleted).

void list_free(list_t **list) 
{
    if (list && *list)
    {
        list_t* next = (*list)->next;
        while (next && (next != *list))
        {
            list_t *tmp = next;
            next = next->next;
            free(tmp);
        }

        free(*list);
        *list = NULL;
    }
}

Or something like that. Invoked by passing the address of your outer list pointer:

list_t *list = NULL;

.. initialize and use your list...

// free the list
list_free(&list);

---

EDIT After the OP posted more code, a couple of things are glaring.

1. list_newnode() does NOT set the values of prev and next so they contain garbage.
2. Every other function here assumes (1) initialized next and prev correctly. Frankly I'm surprised this doesn't fault on inception of the second add.

Circular list insertion must assume that the new node being inserted can be the initial list itself. It appears you're making this effort much harder than it needs to be. Remember, a circular list can have any node as the list head, and this is demonstrated no better than when the current list 'head' is deleted. There must be a mechanism in place to reestablish to the caller the new list 'head' when this happens. This same mechanism must allow for the list head to be set to NULL when the last node is removed.

Your code appears to make overt attempts to doing this without using pointers to pointers, and yet they make the task of a circular linked list so much easier. Other things ov note in your code:

• Most of your functions seem to attempt to suggest to the caller what the list-head should be by return value. Rather, they should enforce it by in/out param.
• Any function that inserts a new node relative to another should return the new node.
• The list_prepend() and list_append() functions should be considered the core insertion functions relative to a list-head. The other apis (list_insert_before(), list_insert_after(), etc.) should be entirely relative to the valid existing node to which you're either inserting before or after, and as I said above, return a pointer to the new inserted node always. You will see that both of the non-root-based inserter functions no longer pass the list head.
• Most of your utility functions were correct, save for not checking for invalid pointers prior to performing dereferences. There are still some that don't, but it is at least manageable now.

The following is a code bed built around most of your functions. The actual node-placement routines, were done over and I commented them as best I could. The main test jig is pretty simple. If there are major bugs in here I'm sure the SO-watchtower will quickly point them out, but the point of the code isn't to just fix yours; its a learning thing:

#include <stdio.h>
#include <stdlib.h>
#include <memory.h>
#include <string.h>
#include <assert.h>

// node structure
typedef struct list_t {
    char *value;
    struct list_t *next;
    struct list_t *prev;
} list_t;

static void failed_allocation(void) {
    fprintf(stderr, "Out of memory.\n");
    abort();
}


// initialize a linked list header pointer. Just sets it to NULL.
void list_init(list_t** listpp)
{
    if (listpp)
        *listpp = NULL;
}

// return the value-field of a valid list node.
// otherwise return NULL if node is NULL.
const char *list_node_value(list_t *node)
{
    return (node ? node->value : NULL);
}

// return the next pointer (which may be a self-reference)
//  of a valid list_t pointer.
list_t *list_next(list_t *node)
{
    return (node ? node->next : NULL);
}

// return the previous pointer (which may be a self-reference)
//  of a valid list_t pointer.
list_t *list_previous(list_t *node)
{
    return (node ? node->prev : NULL);
}


// return the same pointer we were passed.
list_t *list_first(list_t *headp)
{
    return headp;
}

// return the previous pointer (which may be a self-reference)
//  of the given list-head pointer.
list_t *list_last(list_t *headp)
{
    return list_previous(headp);
}

// insert a new item at the end of the list, which means it
//  becomes the item previous to the head pointer. this handles
//  the case of an initially empty list, which creates the first
//  node that is self-referencing.
list_t *list_append(list_t **headpp, const char* value)
{
    if (!headpp) // error. must pass the address of a list_t ptr.
        return NULL;

    // allocate a new node.
    list_t* p = malloc(sizeof(*p));
    if (p == NULL)
        failed_allocation();

    // setup duplicate value
    p->value = (value) ? strdup(value) : NULL;

    // insert the node into the list. note that this
    //  works even when the head pointer is an initial
    //  self-referencing node.
    if (*headpp)
    {
        (*headpp)->prev->next = p;
        p->prev = (*headpp)->prev;
        p->next  = (*headpp);
        (*headpp)->prev = p;
    }
    else
    {   // no prior list. we're it. self-reference
        *headpp = p;
        p->next = p->prev = p;
    }
    return p;
}


// insert a new value into the list, returns a pointer to the
//  node allocated to hold the value. this will ALWAYS update
//  the given head pointer, since the new node is being prepended
//  to the list and by-definition becomes the new head.
list_t *list_prepend(list_t **headpp, const char* value)
{
    list_append(headpp, value);
    if (!(headpp && *headpp))
        return NULL;
    *headpp = (*headpp)->prev;
    return *headpp;
}


// insert a new node previous to the given valid node pointer.
// returns a pointer to the inserted node, or NULL on error.
list_t *list_insert_before(list_t* node, const char* value)
{
    // node *must* be a valid list_t pointer.
    if (!node)
        return NULL;
    list_prepend(&node, value);
    return node;
}


// insert a new node after the given valid node pointer.
// returns a pointer to the inserted node, or NULL on error.
list_t *list_insert_after(list_t* node, const char* value)
{
    // node *must* be a valid list_t pointer.
    if (!node)
        return NULL;
    node = node->next;
    list_prepend(&node, value);
    return node;
}


// delete a node referenced by the node pointer parameter.
//  this *can* be the root pointer, which means the root
//  must be set to the next item in the list before return.
int list_remove(list_t** headpp, list_t* node)
{
    // no list, empty list, or no node all return immediately.
    if (!(headpp && *headpp && node))
        return 1;

    // validate the node is in *this* list. it may seem odd, but
    //  we cannot just free it if the node may be in a *different*
    //  list, as it could be the other list's head-ptr.
    if (*headpp != node)
    {
        list_t *p = (*headpp)->next;
        while (p != node && p != *headpp)
            p = p->next;
        if (p == *headpp)
            return 1;
    }

    // isolate the node pointer by connecting surrounding links.
    node->next->prev = node->prev;
    node->prev->next = node->next;

    // move the head pointer if it is the same node
    if (*headpp ==  node)
        *headpp = (node != node->next) ? node->next : NULL;

    // finally we can delete the node.
    free(node->value);
    free(node);
    return 0;
}


// release the entire list. the list pointer will be reset to
//  NULL when this is finished.
void list_free(list_t **headpp)
{
    if (!(headpp && *headpp))
        return;
    while (*headpp)
        list_remove(headpp, *headpp);
}


// enumerate the list starting at the given node.
void list_foreach(list_t *listp, void (*function)(const char*))
{
    if (listp)
    {
        list_t *cur = listp;
        do {
            function(cur->value);
            cur = cur->next;
        } while (cur != listp);
    }
    printf("\n");
}

// printer callback
void print_str(const char* value)
{
    printf("%s\n", value);
}

// main entrypoint
int main(int argc, char *argv[])
{
    list_t *listp;
    list_init(&listp);

    // insert some new entries
    list_t* hello =   list_append(&listp, "Hello, Bedrock!!");
    assert(NULL != hello);
    assert(listp == hello);

    // insert Fred prior to hello. does not change the list head.
    list_t* fred = list_insert_before(hello, "Fred Flintstone");
    assert(NULL != fred);
    assert(listp == hello);
    // Hello, Bedrock!!
    // Fred Flintstone
    list_foreach(listp, print_str);

    // insert Wilma priot to Fred. does not change the list head.
    list_t* wilma = list_insert_before(fred, "Wilma Flintstone");
    assert(NULL != wilma);
    assert(list_next(wilma) == fred);
    assert(list_previous(wilma) == hello);
    // Hello, Bedrock!!
    // Wilma Flintstone
    // Fred Flintstone
    list_foreach(listp, print_str);

    list_t* barney =  list_prepend(&listp, "Barney Rubble");
    list_t* dino =    list_insert_after(wilma, "Dino");
    assert(barney != NULL);
    assert(dino != NULL);
    assert(listp == barney);
    assert(list_previous(barney) == fred);
    assert(list_next(barney) == hello);
    // Barney Rubble
    // Hello, Bedrock!!
    // Wilma Flintstone
    // Dino
    // Fred Flintstone
    list_foreach(listp, print_str);

    // remove everyone, one at a time.
    list_remove(&listp, fred);   // will not relocate the list head.
    // Barney Rubble
    // Hello, Bedrock!!
    // Wilma Flintstone
    // Dino
    list_foreach(listp, print_str);

    list_remove(&listp, hello);  // will not relocate the list head.
    // Barney Rubble
    // Wilma Flintstone
    // Dino
    list_foreach(listp, print_str);

    list_remove(&listp, barney); // will relocate the list head.
    // Wilma Flintstone
    // Dino
    list_foreach(listp, print_str);
    assert(listp == wilma);
    assert(list_next(wilma) == dino);
    assert(list_previous(listp) == dino);

    list_remove(&listp, wilma);  // will relocate the list head.
    // Dino
    list_foreach(listp, print_str);

    list_remove(&listp, dino);   // will relocate the list head;

    // generate a raft entries (a million of them)/
    char number[32];
    int i=0;
    for (;i<1000000; i++)
    {
        sprintf(number, "%d", i);
        list_append(&listp, number);
    }

    // now test freeing the entire list.
    list_free(&listp);

    return 0;
}

The sprinkling if asserts and dumps are to assist in validating algorithm soundness. The resulting output for this, which should match the comments in the code, is:

Hello, Bedrock!!
Fred Flintstone

Hello, Bedrock!!
Wilma Flintstone
Fred Flintstone

Barney Rubble
Hello, Bedrock!!
Wilma Flintstone
Dino
Fred Flintstone

Barney Rubble
Hello, Bedrock!!
Wilma Flintstone
Dino

Barney Rubble
Wilma Flintstone
Dino

Wilma Flintstone
Dino

Dino

Final Thoughts: I've run this through valgrind and found no leaks. I'm positive it will not drop-in fit into your needs.** Most of it will (half of it is already there).