c - 如何在自定义列表数据结构中动态存储和删除通用数据类型的自动变量？

Question

我已经为通用数据类型创建了一个列表数据结构实现，每个节点声明如下。

struct Node
{
  void *data;
  ....
  ....
}

因此我列表中的每个节点都将指向应存储在列表中的实际数据(通用可以是任何内容)项。我有以下用于将节点添加到列表的签名

AddNode(struct List *list, void* eledata);

问题是，当我想删除一个节点时，我什至要释放节点结构中 *data 指针指向的数据 block ，该数据 block 将被释放。起初释放数据 block 似乎很简单

free(data) // forget about the syntax.....

但是如果数据指向一个由 malloc 创建的 block ，那么上面的调用就没问题....我们可以使用 free 函数释放那个 block

 int *x = (int*) malloc(sizeof(int));
 *x = 10;
  AddNode(list,(void*)x); // x can be freed as it was created using malloc

如果如下创建节点会怎样

  int x = 10;
  AddNode(list,(void*)&x); // x cannot be freed as it was not created using malloc

这里我们不能在变量 x 上调用 free!!!!

我如何知道或实现动态分配变量和静态变量的功能....传递到我的列表....

提前致谢...

完整的实现如下 list.h 只包含函数原型(prototype)。

#include<stdio.h>
#include<stdlib.h>
#include<string.h>
#include<assert.h>
#include "list.h"

//structure of each node
static struct Node{
    void *Data;
    struct Node * Next;
    struct Node * Prev;
};
//complete list interface
struct List{
    int Size;
    struct Node DummyNode;  //dummy node
    void (*Print)(void *Data);
};

//create new List
struct List * CreateList(void(*Print)(void* Data)){
    struct List *newList = (struct List *)malloc(sizeof(struct List));
    if(newList != NULL){
        newList->DummyNode.Data = NULL;
        newList->DummyNode.Next = newList->DummyNode.Prev = &newList->DummyNode;
        newList->Size = 0;
        newList->Print = NULL;

        if(Print != NULL) newList->Print = Print; // hook to user provided print function
        return newList;
    }
    return NULL;
}

//Node *ptr point to one node before the actual node to be removed
static void _RemoveNode(struct List *list, struct Node *ptr)
{
    struct Node *temp = ptr->Next; //catch hold of node that is to be removed
    ptr->Next = temp->Next; // link previous node's next pointer with the temp node next pointer
    temp->Next->Prev = ptr; // link next node's previous pointer with previous node pointer

    temp->Prev = NULL; // unlink from previous node
    temp->Next = NULL; // unlink from next node

    free(temp->Data);  // free the data ............ !!! need to mode generic before cleaning the resource
    free(temp);        // remove the node itself.

    list->Size--;
}
void RemoveNodeAt(struct List *list,int nodeIndex)
{
    if( list->Size > 0 && (nodeIndex >= 0 && nodeIndex < list->Size)){
        int i=-1; // meaning we are at dummy node
        struct Node *ptr = NULL;
        for(ptr = &list->DummyNode ;i < nodeIndex - 1 ;i++) // traverse up to one node before the actual node
            ptr = ptr->Next;
        _RemoveNode(list,ptr);
    }
}

//Node *ptr point to one node before the actual node to be removed
static void _AddNode(struct List *list, struct Node *ptr,void *data)
{
    //create New Node
    struct Node *newNode = (struct Node*)malloc(sizeof(struct Node));
    if(newNode != NULL){
        newNode->Data = data;

        //shift node at index to right
        newNode->Next = ptr->Next; 
        newNode->Prev = ptr; 
        ptr->Next = newNode;
        newNode->Next->Prev = newNode;

        list->Size++;
    }
}
void AddNodeAt(struct List *list,int nodeIndex,void *data)
{
    //A node can be added just before head and just after tail.
    if( nodeIndex >= 0  && nodeIndex <= list->Size){
        int i=-1; // meaning we are at dummy node
        struct Node *ptr = NULL;
        for(ptr = &list->DummyNode ;i < nodeIndex - 1 ;i++) // traverse up to one node before the actual node
            ptr = ptr->Next;
        _AddNode(list,ptr,data);
    }
}

void RemoveNode(struct List *list)
{
    if(list->Size > 0){  //check if the list is not empty
        struct Node * temp = list->DummyNode.Prev; //catch hold of last node
        temp->Prev->Next = temp->Next;   //establish previous node's next pointer to temp node next pointer
        temp->Next->Prev = temp->Prev;   //establish next node's previous pointer to temp node previous pointer

        temp->Next = NULL; // unlink temp node from next node
        temp->Prev = NULL; // unlink temp node from previous node

        free(temp->Data);  // free the data ............ !!! need to mode generic before cleaning the resource
        free(temp);        // remove the node itself.

        list->Size--;
    }
}
void AddNode(struct List *list,void *data)
{
    struct Node *ptr = list->DummyNode.Prev;

    //create New Node
    struct Node *newNode = (struct Node*)malloc(sizeof(struct Node));
    if(newNode != NULL){
        newNode->Data = data;

        //shift node at index to right
        newNode->Next = ptr->Next; 
        newNode->Prev = ptr; 
        ptr->Next = newNode;
        newNode->Next->Prev = newNode;

        list->Size++;
    }
}
void DeleteAllNodes(struct List *list)
{
    struct Node *ptr = &list->DummyNode;
    while(list->Size > 0){
        _RemoveNode(list,ptr);
        ptr = ptr->Next;
    }
}

void Display(struct List *list)
{
    if(list->Print != NULL){  //If conusmer doesnot provide a print function just give up printing process.
        int i=0;
        struct Node *ptr = &list->DummyNode;
        for(i = 0; i < list->Size; i++){
            ptr = ptr->Next;
            list->Print(ptr->Data);  // let the consumer of the list data structure print the way he wants
        }
    }
}

// must be used before inserting automatic variables are passed in to the list
// because freeing a automatic variable with free function is a crime....!!!! *(~_~)*
// So i want you to create clones of the automatic variables and pass those variables.
//  AddNode(list,Clone(&i,sizeof(i)));
void * Clone(void *data, int size)
{
    void * clone = malloc(size);
    memcpy(clone,data,size);
    return clone;
}

Answer 1

好吧，典型的经验法则是堆空间的分配者也应该总是释放它的人。当没有明确定义哪个程序模块“拥有”分配时，事情总是开始变得困惑。

在您的示例中，列表的干净实现永远不会删除数据本身，或会在插入时创建数据的副本，以便数据真正属于列表。为此，还必须传递数据的大小。

避免不必要的复制的一个很好的折衷方案可能是列表总是释放数据本身，但在插入时用户可以选择不发生复制。为此，他可以传递 0 或 -1 的大小值以指示不需要副本，因为数据已经在堆上并且不会被其他人管理(释放)。