free list

**rabers** · 02-17-2009

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?

**matsp** · 02-17-2009

How does it not work properly?

What is your overall structure of the list?

--
Mats

**rabers** · 02-17-2009

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?

**Snafuist** · 02-17-2009

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?

**MK27** · 02-17-2009

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);

**rabers** · 02-17-2009

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.

**tabstop** · 02-17-2009

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

**Bladactania** · 02-17-2009

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

**MK27** · 02-17-2009

Originally Posted by tabstop

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.

**rabers** · 02-17-2009

If I free e4 then what e3->right holds?

**Bladactania** · 02-17-2009

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

**MK27** · 02-17-2009

Originally Posted by rabers

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".

**rabers** · 02-17-2009

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?

**Bladactania** · 02-17-2009

correct.

**MK27** · 02-17-2009

Originally Posted by rabers

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.

Thread: free list

Thread Tools

Search Thread

Display

free list

Similar Threads

Following CTools

Duplicating value of pointer to linked list

singly linked circular list

List class

Linked list with two class types within template.