Working on simple double linked list.

struct list_node {
   struct list_node *prev, *next;
   int data;
};

struct list {
   struct list_node *first, *last;
};

With creation and pushing as follows:

struct list *list_create(void) {
    struct list *_list = malloc(sizeof(struct list));
    if(_list == NULL) {
        die("Memory allocation error for list_create\n");
    }
    _list->first = NULL;
    _list->last = NULL;
    return _list;
}
void list_push(struct list *list, int item_data) {
    struct list_node *_node = malloc(sizeof(struct list_node));
    if(_node == NULL) {
        die("Memory allocation error for list_push\n");
    }
    _node->prev = NULL;
    _node->next = NULL;
    _node->data = item_data;

    //empty list case
    if(list->last == NULL) {
        list->first = _node;
        list->last = _node;
    }
    else {
        _node->prev = list->last;
        list->last->next = _node;
        list->last = _node;
    }
}

One push works but two successive ones cause memory leak - of size of a node.
What am I missing here?

For a completion here is my free for the list - and I am calling it in my code:

void list_destroy(struct list *list) {
    if (list->first != NULL) {
        struct list_node *p = list->first;
        //if one node list
        if(list->first == list->last) {
            list->first = NULL;
            list->last = NULL;
            free(p);
            p = NULL;
        }
        else {
            while (p->next) {
                struct list_node *q = p;
                p = p->next;
                free(q);
                q = NULL;
            }
        }
    }
    free(list);
}

[SOLVED] Bug was in list_destroy - last time through while(p->next) left last p node not properly handled. Thanks everybody!

CodePudding user response：

The memory leaks are produced by the function list_destroy in this while loop

        while (p->next) {
            struct list_node *q = p;
            p = p->next;
            free(q);
            q = NULL;
        }

The last node of the list is not freed due to the condition of the while loop

        while (p->next) {

because for the last node the data member next is equal to NULL.

There is no sense to split the function into two parts. The function can look the following way

void list_destroy(struct list *list) {
    while ( list->first )
    {
        struct list_node *p = list->first;
        list->first = list->first->next;
        free( p );
    }

    free( list );
}   

It would be better to pass the pointer list by reference through a pointer to it as for example

void list_destroy(struct list **list) {
    struct list_node *current = ( *list )->first;

    while ( current )
    {
        struct list_node *p = current;
        current = current->next;
        free( p );
    }

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

In this case after the function execution the pointer to the list in the caller will be equal to NULL.

Also you could write a function that clears the list. It can look the following way

void list_clear(struct list *list) {
    while ( list->first )
    {
        struct list_node *p = list->first;
        list->first = list->first->next;
        free( p );
    }

    list->last = NULL;
}   

CodePudding user response：

Vlad from Moscow wrote a cleaner version. I'd like to add "defensive programming". It's dangerous to assume create() has been called before push() or destroy(). In fact, you can avoid a tough-to-find bug (using a pointer in the calling code after it's been free()'d.) Always check 'passed-in' arguments.

In the calling code:

myList = list_destroy( myList );

and return something that can be used.

list_t *list_destroy( list_t *pList ) {
    assert( pList != NULL );
    // iterate releasing alloc'd blocks...
    return NULL;
}