Hello all,
Thank you in advance for your help and patience. I'm implementing a doubly-linked list in C, and I have some questions about freeing resources. Please forgive me if I get too detailed in my overview. My goal is to be as clear and close to complete as possible in my description.
I will use the confused smile in the sections where I'm describing problems, and I will indent and number actual questions.
I'll start by listing my data structures. First is the node struct, peNode:
Code:
typedef struct peNode__{
void* p_vElem;
struct peNode__* p_Next;
struct peNode__* p_Prev;
} peNode;
Notice that it contains two node pointers that will point to the next and previous list nodes. It also contains a void pointer that will point to the node's data.
The final component of this list data structure is the peList struct:
Code:
typedef struct peList__{
peNode* p_Head;
peNode* p_Tail;
int iSize;
int (*f_Equ)(peNode* p_Node1, peNode* p_Node2);
void (*f_Del)(peNode* p_Node);
}peList;
So far, it has five elements. I will eventually add more and maybe get rid of one based on your input. There are two peNode pointers that will point to the beginning and end nodes in a list. There is an integer field - iSize - that will contain the size of the list.
Finally, there are two function pointers. The first - f_Equ - returns an int and takes two peNode pointers as parameters. This field may be instantiated with a pointer that compares two peNodes to see if they are "equal". The idea is that the equality of two nodes can be determined and defined by the developer.
The second of the two function pointers is f_Del. It returns void and takes a peNode pointer as a parameter. This field may be instantiated with a pointer to a function that deletes a peNode.
I thought that this would be necessary if a developer decided to store a complex data structure in each of the nodes of a list. Since the peNode p_vElem field is a void pointer, it can point to anything. It seemed like a good idea, but now I'm not sure.
1. First, it occured to me that if an implementation needed a user-defined function for the deletion of nodes, then it would also need a user-defined function for the creation of nodes. (I currently have a function called createNode, which I will list and discuss later). Isn't this the case? If you need special instructions to delete a node, wouldn't that imply that you needed special instructions to create it? Of course, it's no trouble to add this functionality to the code. However, the more I thought about it, the less certain I was that the user defined create and delete functions would be of any use.
2. Are there potential uses of this list that would require user-defined create and delete functions for nodes? If a peNode consists of two peNode pointers and a void pointer, then does one call to malloc always do the trick? If the node's void pointer (p_vElem) points to some complex data type, doesn't the developer have to worry about allocating space for the complex data object itself, and not its pointer?
I've currently run into a problem when testing the list using simple data. I'm not worrying about user-defined create and delete functions at this phase of testing. I simply use the following function to create a node:
Code:
peNode* createNode(void *p_vElem){
peNode *p_Node = (peNode *) malloc(sizeof(peNode));
if(p_Node!=NULL){
p_Node->p_vElem = p_vElem;
p_Node->p_Next = NULL;
p_Node->p_Prev = NULL;
}
return p_Node;
}
That's pretty straightforward. Now, if I want to add a node to the head of a list, I use the prependNode function:
Code:
RTRN prependNode(peList *p_List, peNode *p_Node){
if(p_Node == NULL){
return PE_LIST_NULL_ELEMENT;
}
if(isEmpty(p_List)){
p_List->p_Head = p_Node;
p_List->p_Tail = p_Node;
p_Node->p_Prev = NULL;
p_Node->p_Next = NULL;
}else{
p_Node->p_Next = p_List->p_Head;
p_List->p_Head->p_Prev = p_Node;
p_Node->p_Prev = NULL;
p_List->p_Head = p_Node;
}
p_List->iSize++;
return PE_LIST_OK;
}
To remove a node from a list, I use removeNode:
Code:
RTRN removeNode(peList *p_List, peNode *p_Node, void **p_vElem){
if(isEmpty(p_List)){
return PE_LIST_EMPTY;
}
if(p_Node == NULL){
return PE_LIST_NULL_ELEMENT;
}
*p_vElem = p_Node->p_vElem;
if(isHead(p_List,p_Node)){
if(hasNext(p_Node)){
p_List->p_Head = p_Node->p_Next;
p_Node->p_Next->p_Prev = NULL;
}else{
p_List->p_Head = NULL;
p_List->p_Tail = NULL;
}
}else{
p_Node->p_Prev->p_Next = p_Node->p_Next;
if(isTail(p_List, p_Node)){
p_List->p_Tail = p_Node->p_Prev;
}else{
p_Node->p_Next->p_Prev = p_Node->p_Prev;
}
}
free(p_Node);
p_List->iSize--;
return PE_LIST_OK;
}
Finally, if I want to delete a list, I call deleteList. (Please note that I'm not posting the initList code, but it does contain a call to malloc.):
Code:
RTRN deleteList(peList *p_List){
void *p_vElem;
while(containsData(p_List)){
removeNode(p_List, p_List->p_Tail, &p_vElem);
}
free(p_List);
return PE_LIST_OK;
}
OK. Thank you for taking the time to look at these functions. Now I'll get on with the problem. If I use the functions as they are intended:
Code:
int main(void){
peList *p_List;
char *p_str = "A test string";
void *p_vElem;
peNode *p_Node;
initList(p_List);
p_Node = createNode(p_str);
prependNode(p_List, p_Node);
deleteList(p_List);
}
all is fine. But what if I don't call createNode? Well, if I set p_Node to NULL, I'm still fine:
Code:
int main(void){
peList *p_List;
void *p_vElem;
peNode *p_Node = NULL;
initList(p_List);
prependNode(p_List, p_Node);
deleteList(p_List);
}
This works because prependNode checks to ensure that the p_Node parameter isn't null before it adds it to a list. So in the above example, deleteList is passed an empty list, and simply frees the peList object.
But what if I don't call createNode and I don't set p_Node to NULL?
Code:
int main(void){
peList *p_List;
void *p_vElem;
peNode *p_Node;
initList(p_List);
prependNode(p_List, p_Node);
deleteList(p_List);
}
This causes an error. When the p_Node pointer is declared and not initialized (either to NULL or with createNode), it contains garbage. Therefore, the aforementioned NULL check in prependNode doesn't apply, and the p_Node is added to the list. But when deleteList tries to free it, a runtime error is thrown because the node wasn't created with malloc.
So what if I try to free the list without freeing the node? This time I won't call deleteList at all:
Code:
int main(void){
peList *p_List;
void *p_vElem;
peNode *p_Node;
initList(p_List);
prependNode(p_List, p_Node);
free(p_List);
}
Well, this program gets past the call to free, but then it crashes. I'm asuming that this is because I still have a peNode pointer hanging in limbo, but I'm not sure.
3. Can anyone tell me why the last program dies?
4. How can I change deleteList or prependNode to handle uninitialized nodes?
I'd like to thank you all again for you time and your input!