free list

This is a discussion on free list within the C Programming forums, part of the General Programming Boards category; Hello, I have a little problem: I need to free a linked list and for some reason the function FreeList ...

  1. #1
    Registered User
    Join Date
    Jan 2009
    Posts
    29

    free list

    Hello, I have a little problem:
    I need to free a linked list and for some reason the function FreeList I wrote doesn't work.
    The list simulates a matrix and so each struct hold 2 pointers:
    one pointer is "right" and the other is "down".
    I have the anchor of the list (head) which is the upper left struct.
    I wrote:
    Code:
    void freeArray( Array * head )
    {
     if(!head)
      return;
     freeArray(head->right);
     freeArray(head->down);
     free(head);
    }
    Does anyone have an idea why it doesn't work properly?

  2. #2
    Kernel hacker
    Join Date
    Jul 2007
    Location
    Farncombe, Surrey, England
    Posts
    15,677
    How does it not work properly?

    What is your overall structure of the list?

    --
    Mats
    Compilers can produce warnings - make the compiler programmers happy: Use them!
    Please don't PM me for help - and no, I don't do help over instant messengers.

  3. #3
    Registered User
    Join Date
    Jan 2009
    Posts
    29
    i get an Error msg:
    "unhandled exception at....access violation reading location...
    it's like it doesnt really free each struct and i dont know why
    logicly it seems correct
    for example here is a simple list i try to free and i get this msg above
    why?
    Attached Images Attached Images  

  4. #4
    Complete Beginner
    Join Date
    Feb 2009
    Posts
    312
    Does anyone have an idea why it doesn't work properly?
    Yes.

    You are trying to free elements that have already been free()d earlier. Consider the following matrix A:

    e1 e2
    e3 e4

    Calling freeArray(e1) results in the following calls (I ommited calls that immediately return):

    freeArray(e1);
    freeArray(e2);
    freeArray(e4);
    free(e4);
    free(e2);
    freeArray(e3);
    freeArray(e4);
    free(e4);
    free(e3);
    free(e1);

    You'll notice that e4 is free()d two times. Furthermore, you're calling freeArray(e4) after having free()d e4 for the first time. This gets worse if the matrix grows. I suggest another approach freeing the structure, e.g. loop over the rows and free one column at a time.

    Greets,
    Philip

    EDIT: given your picture above, what is the index of the element in the lower right? It could be (2,3) if you reach it with the down-Pointer and (3,2) if you get there via the left-Pointer. This is not a matrix.

    EDIT: God meant matrices to be implemented via multidimensional arrays. Why don't you do just that?
    Last edited by Snafuist; 02-17-2009 at 08:43 AM.
    All things begin as source code.
    Source code begins with an empty file.
    -- Tao Te Chip

  5. #5
    spurious conceit MK27's Avatar
    Join Date
    Jul 2008
    Location
    segmentation fault
    Posts
    8,300
    If head->right->down == head->down->right (it does in your diagram) then Snafuist is right! You are double freeing.

    One simple way out is to set a pointer to NULL after you free it. Then
    Code:
    if (ptr) free(ptr);
    Last edited by MK27; 02-17-2009 at 08:57 AM.
    C programming resources:
    GNU C Function and Macro Index -- glibc reference manual
    The C Book -- nice online learner guide
    Current ISO draft standard
    CCAN -- new CPAN like open source library repository
    3 (different) GNU debugger tutorials: #1 -- #2 -- #3
    cpwiki -- our wiki on sourceforge

  6. #6
    Registered User
    Join Date
    Jan 2009
    Posts
    29
    at the spesific task i have ineed to use linked lists.
    I know its easier with arrays but thats the task i have.
    It's not a regular matrix but a sparse matrix. This kind of matrix holds only the non zero items.
    there for assume the uper row represents the columns heads and the left column represents the rows heads (for example: matrix of 2X2 order) and the only non-zero items are (1,1) and (2,2).
    now,
    after I free e2 and e4 I go back to e1 and go down to e3 and I dont free e4 cause e3's right and down are now NULL (am I right?) cause down was already NULL and right (e4) was free.

  7. #7
    and the Hat of Guessing tabstop's Avatar
    Join Date
    Nov 2007
    Posts
    14,185
    How would e3's right and down be NULL? Just freeing e4 doesn't make every pointer to it all of a sudden point somewhere else.

    Edit: If this is really a sparse matrix, then just traversing the rows (or just traversing the columns) is enough to free every element, eventually (since every element is a member of some row).

  8. #8
    Registered User
    Join Date
    Feb 2009
    Posts
    278
    If you insist on keeping this structure, then you need to rethink how the elements relate to each other. The best way would be to limit the elements so that only those on the far left (those on the down path from head) can have two pointers...

    Code:
    head->l_ear->r_ear->nose->null
       |
    neck->null
       |
    torso->l_arm->r_arm->null
       |
    trunk->l_leg->r_leg-null

  9. #9
    spurious conceit MK27's Avatar
    Join Date
    Jul 2008
    Location
    segmentation fault
    Posts
    8,300
    Quote Originally Posted by tabstop View Post
    How would e3's right and down be NULL? Just freeing e4 doesn't make every pointer to it all of a sudden point somewhere else.
    By which tabstop means free() != NULL -- you have to do that yourself. (S)he's right about the rows but that will be more complicated for you (albeit more optimized for the compiler and processor).

    I almost see some RACE CONDITION problems in the nulling solution, maybe...you won't be able to tell without using something like valgrind.
    Last edited by MK27; 02-17-2009 at 09:08 AM.
    C programming resources:
    GNU C Function and Macro Index -- glibc reference manual
    The C Book -- nice online learner guide
    Current ISO draft standard
    CCAN -- new CPAN like open source library repository
    3 (different) GNU debugger tutorials: #1 -- #2 -- #3
    cpwiki -- our wiki on sourceforge

  10. #10
    Registered User
    Join Date
    Jan 2009
    Posts
    29
    If I free e4 then what e3->right holds?

  11. #11
    Registered User
    Join Date
    Feb 2009
    Posts
    278
    The pointer still points to the same memory adress it did before. The contents of that address are unknown because you've freed the memory. You need to alter the pointers that pointed to a node before freeing the node

  12. #12
    spurious conceit MK27's Avatar
    Join Date
    Jul 2008
    Location
    segmentation fault
    Posts
    8,300
    Quote Originally Posted by rabers View Post
    If I free e4 then what e3->right holds?
    That's the point. You have to set these to NULL, esp. in a linked-list context where you may want to use stuff like "if (ptr->next==NULL)" to find the tail.

    The way I did it is to include an intially NULL "prev" pointer in your function, that then becomes the last ptr before you would move to ptr->next. Then you deal with "prev->next".
    C programming resources:
    GNU C Function and Macro Index -- glibc reference manual
    The C Book -- nice online learner guide
    Current ISO draft standard
    CCAN -- new CPAN like open source library repository
    3 (different) GNU debugger tutorials: #1 -- #2 -- #3
    cpwiki -- our wiki on sourceforge

  13. #13
    Registered User
    Join Date
    Jan 2009
    Posts
    29
    so the problem is that efter freeing e2 and e4
    from e3: the free e3->right try to free e4 again? cause the pointer still pointing the address?

  14. #14
    Registered User
    Join Date
    Feb 2009
    Posts
    278
    correct.

  15. #15
    spurious conceit MK27's Avatar
    Join Date
    Jul 2008
    Location
    segmentation fault
    Posts
    8,300
    Quote Originally Posted by rabers View Post
    so the problem is that efter freeing e2 and e4
    from e3: the free e3->right try to free e4 again? cause the pointer still pointing the address?
    Hmmm. I had not considered the complications in a matrix, since you have to NULL more than one pointer! Maybe you should use a double linked list for this, so every node has a left, a right, a down, and an up. This way you can set NULL the ptr->left->right and ptr->up->down.
    C programming resources:
    GNU C Function and Macro Index -- glibc reference manual
    The C Book -- nice online learner guide
    Current ISO draft standard
    CCAN -- new CPAN like open source library repository
    3 (different) GNU debugger tutorials: #1 -- #2 -- #3
    cpwiki -- our wiki on sourceforge

Page 1 of 3 123 LastLast
Popular pages Recent additions subscribe to a feed

Similar Threads

  1. Following CTools
    By EstateMatt in forum C Programming
    Replies: 5
    Last Post: 06-26-2008, 10:10 AM
  2. Duplicating value of pointer to linked list
    By zephyrcat in forum C Programming
    Replies: 14
    Last Post: 01-22-2008, 02:19 PM
  3. singly linked circular list
    By DarkDot in forum C++ Programming
    Replies: 0
    Last Post: 04-24-2007, 08:55 PM
  4. List class
    By SilasP in forum C++ Programming
    Replies: 0
    Last Post: 02-10-2002, 04:20 PM
  5. Linked list with two class types within template.
    By SilasP in forum C++ Programming
    Replies: 3
    Last Post: 02-09-2002, 05:13 AM

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