C linked list - when to free allocated memory

Question

I have a simple linked list implementation with push, pop, unshift and shift functions to add/remove data as required. I would like to ensure that my implementation is not leaking memory when retrieving data via calls to pop and shift.

How do I go about freeing memory which has been allocated via malloc, while also returning the data to the caller?

list.h

typedef struct _list_cell_t {
    void *data;
    struct _list_cell_t *next;
} list_cell_t;

typedef struct _list_cell_t *list_cell_ptr;

typedef struct {
    int size;
    list_cell_ptr head;
} list_t;

void list_init(list_t *p_list);
void list_free(list_t *p_list);

void list_push(list_t *p_list, void *data);
void list_unshift(list_t *p_list, void *data);

void *list_pop(list_t *p_list);
void *list_shift(list_t *p_list);

---

list.c

#include "list.h"

#include <stdlib.h>
#include <string.h>

void list_init(list_t *p_list)
{
    memset(p_list, 0, sizeof(list_t));

    p_list->head = NULL;
    p_list->size = 0;
}

void list_free(list_t *p_list)
{
    list_cell_ptr p_cell, p_next;

    p_cell = p_list->head;
    while (p_cell != NULL) {
        p_next = p_cell->next;
        memset(p_cell, 0, sizeof(list_cell_t));
        free(p_cell);
        p_cell = p_next;
    }

    memset(p_list, 0, sizeof(list_t));
}

void list_push(list_t *p_list, void *data)
{
    list_cell_ptr *p_curr_ptr, p_tmp;

    p_tmp = (list_cell_ptr)malloc(sizeof(list_cell_t));
    memset(p_tmp, 0, sizeof(list_cell_t));
    p_tmp->data = data;

    p_curr_ptr = &(p_list->head);
    while (*p_curr_ptr != NULL) {
        p_curr_ptr = &((*p_curr_ptr)->next);
    }

    p_tmp->next = NULL;
    *p_curr_ptr = p_tmp;
    p_list->size++;
}

void list_unshift(list_t *p_list, void *data)
{
    list_cell_ptr *p_curr_ptr, p_tmp;

    p_tmp = (list_cell_ptr)malloc(sizeof(list_cell_t));
    memset(p_tmp, 0, sizeof(list_cell_t));
    p_tmp->data = data;

    p_curr_ptr = &(p_list->head);

    p_tmp->next = *p_curr_ptr;
    *p_curr_ptr = p_tmp;
    p_list->size++;
}

void *list_pop(list_t *p_list)
{
    list_cell_ptr *p_curr_ptr = &(p_list->head);

    while ((*p_curr_ptr)->next != NULL) {
        p_curr_ptr = &((*p_curr_ptr)->next);
    }

    void *ret = (*p_curr_ptr)->data;

    *p_curr_ptr = NULL;
    p_list->size--;
    return ret;
}

void *list_shift(list_t *p_list)
{
    void *ret = p_list->head->data;

    list_cell_ptr p_next = p_list->head->next;

    p_list->head = p_next;
    p_list->size--;

    return ret;
}

Answer 1

How do I go about freeing memory which has been allocated via malloc, while also returning the data to the caller?

Overall, the general rule in C memory management is that it must always be clear where the responsibility lies for freeing every piece of dynamically allocated memory, and wherever it does lie, that code must take care to fulfill all such responsibilities without fail. In your case, the only reasonable place to put the responsibility for freeing the struct _list_cell_t objects allocated for a given list is in the code that removes those objects from the list again (the pop, shift, and free functions).

After you free each such object, however, you must not access it again, so you must first store the data pointer you intend to return in a local variable. In fact, you already do this.

There are lots of ways to implement the details, but I suggest this paradigm:

1. Store a pointer to the no-longer-needed struct _list_cell_t in a local variable.
2. Update the structure of the list to cut out that object.
3. Store a pointer to the wanted data in a local variable.
4. Free the unneeded struct _list_cell_t via the pointer recorded in step (1)
5. Return the data