jgs

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.

Please Note: I think I have gained some insight into my problem. If you scroll down to the next section that is displayed in this shade of blue and read on until the end of the message, you'll see my latest progress and question (number 5). You may need to scroll back to some code, but you should get the gist of my question without having to read the entire message. I've posted this on another message board, but haven't had any luck - probably because it's so long. Of course, it you want to read the whole message and post comments about other questions, please do so by all means. Thank you!


I'll start by listing my data structures. First is the node struct, 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:


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:


That's pretty straightforward. Now, if I want to add a node to the head of a list, I use the prependNode function:


To remove a node from a list, I use removeNode:



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.):


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:


all is fine. But what if I don't call createNode? Well, if I set p_Node to NULL, I'm still fine:


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?


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:


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!


I think I may have answered my own questions (see 1 and 2) regarding user-defined create and delete functions in a doubly-linked list. At first, I wasn't sure that I would need to include this functionality in my list. But when I began testing the list, I found a problem.

During the first round of tests, I simply hard coded string values when I was creating new list nodes. For example:

(Toggle Plain Text)

   printf("Creating an empty peList.\n");
   p_List = initList();
   printf("A peList has been created.\n");

   printf("The size of the list is %d.\n", getSize(p_List));

   printf ("Creating a new Node with a string value: \"ABC\".\n");
   p_Node = createNode("\"ABC\"");

   printf("Prepending the node to the list.\n");
   prependNode(p_List, p_Node);

   printf("The size of the list is %d.\n", getSize(p_List));

   printf ("Creating a new Node with a string value: \"XYZ\".\n");
   p_Node = createNode("\"XYZ\"");

   printf("Prepending the node to the list.\n");
   prependNode(p_List, p_Node);

printf("Creating an empty peList.\n"); p_List = initList(); printf("A peList has been created.\n"); printf("The size of the list is %d.\n", getSize(p_List)); printf ("Creating a new Node with a string value: \"ABC\".\n"); p_Node = createNode("\"ABC\""); printf("Prepending the node to the list.\n"); prependNode(p_List, p_Node); printf("The size of the list is %d.\n", getSize(p_List)); printf ("Creating a new Node with a string value: \"XYZ\".\n"); p_Node = createNode("\"XYZ\""); printf("Prepending the node to the list.\n"); prependNode(p_List, p_Node);

... and so on. This worked as expected. (Defintions of the data structures and createNode and prependNode are listed earlier in this post). If I were to print the list, I would get :

Quote:

"XYZ" "ABC"

However, I used a menu interface during my second round of tests so that I could chose the size and content of the list at runtime.

So, if I chose the menu option to prepend a node to the test list, doPrependNode is called:

(Toggle Plain Text)

void doPrependNode(peList *p_List){

   char *p_strData;
   peNode *p_Node = NULL;

   p_strData = getData("\n\nPlease enter data for Node \n)");
   p_Node = createNode(p_strData);
   prependNode(p_List, p_Node);

}

void doPrependNode(peList *p_List){ char *p_strData; peNode *p_Node = NULL; p_strData = getData("\n\nPlease enter data for Node \n)"); p_Node = createNode(p_strData); prependNode(p_List, p_Node); }

Since getData returns a pointer to a global buffer, and the only memory allocated for data in createNode is for a void pointer, the contents of each node changes after each insertion:

(Toggle Plain Text)

// GLOBAL
static char bufr[129];

// GLOBAL static char bufr[129];

(Toggle Plain Text)

char* getData(char *p_strPrompt){

   int ch;
   int i = 0;

   printf("%s\n", p_strPrompt);
   scanf("%s", bufr);

   puts(bufr);

   return (bufr);

}

char* getData(char *p_strPrompt){ int ch; int i = 0; printf("%s\n", p_strPrompt); scanf("%s", bufr); puts(bufr); return (bufr); }

Now, if I select prependNode from the menu and enter "ABC", and then select it again and enter "XYZ", the list will contain:

Quote:

"XYZ" "XYZ"

This is because I'm storing the address of bufr in each node. But the content of bufr changes with each call to getData.

I think this illustrates why I need to have the programmer define createNode, deleteNode and the dataType of the node's content (which might be more complicated than a string) during list initialization.

5: Is this the case, or have I just defined getData incorrectly?

Thank you!

mackenga

Whew, that's a lot of detail. Sadly I don't have that much time on my hands at the moment, but I've spent a few minutes looking at your code and your problem.

Now, when the string goes into the linked list, if all that goes in there is a pointer to your static buffer, then every node will end up pointing at the same thing. The way to sort this is, as I'm sure you know, to make a copy of the string and have the linked list refer to this. You suggest that this means that we must have programmer-specified create/delete functions.

The fact is that many relatively complex data structures are likely to contain dynamically allocated pieces themselves. Creating and deleting them is likely to be a long way from trivial. However, considering the creation and destruction of nodes in this sort of detail to be the job of your linked list code seems a bit too eager! If your code is supposed to provide linked-list support, then why not just say it stores pointers; in which case any allocation/deallocation of the items stored will be left up to the application.

Of course, it would be anyway if you were requiring custom programmer-supplied create and delete functions - but then the application programmer would end up with the added complexity of registering these functions and would still effectively be writing the same code anyway - so why not just deal with pointers, and leave the application to make sure it's not supplying your linked list code with many pointers to a static buffer?

In other words, I think the sensible way to deal with this program is to call it a bug in the application and just have the linked list nodes store a pointer anyway. This would mean node creation and node deletion were standard and just a matter of creating and setting up the node structures themselves, and those node structures would just simply contain pointers to the type of data to be stored.

This is dodging the issue a bit, you could argue, but this is the way I would do it unless I had a very good reason to do otherwise.

Oh, as for the crashing: I'm not 100% sure, but what occurs to me is that free() on an uninitialised pointer is just as bad as trying to access the value it points at. I reckon you'll find the problem has something to do with that.

Eggbert

>peNode__{
>struct peList__{
Two consecutive underscores are always reserved by the implementation for any use. Your code could mysteriously break for no reason because of this. It would be wise to change these names. However, because a structure tag and a typedef name are in different name spaces, you can legally do this:
1. Creation is not required because the client code should be initializing p_vElem with a pointer to the content data. Creation and initialization of the content data is application specific, so there is no general way to do it from within your list. Deletion on the other hand is doable because function arguments can be standardized for a generic list. Deletion is a good idea as well. The only alternative would be to save a pointer to p_vElem and return it to the client code for deletion. Such a strategy has proven to be error prone.

2. The list only has to worry about allocating enough memory for a peNode. The memory pointed to by p_vElem is irrelevant except to the client code. For example:
In the client code, memory for p would be allocated and initial values assigned. For example:
3. Undefined behavior has a tendency to crash. In this case, prependNode is dereferencing an uninitialized pointer when it sets the p_Prev and p_Next members.

4. You cannot. This is a quality of implementation issue on the side of the client. There is no way to test for an uninitialized pointer, so you can only hope that the client knows what it is doing and either passes you a properly initialized pointer, or a null pointer.

5. Naturally, if you use the address of a global variable for every node, you will have aliasing problems and each node will reference the same memory. A linked list only works properly if each node is unique, so yes, createNode and deleteNode are needed. However, they should not be concerned with allocating and initializing p_vElem. That is the job of the client code as there is no portable way to create this functionality from within the list.