Linked list possible memory leak?

This is a discussion on Linked list possible memory leak? within the C Programming forums, part of the General Programming Boards category; Hey all, It occurred to me recently that in year of coding I have never learned to use linked lists, ...

  1. #1
    Registered User
    Join Date
    Jun 2009
    Posts
    452

    Linked list possible memory leak?

    Hey all,

    It occurred to me recently that in year of coding I have never learned to use linked lists, so I decided to remedy that. I put together an implementation of a singly linked list.

    Now, I ran this through valgrind, and it says that there are several blocks "possibly lost" but I can't find where I would get a memory leak here. Can someone point it out?

    And, any general criticisms or suggestions are welcome as well, since I did this from scratch off the top of my head and I am sure there are ways to improve on it.

    Code:
    #include <stdio.h>
    #include <stdlib.h>
    
    
    typedef struct node 
    {
      int index;
      int data;
      struct node *next;
    }node; //data type for linked list nodes
    
    typedef struct list_info
    {
      int length;
      int size_of_elements;
      node *head;
      node *latest;
    }list_info; //data type to keep track of the current state of the list;
    
    
    /********************************************
    *Free the entire list
    */
    int free_list(list_info *list_props)
    {
      node *current;
      node *iter;
      int i;
      int freecount=0;
      current=list_props->head;
      while (current!=NULL)
      {
        iter=current->next;
        free(current);
        current=iter;
        freecount++;
        list_props->length--;
      }
      return freecount;
    }
      
      
    /********************************************
    *After adding a new node in the middle of the list, we need to fix the indices of other nodes
    */
    
    void re_Index_List(list_info *list_props)
    {
      int count=0;
      node *iter;
      for (iter=list_props->head; iter!=NULL; iter=iter->next)
      {
        iter->index=count;
        count++;
      }
    }
    
    
    /********************************************
    *print the index of the nodes along with the data they store
    */
    
    void print_list(list_info *list_props)
    {
      node *iter;
      for (iter=list_props->head; iter!=NULL;iter=iter->next)
      {
        printf("%d\t%d\n",iter->index,iter->data);
      }
    }
    
    
    /********************************************
    *Multipurpose node adder:
    *add a node at the end of the list if position desired exceeds the end
    *add a node in the position specificed otherwise
    */
    int add_node(list_info *list_props, int position) 
    {
      node *iter;
      node *newnode;
      if ((newnode=malloc(sizeof(node)))==NULL)
      {
        printf("Cannot allocate new node in position %d\n",position);
        abort();
      }
      for (iter=list_props->head;iter->next!=NULL && iter->next->index<position; iter=iter->next);
      if (position==0)
      {
        printf("Cannot replace head\n");
        return -1;
      }
      if (iter->next==NULL) //if we get to the end of the list before we are at the relevent position
      {
        iter->next=newnode;
        newnode->next=NULL;
        newnode->index=list_props->length;
        newnode->data=0;
        list_props->latest=newnode;
        list_props->length++;
        return 1;
      }
      else //we are adding a node in the middle of the list
      {
        node *temp;
        temp=iter->next;
        iter->next=newnode;
        newnode->next=temp;
        newnode->data=0;
        re_Index_List(list_props);
        list_props->latest=newnode;
        list_props->length++;
        return 2;
      }
        
    }
    
    
    int main(void)
    {
      list_info *list_props;
      if ((list_props=malloc(sizeof(list_info)))==NULL)
      {
        printf("cannot allocate memory for list_info\n");
        abort();
      }
      
      if ((list_props->head=malloc(sizeof(node)))==NULL)
      {
        printf("cannot allocate memory for head\n");
        abort();
      }
      int check;
      list_props->length=1;
      list_props->size_of_elements=sizeof(node);
      list_props->head->next=NULL;
      
      check = add_node(list_props, 1);
      list_props->latest->data=12;
      printf("check 1 = %d\n",check);
      
      add_node(list_props, 2);
      list_props->latest->data=15;
      printf("check 2 = %d\n",check);
      
      add_node(list_props, 3);
      list_props->latest->data=2;
      printf("check 3 = %d\n",check);
      
      add_node(list_props, 4);
      list_props->latest->data=5;
      printf("check 4 = %d\n",check);
      
      check = add_node(list_props, 3);
      list_props->latest->data=17;
      printf("check 5 = %d\n",check);
      
      check = add_node(list_props, 1);
      list_props->latest->data=4;
      printf("check 6 = %d\n",check);
      
      print_list(list_props);
      check = free_list(list_props);
      printf("%d free'd\n",check);
      return 0;
      
      
    }
    Last edited by KBriggs; 08-12-2010 at 09:41 AM.

  2. #2
    and the hat of wrongness Salem's Avatar
    Join Date
    Aug 2001
    Location
    The edge of the known universe
    Posts
    32,659
    Well you don't free list_props
    If you dance barefoot on the broken glass of undefined behaviour, you've got to expect the occasional cut.
    If at first you don't succeed, try writing your phone number on the exam paper.
    I support http://www.ukip.org/ as the first necessary step to a free Europe.

  3. #3
    Registered User
    Join Date
    Jun 2009
    Posts
    452
    Ha... so I don't.

    Nice...

    EDIT: yea, that was the whole problem. Now valgrind complains that I am using unititalized values in the print fucntion - is that just complaining about my comparison of iter to NULL?
    Last edited by KBriggs; 08-12-2010 at 08:58 AM.

  4. #4
    a_capitalist_story
    Join Date
    Dec 2007
    Posts
    2,651
    Code:
    if ((newnode=(node *)malloc(sizeof(node)))==NULL)
    You should NOT be casting the return value of malloc in a C program.

  5. #5
    Registered User
    Join Date
    Jun 2009
    Posts
    452
    Fair enough, but it can't hurt as long as I include stdlib.h, yes?

  6. #6
    and the hat of wrongness Salem's Avatar
    Join Date
    Aug 2001
    Location
    The edge of the known universe
    Posts
    32,659
    The hurt isn't when you're doing it right, it's when you're doing it wrong.

    NOT casting and NOT including stdlib.h gets you an error message you really need to pay attention to.

    See the FAQ
    If you dance barefoot on the broken glass of undefined behaviour, you've got to expect the occasional cut.
    If at first you don't succeed, try writing your phone number on the exam paper.
    I support http://www.ukip.org/ as the first necessary step to a free Europe.

  7. #7
    Registered User
    Join Date
    Jun 2009
    Posts
    452
    OK, I fixed it.

    Any comments/criticisms of the way I have implemented the list?

  8. #8
    and the hat of wrongness Salem's Avatar
    Join Date
    Aug 2001
    Location
    The edge of the known universe
    Posts
    32,659
    Creating a dummy node at the head of the list is a waste.
    If you dance barefoot on the broken glass of undefined behaviour, you've got to expect the occasional cut.
    If at first you don't succeed, try writing your phone number on the exam paper.
    I support http://www.ukip.org/ as the first necessary step to a free Europe.

  9. #9
    Jack of many languages Dino's Avatar
    Join Date
    Nov 2007
    Location
    Katy, Texas
    Posts
    2,309
    This code
    Code:
      for (iter=list_props->head;iter->next!=NULL && iter->next->index<position; iter=iter->next);
      if (position==0)
      {
        printf("Cannot replace head\n");
        return -1;
      }
    I would swap the two statements. No sense running the list before checking to see if input is valid or not. Also, why can't the head be replaced? Arbitrary decision?
    Mac and Windows cross platform programmer. Ruby lover.

    Quote of the Day
    12/20: Mario F.:I never was, am not, and never will be, one to shut up in the face of something I think is fundamentally wrong.

    Amen brother!

  10. #10
    Registered User
    Join Date
    Jun 2009
    Posts
    452
    Yeah, arbitrary decision. I plan to change that later, but for now there is no need.

    Statements swapped.

    Who said the head was a dummy node? I just haven't put anything in it in those test cases.

  11. #11
    Registered User
    Join Date
    Jun 2009
    Posts
    452
    Code added:

    Code:
    void get_pointer(list_info *list_props, node *ptr, int i)
    {
      if (i > list_props->length)
      {
        printf("Cannot get pointer for index %d: invalid index\n",i);
        ptr=NULL;
      }
      else if (i==-1) //get last node
      {
        for (ptr=list_props->head; ptr->next!=NULL; ptr=ptr->next);
      }
      else
      {
        for (ptr=list_props->head; ptr!=NULL && ptr->index<i; ptr=ptr->next);
      }
    }
    I want to get a pointer to to the node with index i with that. For some reason, if I call it in main as follows:

    Code:
    int main(void)
    {
      list_info *list_props;
      if ((list_props=malloc(sizeof(list_info)))==NULL)
      {
        printf("cannot allocate memory for list_info\n");
        abort();
      }
      
      if ((list_props->head=malloc(sizeof(node)))==NULL)
      {
        printf("cannot allocate memory for head\n");
        abort();
      }
      int check;
      list_props->length=1;
      list_props->size_of_elements=sizeof(node);
      list_props->head->next=NULL;
      
      check = add_node(list_props, 1);
      list_props->latest->data=12;
      printf("check 1 = %d\n",check);
      
      add_node(list_props, 2);
      list_props->latest->data=15;
      printf("check 2 = %d\n",check);
      
      add_node(list_props, 3);
      list_props->latest->data=2;
      printf("check 3 = %d\n",check);
      
      add_node(list_props, 4);
      list_props->latest->data=5;
      printf("check 4 = %d\n",check);
      
      check = add_node(list_props, 3);
      list_props->latest->data=17;
      printf("check 5 = %d\n",check);
      
      check = add_node(list_props, 1);
      list_props->latest->data=4;
      printf("check 6 = %d\n",check);
      
      
      node *ptr;
      get_pointer(list_props, ptr, 1);
      printf("%d --> %d\n",ptr->index,ptr->data);
      
      
      
      
      
      
      
      
      print_list(list_props);
      check = free_end_of_list(list_props, 3);
      printf("%d free'd\n",check);
      print_list(list_props);
      check = free_list(list_props);
      printf("%d free'd\n",check);
      free(list_props);
      return 0;
      
      
    }
    The contents of pointer are garbage, but the contents of the element with index 1 are not. Now, I'm sure it's something simple I am missing... Can someone point it out?
    Last edited by KBriggs; 08-12-2010 at 10:50 AM.

  12. #12
    and the hat of wrongness Salem's Avatar
    Join Date
    Aug 2001
    Location
    The edge of the known universe
    Posts
    32,659
    > Who said the head was a dummy node?
    Well you treat it as a special case when you add it, and then you also have a specific case if you try and delete it.

    Neither of these should be true.
    If you dance barefoot on the broken glass of undefined behaviour, you've got to expect the occasional cut.
    If at first you don't succeed, try writing your phone number on the exam paper.
    I support http://www.ukip.org/ as the first necessary step to a free Europe.

  13. #13
    Registered User whiteflags's Avatar
    Join Date
    Apr 2006
    Location
    United States
    Posts
    7,738
    Code:
    void get_pointer(list_info *list_props, node *ptr, int i)
    The contents of pointer are garbage, but the contents of the element with index 1 are not. Now, I'm sure it's something simple I am missing... Can someone point it out?
    Say your function finds the node with index i, stores the result in ptr, and returns. The ptr is popped from get_pointer's stack frame, along with the rest of it's parameters. You would either fix it by passing in the address of a pointer to change or by using a return value. It would be ok to delete the pointer-to-pointer, because the caller still has the pointer you changed.

  14. #14
    Registered User
    Join Date
    Jun 2009
    Posts
    452
    @Salem: You're right, I'll change that when I get a chance

    @whiteflags: Can't test it now, but do you mean something like this?

    Code:
    node *get_pointer(list_info *list_props, node *ptr, int i)
    {
      if (i > list_props->length)
      {
        printf("Cannot get pointer for index %d: invalid index\n",i);
        ptr=NULL;
      }
      else if (i==-1) //get last node
      {
        for (ptr=list_props->head; ptr->next!=NULL; ptr=ptr->next);
      }
      else
      {
        for (ptr=list_props->head; ptr!=NULL && ptr->index<i; ptr=ptr->next);
      }
       return ptr;
    }

  15. #15
    Registered User
    Join Date
    Jun 2009
    Posts
    452
    OK, that works, thanks Whiteflags.

    However, I am having a bit of trouble understanding it. Since ptr is passed by reference, shouldn't changes to it in the called function be reflected in the caller? Or does that concept only work for "one level down the pointer chain?"

Page 1 of 2 12 LastLast
Popular pages Recent additions subscribe to a feed

Similar Threads

  1. printing with linked list problem
    By schmidtc in forum C Programming
    Replies: 8
    Last Post: 07-13-2010, 06:17 PM
  2. Need help sorting a linked list. Beginner
    By scarlet00014 in forum C Programming
    Replies: 1
    Last Post: 09-27-2008, 06:16 PM
  3. Linked List Help
    By CJ7Mudrover in forum C Programming
    Replies: 9
    Last Post: 03-10-2004, 09:33 PM
  4. problem with structures and linked list
    By Gkitty in forum C Programming
    Replies: 6
    Last Post: 12-12-2002, 05:40 PM
  5. singly linked list
    By clarinetster in forum C Programming
    Replies: 2
    Last Post: 08-26-2001, 10:21 PM

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21