Deallocating memory for a linked list

Hi everyone,
i am trying to deallocate the memory for i linked list i allocated using malloc. but i cannot seem to clear the nodes.

here is the relevant parts of my program:

Code:

---

struct node
{
        char depart[25];
        char arrive[25];
        int depart_time;
        int arrive_time;
       
        int id;       

        struct node *next;
};

---

This is where my structure 'node' is created.

Code:

---

struct node* mknode(char depstat[25], char arrstat[25], int dtime, int atime, int check)
{
        struct node* np;
       
        np=(struct node*)malloc(sizeof(struct node));
       
        if(np)
        {
                strcpy(np->depart,depstat);
                strcpy(np->arrive,arrstat);
                np->depart_time=dtime;
                np->arrive_time=atime;
               
                np->id=check;
               
                np->next=NULL;
        }
       
        return np;
}

---

This part is assigning values to each variable in the structure.

Code:

---


        struct node *n2;
        int number;

        for(number=1; number<=check; number++)
        {
                if(number==n->id)
                {
                        n2=n;
                        n=n->next;
                        free(n2);
                        return 1;
                }
        }
}

---

I have tried to deallocate using this code(this is the part where i am sure it is going wrong)

Code:

---

deallocate(&n_start, check);

---

and i call the function using this line

the first node in the linked list is 'n_start'
check is the number of nodes in the list

i know that the nodes are all being created properly so that part is ok.

and how can i check that the mmory is deallocated?can i use a simple printf of what should be deallocated?(btw: i am using OSX Tiger and Xcode if that makes a difference)

thank you all very much

How many of the nodes are you trying to remove?

All of them?

yes, i intend to run the function just before the program closes so i can avoid memory leaks.

so i dont need to bother about relinking the nodes on either side, i just need to remove everything

Code:

---

deallocate(&n_start, check);

---

is n_start poinrt???
I mean struct node *n_start;
You are passing n_start as "&n_start" inturn passing address where n_start is stored in memory, so that can be a problem,so you are probably accessing memory which is not urs,so that can be a problem.
It would be better if u post ur entire code or atleast entire function.
Thanks & Regards
Vinit :)

I am not sure I understod you.
But the a look at the deallocate function.

Code:

---

#include <stdlib.h>
#include <stdio.h>
#include <math.h>
#include <limits.h>
#include <string.h>
#include <time.h>


/* You don't need to worry about memory leaks. becasue as the
  program closes, All the memory for this program is relased */

struct node
{
        char depart[25];
        char arrive[25];
        int depart_time;
        int arrive_time;
       
        int id;       

        struct node *next;
};


struct node* mknode(char depstat[25], char arrstat[25], int dtime, int atime, int check)
{
        struct node* np;
       
        np=(struct node*)malloc(sizeof(struct node));
       
        if(np)
        {
                strcpy(np->depart,depstat);
                strcpy(np->arrive,arrstat);
                np->depart_time=dtime;
                np->arrive_time=atime;
               
                np->id=check;
               
                np->next=NULL;
        }
       
        return np;
}



void deallocate(struct node *phead)
{
struct node *pdel;


while ( pdel = phead )
  {
  phead = phead->next;
/* check that the mmory is deallocated */
  printf("Deallocate : %s %s %d %d %d\n",
            pdel->depart, pdel->arrive, pdel->depart_time, pdel->arrive_time, pdel->id);
  free(pdel);
  }       

}


int main(void)
{
struct node *phead;
struct node *pnew ;
char Idepart[25];
char Iarrive[25];
int Idepart_time;
int Iarrive_time;
int Iid;       


phead = NULL;
for ( ;  ; )
  {
  printf("Enter depart arrive depart_time arrvie_time id\n");
  scanf("%s %s %d %d %d", Idepart, Iarrive, &Idepart_time,&Iarrive_time, &Iid);
  if ( Idepart[0] == 'q' )
      break;
  if ( ! ( pnew = mknode(Idepart, Iarrive, Idepart_time,Iarrive_time, Iid)) )
      {
      printf("memory error\n");
      break;
      }
  pnew->next = phead;
  phead = pnew;
  }

deallocate(phead);
getchar();
getchar();
return(0);         
}

---

You dellocate memory using free(). I haven't plugged this into the code, but I would maybe do something like the following to delete the nodes. This is only one way of approching the problem.

Code:

---

void deallocate(struct node *phead)
{
 while(phead ! = NULL)
  struct node *temp = phead;
  phead = phead->next;
  free(temp);
 }
}

---

thanks for the posts...i dont quite understand the function tho :confused:

here is my whole code so far:

Code:

---

#include<stdio.h>
#include<stdlib.h>
#include<string.h>

struct node
{
        char depart[25];
        char arrive[25];
        int depart_time;
        int arrive_time;
       
        int id;       

        struct node *next;
};

struct node* mknode(char depstat[25], char arrstat[25], int dtime, int atime, int check)
{
        struct node* np;
       
        np=(struct node*)malloc(sizeof(struct node));
       
        if(np)
        {
                strcpy(np->depart,depstat);
                strcpy(np->arrive,arrstat);
                np->depart_time=dtime;
                np->arrive_time=atime;
               
                np->id=check;
               
                np->next=NULL;
        }
       
        return np;
}

int direct(char depart[25], char arrive[25], int arrival, struct node *n, int check)
{       
        int direct_value=0,time=0;
       
        printf("\nDIRECT ROUTE: ");
       
        while((n->id)<=(check))
        {       
                if((strcmp(depart,n->depart)==0)&&(strcmp(arrive,n->arrive)==0)&&(n->arrive_time<=arrival)&&((arrival-200)<(n->arrive_time)))
                {
                        time=duration(n->depart_time, n->arrive_time);
                        printf("\nDepart: %s at %.2d:%.2d\n",depart,n->depart_time/100,n->depart_time%100);
                        printf("Arrive: %s at %.2d:%.2d\nChange at: None\n",arrive,n->arrive_time/100,n->arrive_time%100);
                        printf("Duration: %.2d:%.2d\n",time/60,time%60);
                        direct_value=1;
                }
               
                if((n->next) != NULL)
                        n=n->next;
                else
                        break;
        }
       
        if(direct_value==0)
                printf("None\n");
               
        return 0;
}

int indirect(char depart[25], char arrive[25], int arrival, struct node *n,int check)
{
        struct node *second_node=NULL, *head=NULL;
        char change_station[25];
        int loops=1,change=0,indirect_value=0;
        int wait_time,time;
       
        head=n;
        second_node=n;
       
        printf("\nINDIRECT ROUTE: ");
       
        while((second_node->id) <= check)
        {               
                if(strcmp(depart,second_node->depart)==0)
                        {
                                strcpy(change_station,second_node->arrive);
                                change=1;
                        }
               
                if(change==1)
                {       
                        while((n->id) <= check)
                        {                                       
                                if((strcmp(n->arrive,arrive)==0)&&(strcmp(change_station,n->depart)==0)&&(n->arrive_time<=arrival)&&((arrival-200)<(n->arrive_time)))
                                {
                                        wait_time=duration(second_node->arrive_time,n->depart_time);
                                        if((5<=wait_time)&&(wait_time<=60))
                                        {
                                                time=duration(second_node->depart_time, n->arrive_time);
                                                printf("\nDepart: %s at %.2d:%.2d\n",depart,second_node->depart_time/100,second_node->depart_time%100);
                                                printf("Arrive: %s at %.2d:%.2d\n",arrive,n->arrive_time/100,n->arrive_time%100);
                                                printf("Change at: %s\n",change_station);
                                                printf("Duration: %.2d:%.2d\nWait time at %s: %.2d minutes\n",time/60,time%60, change_station,wait_time);
                                                indirect_value=1;
                                        }
                                }
                               
                                if((n->next) != NULL)
                                        n=n->next;
                                else
                                        break;
                        }
                }
                n=head;
                loops++;
               
                if((second_node->next) != NULL)
                        second_node=second_node->next;
                else
                        break;
                       
                change=0;
        }
       
        if(indirect_value==0)
                printf("None\n");
       
        return 0;
}

int check_station(char station[25], struct node *n, int check)
{
        int real_station=0;
       
        while((n->id)<=(check))
        {       
                if((strcmp(station,n->depart) == 0) || (strcmp(station,n->arrive) == 0))
                        real_station=1;
                                                                                       
                if((n->next) != NULL)
                        n=n->next;
                else
                        break;
        }
       
        if(real_station==0)
                        printf("THE STATION ENTERED '%s' IS NOT A VALID STATION\n",station);
       
        return real_station;
}

int duration(int timeA, int timeB)
{
        int hoursA,hoursB,minsA,minsB,timeA_mins,timeB_mins,diff_mins;

        hoursA=timeA/100;
        minsA=timeA-(hoursA*100);
        timeA_mins=(hoursA*60)+(minsA);
               
        hoursB=timeB/100;
        minsB=timeB-(hoursB*100);
        timeB_mins=(hoursB*60)+(minsB);
       
        diff_mins=timeB_mins-timeA_mins;
               
        return diff_mins;
}

int deallocate(struct node *n, int check)
{
        struct node *n2;
        int number;

        for(number=1; number<=check; number++)
        {
                if(number==n->id)
                {
                        n2=n;
                        n=n->next;
                        free(n2);
                        return 1;
                }
        }
}

int main(void)
{
        int arrival,c=0,d=0,start=0,check=0,real_station=0;
        char arrive[20],depart[20],a[25],b[25];
        FILE *ttimes;
        struct node *n=NULL,*n_start=NULL,*n2=NULL, *n3=NULL;
                       
        ttimes=fopen("times.txt","r");
        if(ttimes == NULL)
        {
                printf("There was an error opening the train timetable\nNow exiting...\n");
                return 1;
        }
                       
        while(fscanf(ttimes,"%s %s %d %d",a,b,&c,&d) != EOF)
        {
                check++;
               
                if(start == 1)
                {       
                        n2=mknode(a,b,c,d, check);
                        n->next=n2;
                        n=n2;
                }
               
                if(start == 0)
                {       
                        n=mknode(a,b,c,d, check);
                        start=1;
                        n_start=n;
                }       
        }
       
        fclose(ttimes);
       
        while(real_station == 0)
        {
                        printf("Enter the name of the station you will be departing from:\n");
                        scanf("%s",depart);
                        real_station=check_station(depart, n_start, check);
        }
       
        real_station=0;
       
        while(real_station == 0)
        {
                        printf("Enter the name of the station you will be arriving at:\n");
                        scanf("%s",arrive);
                        real_station=check_station(arrive, n_start, check);
        }
               
        printf("Please enter the time (HHMM) at which you would like to arrive at %s:\n", arrive);
        scanf("%d", &arrival);
               
        printf("\nUser wants to travel from %s to %s, to arrive at %d\n",depart,arrive,arrival);
       
        direct(depart, arrive, arrival, n_start, check);
        indirect(depart, arrive, arrival, n_start, check);
        deallocate(&n_start, check);
                       
        printf("\n");                       

        return 0;
}

---

i have left in my original deallocate function. there is an input file, but i know that this part of the code is correct, so hopefully some sense can still be made of this :p

its very long i know...but if anyone has any hints still, id be very grateful :D

thank you all so much

Okay, I need to drag my butt into work, but the method I used uses temp nodes.
Temp points to phead. phead points to next. I then free the temp node. The reason for this is because if the temp node wasn't there and phead->next was NULL, free() would do a segmentation fault because it was passed NULL. If phead->next was after free(), this would be undefined behavior.

Maybe someone else can explain this better than me.

ok, i understand that function...i think.
i have tried it, and it compiles and runs through the function but i dont think it is deallocating the memory.
i have used the code from cdalten like this:

Code:

---

void deallocate(struct node *phead)
{
        struct node *temp;
       
        while(phead != NULL)
        {
               
                temp = phead;
                phead = phead->next;
                printf("+-+%d+-+\n",temp->arrive_time);
                free(temp);
                printf("*-*%d*-*\n",temp->arrive_time);
        }
}

---

if the dellocation process id working, should the second printf be a blank space rather than a time?when i run the program, the times are printed, but both are the same :confused:
eg:
+-+0932+-+
*-*0932*-*
+-+1009+-+
*-*1009*-*
etc etc

thank you for your time

free(3) returns memory space allocated by malloc(3) and the like back to the OS, this does NOT mean it blanks out the memory.

What you're reading is the contents of the memory location pointed to by temp which is nolonger allocated to your program. It just so happens to hold the same data in it from its last use - given enough time this data will eventually be overwritten or used by something else.

oh ok .. so as the function is now, if ive understood you correctly, the memory allocated to the node is cleared?
so, is there any other way to check the memory is deallocated or is it down to faith in the program? :confused:

many thanks

> so, is there any other way to check the memory is deallocated
If you called free(), then it's gone.

As wintellect pointed out, the bytes are still there, probably containing what you last stored there, but you certainly can't rely on the memory containing anything in particular. As with a lot of these things, "seems to work" is only half the battle.

For example, some debug versions of memory manangement
- fill the memory you just deallocated with a magic pattern to indicate the memory has been freed.
- make the memory inaccessible to the program (causes a segfault)

Thank you all for your help :D

Another idéa is to use a memory pool!
Allocate memory pool(s) with an arbitary size with malloc( ), etc. Then you get memory objects from a pool with your own allocate( ) function. When it's curtains for the app you just free( ) your pool(s) of memory. Google on!

Quote:

---

free() would do a segmentation fault because it was passed NULL

---

free() will simply do nothing when passed a NULL, it won't crash anything.