C链表 - 何时释放分配的内存

Question

我有一个简单的链表实现，可以根据需要将 push、pop、unshift 和 shift 函数推送到 add/remove 数据。我想确保我的实现在通过调用 pop 和 shift 检索数据时不会泄漏内存。

如何释放通过 malloc 分配的内存，同时将数据返回给调用者？

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

你可以使用智能指针。

这可以使用 C 中的结构来完成。我在 C 中包含了一个基本示例。它没有实现您拥有的所有功能（只是推送和弹出），但它应该让您了解智能指针。

#include <stdlib.h>

// the client get's a pointer to this struct NOT the listitem
struct data
{
    int ref_count;
    int *data;
};

// this is only used by the main, push and pop functions
struct listitem
{
    struct listitem *next;
    struct data *the_data;
};

// the client will have to use decrement() when it is finished with the data
int decrement(struct data *list_data)
{
    if(list_data->ref_count > 0)
        list_data->ref_count--;
    if (list_data->ref_count == 0 && list_data->data)
    {
        free(list_data->data);
        list_data->data = 0;
        free(list_data);
        return 0;
    }
    return(list_data->ref_count);
}

// the client can use increment() if it passes the data to another variable
struct data *increment(struct data *list_data)
{
    if (list_data)
        list_data->ref_count++;
    return(list_data);
}

void free_list(struct listitem **pp)
{
    while (*pp)
    {
        struct listitem *temp = (*pp)->next;
        decrement((*pp)->the_data);
        free(*pp);
        (*pp) = temp;
    }
}

void push_list(struct listitem **pp, int *data)
{
    struct listitem *temp = (struct listitem *)malloc(sizeof(struct listitem));
    temp->next = (*pp);
    (*pp) = temp;
    temp->the_data = (struct data *)malloc(sizeof(struct data));
    temp->the_data->data = data;
    temp->the_data->ref_count = 1;
}

struct data *pop_list(struct listitem **pp)
{
    if (*pp)
    {
        struct listitem *temp = (*pp)->next;
        struct data *d = (*pp)->the_data;
        free(*pp);
        (*pp) = temp;
        return(d); // the data is not being freed from memory here
    }
    return 0;
}

int main()
{
    struct listitem *list = 0;
    int i;

    for (i = 0; i < 10; i++)
    {
        int *pi = (int*)malloc(sizeof(int));
        (*pi) = rand();
        push_list(&list, (int *)pi);
    }
    struct data *d[5];
    for (i = 0; i < 5; i++)
        d[i] = pop_list(&list);
    free_list(&list); // the linked list has been destroyed now

    // this would be the client code
    struct data *d2 = increment(d[0]);

    struct data *d3 = increment(d[1]);

    // clean up, delete all but d2 and d3
    for (i = 0; i < 5; i++)
        decrement(d[i]);

    // do something with d2(d[0]) and d3(d[1])

    // clean up time
    decrement(d2); // now this data has been deleted
    decrement(d3); // now this data has been deleted

    return 0;
}

确实没有其他方法可以在您的代码和客户端之间共享内存。

Answer 2

在覆盖该值并松开您指向的地址之前，您应该使用您拥有的指针释放内存。您已使用该指针释放内存 space.

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;
    free(*p_curr_ptr); //free memory
    *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;
    free(p_list->head); //use this to free memory
    p_list->head = p_next;
    p_list->size--;

    return ret;
}

希望我回答了你的问题

Answer 3

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

总的来说，C 内存管理的一般规则是，必须始终清楚释放每块动态分配内存的责任在哪里，无论它在哪里，代码都必须注意履行所有这些责任没有失败。在您的情况下，释放为给定列表分配的 struct _list_cell_t 对象的责任的唯一合理位置是再次从列表中删除这些对象的代码（pop、shift，和 free 函数）。

但是，在释放每个这样的对象之后，您不能再次访问它，因此您必须首先将您打算 return 的 data 指针存储在局部变量中。事实上，你已经这样做了。

实现细节的方法有很多，但我建议采用这种范式：

在局部变量中存储指向 no-longer-needed struct _list_cell_t 的指针。
更新列表结构以删除该对象。
在局部变量中存储指向所需数据的指针。
通过步骤(1)中记录的指针释放不需要的struct _list_cell_t
Return数据

C链表 - 何时释放分配的内存

C linked list - when to free allocated memory

c

malloc

free

memory-management

linked-list

list.h

list.c