Calling free() on unknown data

I‘m writing a linked list in C and I‘m using a void* for the data.
The problem is that the void* could point to memory that was allocated by a user with malloc or to statically allocated memory (just a variable that was declared).
Now when I delete a Node I can’t tell if I have to call free() to free the allocated memory by the user or if I don’t have to call free() because the program would crash otherwise.

Is there a solution to this problem?

There is a snippet of my linked list code:

typedef struct Node{
	struct Node* next;
        void* data;
} Node;
	
typedef struct List{
	struct Node* head;
	struct Node* tail;
} List;

Node* lst_add(List* list, Node* insertPos, void* data){
	Node* newNode = (Node*)malloc(sizeof(Node));
	if (newNode == NULL) return NULL;
	
	newNode->data = data;
	newNode->next = NULL;
		
	if (insertPos != NULL){
		Node* tmp = insertPos->next;
		insertPos->next = newNode;
		newNode->next = tmp;
		return newNode;
	}

	if (list->head == NULL){
		list->head = newNode;
		list->tail = newNode;
		return newNode;	
	}

	list->tail->next = newNode;
	list->tail = newNode;
	return newNode;
}

Node* lst_delete(List* list, Node* n){
	if (n == NULL || list->head == NULL) return NULL;
	
	if (n == list->head){
		Node* tmp = list->head;
		list->head = list->head->next;
		free(tmp->data); /* programm crahes here if tmp->data was not allocated with malloc */
		free(tmp);
		return tmp;
	}	
	
	Node* current = list->head;
	Node* prev = current;
	
	while (current != NULL){
		if (current == n){
			prev->next = current->next;
			free(current->data);               /* programm crahes here if current->data was not allocated with malloc */
			free(current);
			return current;
		}
		prev = current;
		current = current->next;
	}
	return NULL;
}

I want to be able to do this:

int i = 5;
lst_add(pointer_to_list, pointer_to_insert_position, &i) // &i -> void*

... and this:

int* i = (int*)malloc(sizeof(int));
*i = 5;
lst_add(pointer_to_list, pointer_to_insert_position, i) // i -> void*

Thanks for your help in advance!

If I call free() in both cases my program crashes and if I don’t call free() at all I have memory leaks in some cases.

> Is there a solution to this problem?

You must design your program so that it knows whether or not it should pass the address to free.

One way to do this is not to put any statically allocated memory into your data structure. If you have static data you want to include in the structure, you can, during initialization of the data structure, copy the data into dynamically allocated memory and put that into the structure. That way, all items in the data structure use dynamically allocated memory, so it may always be freed.

Another way to do satisfy the design requirement is to tag each item in the structure with a flag indicating whether it was dynamically allocated or not.

Additional alternatives could be:

• Compare the address of the data potentially to be freed to the address or addresses of known static data.
• Design your algorithms so that the statically allocated data is never removed from your data structure.

That's a nice question. Indeed, there is no way (within the C standard and by avoiding hideous hacks) to be able to handle invalid free() calls.

A proper generic way of defining your data structure would be to have the client code create and pass a function pointer that handles the destruction/freeing.

That function is to be called instead of free() with the data item passed as argument. Depending on what the data type is, that function may call free() or do nothing.

That means that the user of the code will have to create one "destructor" function for each date type they want to store (or rather, each set of types that are destroyed the same way).

There are some considerations on where to pass/save this function pointer. Namely:

1. Save the function pointer inside your list struct. lst_delete() will be calling list->destruction_function(data) instead of free. Pros: This requires the user code to pass that function only ones at the creation of the list which is very clean. Cons: The list can save only a single data type (or rather, data types that are destroyed the same way).
2. Make your lst_delete() function accept a pointer to the destruction function as an argument - i.e. Node* lst_delete(List* list, Node* n, void (*destruction_function)(void *)); and use that. Pros: Each item can be of different type, since the destruction function can be different. Cons: The user must know what type of data each specific node stores in order to pass the appropriate destruction function.
3. Pass the destruction function in lst_add(...) as a pointer and save that pointer within the Node struct alongside the data. Therefore, lst_delete() has the information within argument n of which destruction function to call. Pros: This is the most generic way as it can handle different types of data within the same struct and there is no need of the user "remembering" their type information when deletion happens. Cons: More effort to implement.

Implementation of approach #2 from above:

Node* lst_delete(List* list, Node* n, void (*destruction_function)(void *)){
    if (n == NULL || list->head == NULL) return NULL;
    
    if (n == list->head){
        Node* tmp = list->head;
        list->head = list->head->next;
        destruction_function(tmp->data); /* programm crahes here if tmp->data was not allocated with malloc */
        free(tmp);
        return tmp;
    }   
    
    Node* current = list->head;
    Node* prev = current;
    
    while (current != NULL){
        if (current == n){
            prev->next = current->next;
            destruction_function(current->data);   /* change here */
            free(current);
            return current;
        }
        prev = current;
        current = current->next;
    }
    return NULL;
}

// ----- "client code from now on" -----

void do_nothing(void *x){
   ;
}

void free_a_pointer(void *x){
  free(x);
}


int i = 5;
lst_add(pointer_to_list, pointer_to_insert_position, &i);
lst_delete(pointer_to_list, pointer_to_delete_position, do_nothing);



int* i = (int*)malloc(sizeof(int));
*i = 5;
lst_add(pointer_to_list, pointer_to_insert_position, i);
lst_delete(pointer_to_list, pointer_to_delete_position, free_a_pointer);

A Note on deleting void * data items on structures:
Even if you are storing pointer and free() can be called without error, this is still not the best way to do it!

1. It is perfectly normal for the client code to pass pointer to data items that cannot be cleared by a simple free operation (e.g. a dynamic pointer to a struct who has internal pointers to allocated memory, such as strings). Calling free on such data creates memory leaks.
2. The user might like to have the data available even after deletion from your data structure. E.g. some structs like binary search trees are built as fast search structures for your data, so it makes sense to store only pointers to that data and keep them even if they are removed from the index. A struct that imposes deletion every time is a bit more restrictive.

For those reasons, the destruction function is indeed the way to go.