How to store and remove dynamically and automatic variable of generic data type in custum list data structure?

Question

Hi

I have created a List data structure implementation for generic data type with each node declared as following.

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

So each node in my list will have pointer to the actual data(generic could be anything) item that should be stored in the list. I have following signature for adding a node to the list

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

the problem is when i want to remove a node i want to free even the data block pointed by *data pointer inside the node structure that is going to be freed. at first freeing of datablock seems to be straight forward

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

But if data is pointing to a block created by malloc then the above call is fine....and we can free that block using free function

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

what if a node is created as following

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

Here we cannot call free on variable x!!!!

How do i know or implement the functionality for both dynamically allocated variables and static ones....that are passed to my list....

Thanks in advance...

The complete implementation is as following list.h simply contains function prototypes.

#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

Well, the typical rule of thumb is that the allocator of heap space shall always also be the one who frees it. Things always start to get messy when it is not well defined which program module 'owns' the allocation.

In your example a clean implementation of the list would never delete the data itself, or would create a copy of the data on insertion such that the data truly belongs to the list. For this, also the size of the data has to be passed.

A good compromise that avoids unnecessary copies may be that the list always frees the data itself but on insertion the user can choose that no copy occurs. For this, he could pass size values of 0 or -1 to indicate that no copy is needed, as the data is already on the heap and will not be managed (freed) by sombody else.

Answer 2

If you are using such snippet

int x = 10;
AddNode(list, (void *)&x);

inside another function, where x is declared auto variable on stack, the code may not behave as you would expect. The pointer is generated from stack address and it's not guaranteed to hold that value of x when the function returns. The pointer you saved in the list will now point to some other data on the stack frame.

For clean implementation of a generic list, you should use dynamically allocated memory or global data which is not stored on stack. Your code will work for global or static variables but not for automatic variables.

Answer 3

There is no automatic way to know whether a pointer can be freed or not. If the logic of your program does not make it obvious, you are going to need a helper variable:

struct Node
{
  void *data;
  int data_on_heap;  // on heap, so should be freed
  ....
  ....
};

You'll need to modify your AddNode function to take that info:

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

int x2 = 10;
AddNode(list, &x2, 0);

And when you want to free it, you'll have to check:

if (n->data_on_heap)
    free(n->data);

Answer 4

Modify the AddNode function to always make a copy of the data passed to it, and free the data when you want to delete the node.