Connecting Tech Pros Worldwide Forums | Help | Site Map
bytes > topic > c > answers

How to free Single linked List Nodes with dynamic char* fields???

Newbie
  
Join Date: Jan 2007
Location: na
Posts: 26
#1: Jun 8 '08
hi guys please help about Linked List,

I'm having trouble freeing the allocated memory of a single linked list node with a dynamic char* fields, it doesn't freed up if I use the FREE() function in C.. But if I try to use a single linked list with a static char array fields I can free the memory allocated with out any problems using the FREE(). So, why freeing a single linked list with dynamic char* is hard and why the FREE() function is not working??? You can see the difference if you monitor the Memory and Swap in your OS System Monitor.

Thanks in advance!

Here is my code

Expand|Select|Wrap|Line Numbers
  1. #include <stdio.h>
  2. #include <string.h>
  3. #include <stdlib.h>
  4.  
  5. /*
  6.     Base Platform OS: Ubuntu 7.04
  7.  
  8.     C Compiler      : gcc (GCC) 4.1.2 (Ubuntu 4.1.2-0ubuntu4)
  9.  
  10.     How I compile  : 
  11.  
  12.             terminal$ gcc -Wall main.c -o main
  13.  
  14.     Problem         : Freeing the allocated memory of Dynamic Char* in a Single Linked 
  15.               List is not working I don't know why.. But if I use the Static Char 
  16.               Array and free the Single Linked List Nodes, the memory and swap 
  17.               allocated are freed up successfuly.
  18.  
  19.     Note        : To monitor the behaviour of the Memory and the Swap memory of the OS 
  20.               use the System Monitor 
  21.  
  22. */
  23.  
  24. typedef struct ptable
  25. {
  26.   char *data1;//[50];    
  27.   char *data2;//[50];
  28.   char *data3;//[50];
  29.   char *data4;//[50];
  30.   int len;
  31.   struct ptable *next;
  32. }pTable;
  33.  
  34. /* function prototypes */
  35. void freemem(pTable **pointer);
  36. void drop_rec(char * rec);
  37. int display(pTable *pointer);
  38.  
  39. /* Free the allocated memory of Dynamic Char* */
  40. void drop_rec(char * rec)
  41. {
  42.     free(rec);
  43.     rec = NULL;
  44. return;
  45. }
  46.  
  47. int main()
  48. {
  49.     long i = 0;
  50.     char tdata[50] = "";
  51.  
  52.     pTable * ptable;
  53.     pTable * header;
  54.     pTable * pointer;
  55.  
  56.     memset(tdata,0,50);        
  57.  
  58.         /* create a list of data */
  59.     for(i=0;i<=1000000;i++)
  60.     {
  61.         /* clean tdata first */
  62.         memset(tdata,0,50);
  63.  
  64.         /* create data to be inserted */
  65.         sprintf(tdata,"0000000%ld",i);
  66.  
  67.         /* allocate memory */
  68.         ptable = (pTable *) malloc(sizeof(pTable));    
  69.         if(ptable == NULL){
  70.             printf("Unable to allocate memory.\n");
  71.             break;
  72.             return -1;
  73.         }
  74.  
  75.         /* I should also check these,if the memory has been allocated successfuly */
  76.                 /* but I want to make this code short just to understand quickly*/
  77.  
  78.         ptable->data1 = malloc(strlen((char *) tdata)+1); /* set the size to be allocated */
  79.         ptable->data2 = malloc(strlen((char *) tdata)+1); /* set the size to be allocated */
  80.         ptable->data3 = malloc(strlen((char *) tdata)+1); /* set the size to be allocated */
  81.         ptable->data4 = malloc(strlen((char *) tdata)+1); /* set the size to be allocated */
  82.  
  83.         ptable->next = NULL;
  84.  
  85.         if(header == NULL)
  86.             header = ptable;
  87.         else
  88.             pointer->next = (pTable *) ptable;
  89.  
  90.         /* Assign some values */
  91.         sprintf(ptable->data1,"%s",(char *) tdata);
  92.         sprintf(ptable->data2,"%s",(char *) tdata);
  93.         sprintf(ptable->data3,"%s",(char *) tdata);
  94.         sprintf(ptable->data4,"%s",(char *) tdata);
  95.  
  96.         pointer = ptable;
  97.  
  98.     }    
  99.  
  100.     pointer = header;
  101.  
  102.         /* displaying the records will take some time */
  103.     /* display(pointer); */
  104.  
  105.     printf("Press Any Key to release allocated memory . . .\n");
  106.     getchar();
  107.     printf("freeing allocated memory . . .\n");    
  108.     printf("Look at the System Monitor if the Memory and Swaps are being freed.\n");
  109.     freemem(&pointer); /* free memory (this one is not working I don't know) */
  110.     freemem(&header);  /* free memory (this one is not working I don't know) */
  111.     printf("Memory freed up! Done.\n");
  112.     printf("Press Any Key to close.\n");
  113.     getchar();
  114.  
  115.     /* then it only freed up the allocated memory 
  116.        if the program is terminated */
  117.  
  118.     return 0;
  119. }
  120.  
  121. /* free up memory doesn't work */
  122. void freemem(pTable **pointer)
  123. {
  124.     pTable *ptr,*next;
  125.     ptr = *pointer;
  126.  
  127.     while(ptr != NULL)
  128.     {
  129.         /* save the next node */
  130.         next =(pTable*) ptr->next;        
  131.  
  132.         /* defective part of my freemem (NOT Working)*/
  133.         /* I used the FREE() function, same result doesn't work*/
  134.         drop_rec(ptr->data1); /* free the char* field */
  135.         drop_rec(ptr->data2); /* free the char* field */
  136.         drop_rec(ptr->data3); /* free the char* field */
  137.         drop_rec(ptr->data4); /* free the char* field */
  138.  
  139.             free(ptr);  /* free node */
  140.         ptr = next; /* get the next node to be freed up*/
  141.     }
  142.     /* remove the handle*/  
  143.     ptr = NULL;
  144.     return;
  145. }
  146.  
  147. int display(pTable *pointer)
  148. {
  149.     pTable *ptr;
  150.  
  151.     ptr = pointer;
  152.     printf("\n\n");
  153.     /* loop and display records */
  154.     while(ptr != NULL)
  155.     {    
  156.         printf("************\n");
  157.         printf("Data1 [%s]\n",ptr->data1);
  158.         printf("Data2 [%s]\n",ptr->data2);
  159.         printf("Data3 [%s]\n",ptr->data3);
  160.         printf("Data4 [%s]\n",ptr->data4);
  161.         ptr = (pTable*) ptr->next;
  162.         printf("************\n");
  163.     }
  164.     printf("\n\n");
  165. return 0;
  166. }

gpraghuram's Avatar
Expert
  
Join Date: Mar 2007
Location: Chennai
Posts: 1,258
#2: Jun 9 '08

re: How to free Single linked List Nodes with dynamic char* fields???

It should work.
Try replacing the function drop_rec with free(ptr) and ptr=NULL; inside the code itself.

Raghu
Newbie
  
Join Date: Jan 2007
Location: na
Posts: 26
#3: Jun 9 '08

re: How to free Single linked List Nodes with dynamic char* fields???

Quote:

Originally Posted by gpraghuram

It should work.
Try replacing the function drop_rec with free(ptr) and ptr=NULL; inside the code itself.

Raghu

Yes Sir, I did this one before and it doesn't work with dynamic char* but when I'm using the static char array it works well. I tried it again just to verify it and here is the new code for freemem() function as suggested. I don't know if there is a hardware issues or OS issues but I tried to use another computer with same OS but with different hardware and the result is still problematic.

Expand|Select|Wrap|Line Numbers
  1. /* free up memory doesn't work */
  2. void freemem(pTable **pointer)
  3. {
  4.     pTable *ptr,*next;
  5.     ptr = *pointer;
  6.  
  7.     while(ptr != NULL)
  8.     {
  9.         /* save the next node */
  10.         next =(pTable*) ptr->next;        
  11.         /* Only works if I change the fields char* to static array char[50]*/
  12.         free(ptr);    // replace drop_rec function with FREE    
  13.         ptr = NULL; // release handle
  14.  
  15.         ptr = next; /* get the next node to be freed up*/
  16.     }
  17.  
  18.     return;
  19. }
gpraghuram's Avatar
Expert
  
Join Date: Mar 2007
Location: Chennai
Posts: 1,258
#4: Jun 9 '08

re: How to free Single linked List Nodes with dynamic char* fields???

How are u saying that free is not working?

Raghu
Newbie
  
Join Date: Jan 2007
Location: na
Posts: 26
#5: Jun 9 '08

re: How to free Single linked List Nodes with dynamic char* fields???

Quote:

Originally Posted by gpraghuram

How are u saying that free is not working?

Raghu

Ok, free() is not working if I freeing the allocated memory of a Single Linked List with dynamic array char* field. On the other hand, free() is working if I freeing the allocated memory of a Single Linked List with static array char[]. Yes, I agreed with you that the previous suggestion you mentioned should work. But in this case I don't know what is going on I can not see the problem. If you want may be you could try to run my program and see what I'm trying to say.

I remove my code here, because I think I'm violating the posting rules here
Newbie
  
Join Date: Jan 2007
Location: na
Posts: 26
#6: Jun 9 '08

re: How to free Single linked List Nodes with dynamic char* fields???

You will notice that there will be no compilation error, and while running the program will run smoothly no crashes or memory fault will happen. You can open the System Monitor to see what's going on to the Memory and Swap, you'll see the difference.

Thanks
gpraghuram's Avatar
Expert
  
Join Date: Mar 2007
Location: Chennai
Posts: 1,258
#7: Jun 9 '08

re: How to free Single linked List Nodes with dynamic char* fields???

Quote:

Originally Posted by sirsnorklingtayo

You will notice that there will be no compilation error, and while running the program will run smoothly no crashes or memory fault will happen. You can open the System Monitor to see what's going on to the Memory and Swap, you'll see the difference.

Thanks

I am not very sure that this is the right way to find whether the free is working.
There should be a better way of doing this...
Other experts please comment on this

Raghu
Banfa's Avatar
AdministratorVoR
  
Join Date: Feb 2006
Location: South West UK
Posts: 6,190
#8: Jun 9 '08

re: How to free Single linked List Nodes with dynamic char* fields???

How do you know that free is not working? How do you know it has not returned the memory to the heap?
JosAH's Avatar
Expert
  
Join Date: Mar 2007
Posts: 10,611
#9: Jun 9 '08

re: How to free Single linked List Nodes with dynamic char* fields???

If you allocate a list node and allocate again for a char* that is part of that list node
then you have to free them both in opposite direction: first free that char* part of
the list node and then free the node itself.

kind regards,

Jos
Newbie
  
Join Date: Jan 2007
Location: na
Posts: 26
#10: Jun 9 '08

re: How to free Single linked List Nodes with dynamic char* fields???

I can see it using the System Monitor of Linux Ubuntu, there is a real-time graph that can tell how much memory are being allocated. And so when I'm running my sample program, the Memory and Swap Graph telling me that my memory is hitting up to 40% - 50% of usage. You'll notice in my code that I'm pausing the program and ask the user to press any key to free some memory so that the user has enough time to see the Memory Graph declining, it means the memory are being deallocated and return it to OS. But this scenario is only working and it happens in real time when deallocating the memory allocated by a "Single Linked List Node with static array char", so this scenario should also happen when deallocating a "Single Linked List Node with Dynamic Array Char*" but it did not and it only means that the memory are still allocated and not being freedup by FREE() function. So what do you think Sirs?

Best Regards,
Norman
Newbie
  
Join Date: Jan 2007
Location: na
Posts: 26
#11: Jun 9 '08

re: How to free Single linked List Nodes with dynamic char* fields???

Quote:

Originally Posted by JosAH

If you allocate a list node and allocate again for a char* that is part of that list node
then you have to free them both in opposite direction: first free that char* part of
the list node and then free the node itself.

kind regards,

Jos

Yes Sir, I did this also deallocate first the fields then next is the list node pointer. Like the code below taken from above code

Expand|Select|Wrap|Line Numbers
  1. #
  2. /* free up memory doesn't work */
  3.  
  4. void freemem(pTable **pointer)
  5. {
  6.     pTable *ptr,*next;
  7.     ptr = *pointer;
  8.  
  9.     while(ptr != NULL)
  10.     {
  11.         /* save the next node */
  12.         next =(pTable*) ptr->next;   
  13.         /* defective part of my freemem (NOT Working)*/
  14.  
  15.         /* I used the FREE() function, same result doesn't work*/
  16.  
  17.         drop_rec(ptr->data1); /* free the char* field */
  18.         drop_rec(ptr->data2); /* free the char* field */
  19.         drop_rec(ptr->data3); /* free the char* field */
  20.         drop_rec(ptr->data4); /* free the char* field */
  21.         free(ptr);  /* free node */
  22.  
  23.         ptr = next; /* get the next node to be freed up*/
  24.      }
  25.     /* remove the handle*/ 
  26.  
  27.     ptr = NULL;
  28.     return;
  29. }
And this is the reason why I raised this problem here, because in the first place freeing a memory should never be a problem because FREE() function will handle it.

Best Regards,
Norman
JosAH's Avatar
Expert
  
Join Date: Mar 2007
Posts: 10,611
#12: Jun 9 '08

re: How to free Single linked List Nodes with dynamic char* fields???

And what 'does not work' mean?

kind regards,

Jos
Banfa's Avatar
AdministratorVoR
  
Join Date: Feb 2006
Location: South West UK
Posts: 6,190
#13: Jun 9 '08

re: How to free Single linked List Nodes with dynamic char* fields???

Quote:

Originally Posted by sirsnorklingtayo

I can see it using the System Monitor of Linux Ubuntu, there is a real-time graph that can tell how much memory are being allocated. And so when I'm running my sample program, the Memory and Swap Graph telling me that my memory is hitting up to 40% - 50% of usage. You'll notice in my code that I'm pausing the program and ask the user to press any key to free some memory so that the user has enough time to see the Memory Graph declining, it means the memory are being deallocated and return it to OS. But this scenario is only working and it happens in real time when deallocating the memory allocated by a "Single Linked List Node with static array char", so this scenario should also happen when deallocating a "Single Linked List Node with Dynamic Array Char*" but it did not and it only means that the memory are still allocated and not being freedup by FREE() function. So what do you think Sirs?

I think that this is extremely circumstantial evidence that the memory is not freed. I do not know Ubuntu (or any other Linux) well but I would want an exact description of what is being monitored before I took this as proof of free not working.

In the context (I assume you are using gcc) I think it is far more likely that you either have a mistake in your program or are mis-interpreting the data than free from the gcc standard library or Ubuntu has an error in it.
Newbie
  
Join Date: Jan 2007
Location: na
Posts: 26
#14: Jun 10 '08

re: How to free Single linked List Nodes with dynamic char* fields???

Quote:

Originally Posted by JosAH

And what 'does not work' mean?

kind regards,

Jos

The memory is not released/deallocate when using the FREE() function. And there are no warning or error messages.
Newbie
  
Join Date: Jan 2007
Location: na
Posts: 26
#15: Jun 10 '08

re: How to free Single linked List Nodes with dynamic char* fields???

Quote:

Originally Posted by Banfa

I think that this is extremely circumstantial evidence that the memory is not freed. I do not know Ubuntu (or any other Linux) well but I would want an exact description of what is being monitored before I took this as proof of free not working.

In the context (I assume you are using gcc) I think it is far more likely that you either have a mistake in your program or are mis-interpreting the data than free from the gcc standard library or Ubuntu has an error in it.

Ok just give me some time to check this again I'll use different OS like Windows and lets see if I will be having a same problem again. Yes, actually that is my first suspect, may be I did something wrong in my codes or the Ubuntu 7.04 has an error on freeing memory. But the linux community stating that the Linux Ubuntu is very good in Memory management.. anyways I'll keep you posted on this I'll try something different.


Thanks and Best regards to all experts here,
Norman
Newbie
  
Join Date: Jan 2007
Location: na
Posts: 26
#16: Jun 10 '08

re: How to free Single linked List Nodes with dynamic char* fields???

Quote:

Originally Posted by sirsnorklingtayo

Ok just give me some time to check this again I'll use different OS like Windows and lets see if I will be having a same problem again. Yes, actually that is my first suspect, may be I did something wrong in my codes or the Ubuntu 7.04 has an error on freeing memory. But the linux community stating that the Linux Ubuntu is very good in Memory management.. anyways I'll keep you posted on this I'll try something different.


Thanks and Best regards to all experts here,
Norman

Hi again, it took me only a very short time to compile and test this on Windows Environment using the DEV-C++ Compiler. And I discovered something, there was an error message pop-up while freeing the memory note that "I used the same program and code".

At first the program running smoothly then, when the program done loading the data and ask me to press any key to free the memory allocated then this one pops up.

Message Box from Windows:
Application Error

The instruction at "0x004015e3" referenced memory at "0x83042460". The memory could not be "read".

Click on OK to terminate the progarm
Click on Cancel to debug the program

So, what does it mean? did I step on wrong address or something. The only thing that I am doing is just FREEing the memory using FREE() function and nothing more.
JosAH's Avatar
Expert
  
Join Date: Mar 2007
Posts: 10,611
#17: Jun 10 '08

re: How to free Single linked List Nodes with dynamic char* fields???

Quote:

Originally Posted by sirsnorklingtayo

The instruction at "0x004015e3" referenced memory at "0x83042460". The memory could not be "read".

Click on OK to terminate the progarm
Click on Cancel to debug the program

So, what does it mean? did I step on wrong address or something. The only thing that I am doing is just FREEing the memory using FREE() function and nothing more.

Indeed, the free() function doesn't corrupt memory by itself unless the memory
was corrupted already. Probably the addresses you passed to the free() function
were incorrect already. I'm afraid it's debugging time. Do your char* pointers in
your nodes actually point to dynamically allocated memory?

kind regards,

Jos
Newbie
  
Join Date: Jan 2007
Location: na
Posts: 26
#18: Jun 10 '08

re: How to free Single linked List Nodes with dynamic char* fields???

Quote:

Originally Posted by JosAH

Indeed, the free() function doesn't corrupt memory by itself unless the memory
was corrupted already. Probably the addresses you passed to the free() function
were incorrect already. I'm afraid it's debugging time. Do your char* pointers in
your nodes actually point to dynamically allocated memory?

kind regards,

Jos

Yes Sir, it should point to dynamically allocated memory because I used the MALLOC() function and malloc should point it correctly and do the job correctly. And the code goes like this:

Expand|Select|Wrap|Line Numbers
  1. typedef struct ptable
  2. {
  3.   char *data1;
  4.   char *data2;
  5.   char *data3;
  6.   char *data4;
  7.   int len;
  8.   struct ptable *next;
  9. }pTable;
  10. ...
  11. ...
  12. for(i=0;i<=1000000;i++)
  13.     {
  14.         memset(tdata,0,50);
  15.         sprintf(tdata,"0000000%ld",i);
  16.  
  17.         ptable = (pTable *) malloc(sizeof(pTable));
  18.         if(ptable == NULL){
  19.             printf("Unable to allocate memory.\n");
  20.             break;
  21.             return -1;
  22.         }
  23.  
  24.         ptable->data1 = malloc(strlen((char *) tdata)+1);
  25.         ptable->data2 = malloc(strlen((char *) tdata)+1);
  26.         ptable->data3 = malloc(strlen((char *) tdata)+1);
  27.         ptable->data4 = malloc(strlen((char *) tdata)+1); 
  28.         ptable->next = NULL;
  29.  
  30.         if(header == NULL)
  31.             header = ptable;
  32.         else
  33.             pointer->next = (pTable *) ptable;
  34.  
  35.         sprintf(ptable->data1,"%s",(char *) tdata);
  36.         sprintf(ptable->data2,"%s",(char *) tdata);
  37.         sprintf(ptable->data3,"%s",(char *) tdata);
  38.         sprintf(ptable->data4,"%s",(char *) tdata);
  39.  
  40.         pointer = ptable;
  41.  
  42.     }   
  43.  
is it aviceable to place the malloc() inside a for loop statement and allocate a new memory everytime a new link node is created?

Best Regards,
Norman
JosAH's Avatar
Expert
  
Join Date: Mar 2007
Posts: 10,611
#19: Jun 10 '08

re: How to free Single linked List Nodes with dynamic char* fields???

What are 'header' and 'pointer' and the other undefined variables?

kind regards,

Jos
Newbie
  
Join Date: Jan 2007
Location: na
Posts: 26
#20: Jun 11 '08

re: How to free Single linked List Nodes with dynamic char* fields???

Quote:

Originally Posted by JosAH

What are 'header' and 'pointer' and the other undefined variables?

kind regards,

Jos

Ah ok, these variables are used to store the data inserted into ptable structure, you know linked list stuff.

pTable * header;
pTable * pointer;

header struct is used to store the first data entered to a linked node, this is essential to back track the first data since linked list node of ptable will end up to the last record, so I need to remember the first data entry or the first address so that I can go back in the first record.

pointer struct is used to to store all the data coming from ptable struct, so everytime there is a new node created, pointer struct will handle all the data of the linked list nodes. So that I can loop all over and retrive the data inserted.

and last the ptable struct this is used to buffer the data entered then pass it to header and pointer via dereferencing.

header = ptable; // dereference the ptable to header
pointer = ptable; // dereference the ptable to pointer

Since ptable srtuct is dereference to header and pointer, in the last data entry the only contents left on the ptable will be the first and last record only not all record will be inserted in this struct. It is beacuse the ptable is dereferenced to header and to last pointer record.

best regards,
norman
Newbie
  
Join Date: Jun 2008
Posts: 9
#21: Jun 15 '08

re: How to free Single linked List Nodes with dynamic char* fields???

Quote:

Originally Posted by sirsnorklingtayo

Ah ok, these variables are used to store the data inserted into ptable structure, you know linked list stuff.

pTable * header;
pTable * pointer;

header struct is used to store the first data entered to a linked node, this is essential to back track the first data since linked list node of ptable will end up to the last record, so I need to remember the first data entry or the first address so that I can go back in the first record.

pointer struct is used to to store all the data coming from ptable struct, so everytime there is a new node created, pointer struct will handle all the data of the linked list nodes. So that I can loop all over and retrive the data inserted.

and last the ptable struct this is used to buffer the data entered then pass it to header and pointer via dereferencing.

header = ptable; // dereference the ptable to header
pointer = ptable; // dereference the ptable to pointer

Since ptable srtuct is dereference to header and pointer, in the last data entry the only contents left on the ptable will be the first and last record only not all record will be inserted in this struct. It is beacuse the ptable is dereferenced to header and to last pointer record.

best regards,
norman



hello, i am new to this forum and i this is my first attempt to help !

First of all you do not initialize head to NULL. So head = NULL is really needed in the beginning.

Then, there is nothing wrong with your function. The only thing that i see wrong is calling it second time with invalid addresses for free function.

You have head and pointer point to the same thing: the start of the list, and of course they both have the same value ; that is the address of the first node of the list.

When firstly freemem is called with &pointer, function will free the entire list correctly ( at least in my computer ).

However, when you secondly use freemem function, with &head, free will try to free the block that head points at, which is of course wrong cause the list is already freed! Do not forget, that the function freemem when called with &pointer does NOT make head = NULL so as in the second call with &head the while loop will not be entered.

Hope i helped...
Reply

« previous question | next question »

/bytes/development

/bytes/it

Forums
Visit our community forums for general discussions and latest on Bytes

Our staff and community areas have moved to bytes.com/forums/

/bytes/about

We are a network of experts and professionals in IT and software development that help one another with answers to tough questions and share insights. Get the best answers to your questions from over 226,501 network members.

dev questions:
algorithms | asp | asp.net | c/c++ | coldfusion | c# | flash | html/css | java | javascript |
mobile dev | .net | perl | php | python | ruby | software dev | vb.net | visual basic | xml
it questions:
access | apache | careers | db2 | iis | macosx | mysql | networking | oracle | postgresql | sql server | unix | windows

About Bytes | Copyright 1995-2009 BYTES. All rights Reserved