problem in freeing a "tree" of stuctures

let me start saying that I'm not a good c programmer
anyway at the moment I'm working on a program that someone else has written and that I have to modify to add other features (it deals with electromagnetic engineering but it is not relevant I guess)


DBimages is the following structure:

Code:

---

typedef struct DBIMAGES
{
  int *face;
  double *point;
  int Nbfaces;
  struct DBimages *NextLevel;
  struct DBimages *NextSameLevel;
  struct DBimages *PreviousLevel;
} DBimages;

---

as you can imagine the pointers inside the structure points to other structures to build a sort of tree with different levels

in the original program a sort of tree was built only once and it was used till the end of the program
that's why I think they didn't bother to write something to free that

now I have to build several of those and I'm running short of memory without freeing

this is what I tried to write (maxlev is the height of the tree or better the maximum number of levels allowed in the tree):

Code:

---

void FreeDBimages (ptr,maxlev)
DBimages *ptr;
int maxlev;
{
DBimages *curs,*temp;
int level;
level=1;
curs=(DBimages*)ptr->NextLevel;
while(level<maxlev){
  curs=(DBimages*)curs->NextLevel;
  level++;
}
while(curs!=NULL){
  temp=curs;
  FreedVector(temp->point,3);
  FreeiVector(temp->face,2);
  if(curs->NextSameLevel!=NULL)
  curs=(DBimages*)curs->NextSameLevel;
  else
  curs=(DBimages*)curs->PreviousLevel;
  free(temp);
}
}

---

unfortunately this function seems not to work
the first time I run it I got a segmentation fault (quite far from the beginning of the while loop)

anyone has any remark or suggestion or correction?

thanks in advance for any help

> void FreeDBimages (ptr,maxlev)
> DBimages *ptr;
> int maxlev;
Jeez, how old is this code?
This notation for a function has been obsolete for over 20 years.

You don't need to do anything with maxlev just to free the tree, so I just pass 0 down the tree.

Code:

---

void FreeDBimages (ptr,maxlev)
DBimages *ptr;
int maxlev;
{
    DBimages *curs,*temp;
    curs = ptr;
    while(curs!=NULL){
      temp=curs->NextSameLevel;            // next node at the current level
      FreeDBimages( curs->NextLevel, 0 );  // free everything below us
      FreedVector(curs->point,3);          // free everything we own
      FreeiVector(curs->face,2);
      free(cur);                            // free ourself
      cur = temp;                          // the saved next node
    }
}

---

the original program is not that old, anyway as I've said I'm far from being a good programmer and for sure I don't have any idea of obsolete or update notations

but the problem I guess isn't the notation

thanks for your reply but that won't work
it is my fault, I haven't explained how this sort of tree is implemented

let me do a scheme of that (the vertical bars are NextLevel pointers and the horizontal ones are NextSame Level pointers)

0
|
0 - 0 - 0
|
0 - 0 - 0 - 0
|
0 - 0

and all the nodes are linked with PreviousLevel pointer to the first of the previous level
the top one has a NULL pointer to previous level and the last ones of each level has a NULL pointer to NextSameLevel

I hope this is clear enough

Salem got a couple "cur" where he meant "curs", but otherwise what's wrong with it? Edit: It assumes that there are no links downwards from the second, third, ..., node in a horizontal chain, which is what your picture shows anyway. If there are links downwards, then you'll get double free errors.

> Edit: It assumes that there are no links downwards from the second, third,
Each curs tests curs->NextLevel, so that wouldn't be a problem AFAIK.

> thanks for your reply but that won't work
Did you try it, or just decide based on your limited knowledge?
Because what you've drawn and said is what I wrote (in advance) the code for.

The PreviousLevel pointers are of no use when you're just deleting the whole tree. Just let recursion, and the multiple instances of curs you get as a result handle that. You don't need to follow a PreviousLevel pointer to carry on deleting the tree.

> Salem got a couple "cur" where he meant "curs",
:)

Quote:

---

Originally Posted by Salem

> Edit: It assumes that there are no links downwards from the second, third,
Each curs tests curs->NextLevel, so that wouldn't be a problem AFAIK.

---

Well, what I mean is, you go down all the way and kill the bottom level just fine. But as you go across the level above that, if each node going across tries to go down and kill the bottom level again, bad things could happen. But as you said, that's not how it's drawn and it's not what I expect, so hey.

probably I still wasn't clear enough
I have also tried it anyway and it is not working
I don't know if tabstop was saying something like this but anyway what I was trying to say is that at a certain level all the nodes are linked with a nextsamelevel relationship even if they belong to different father nodes
I guess the code you wrote is going to try to free some node more than once
after that the last level has not a netxlevel null pointer assigned so I think maxlev is necessary

No null pointers at the bottom of the tree? Yikes.

Anyway, the question is, do you have a way to make sure you get the entire level? (I.e., do you know a "left-most" node like you have in your drawing?) And if you don't have nulls at the right to stop nextsamelevel, things could get really sticky. If so, then you're golden:

Code:

---

if (n>0)
    call recursively with child node and n-1
clear out current level (set temp = nextsamelevel, free this, set this to temp, lather, rinse, repeat)

---

It's not really a tree then if some nodes are pointed at by more than one other node. It's what is actually called a "directed acyclic-graph".

Anyway to delete one of those data structures you can simply keep some seperate list of all nodes deleted along the way, and before you delete any node, check it against that list.

> at a certain level all the nodes are linked with a nextsamelevel relationship even if they belong to different father nodes
So you have complicated traversal code in other places as well?

IMO, you have an unnecessarily complicated linking structure when you have that kind of special case. Do you have a good reason for it?
I mean, what happens when you want another level, don't you have to go all through the tree and pick apart the lowest level so it's no longer the lowest level?

> No null pointers at the bottom of the tree? Yikes.
Yeah, yikes here too :)

I just looked at your initial example and assumed it would be a regular tree where each Next pointer pointed to NULL if there was no more tree in that particular direction.

Quote:

---

Originally Posted by tabstop

No null pointers at the bottom of the tree? Yikes.

---

the reason they are not needed in the program is that you know exactly how many levels you have and you use that sort of tree always backward from the last level to the root (so there is a NULL previous level pointer in the root)

Quote:

---

Originally Posted by tabstop

Anyway, the question is, do you have a way to make sure you get the entire level? (I.e., do you know a "left-most" node like you have in your drawing?) And if you don't have nulls at the right to stop nextsamelevel, things could get really sticky.

---

the last node of a certain level has a NULL nextsamelevel pointer
about the leftmost node in a level I would say that for the first level is the one pointed with nextlevel by the root, for the second level is the one pointed with next level by the one pointed with nextlevel by the root and so on

Quote:

---

Originally Posted by Salem

So you have complicated traversal code in other places as well?

IMO, you have an unnecessarily complicated linking structure when you have that kind of special case. Do you have a good reason for it?
I mean, what happens when you want another level, don't you have to go all through the tree and pick apart the lowest level so it's no longer the lowest level?


I just looked at your initial example and assumed it would be a regular tree where each Next pointer pointed to NULL if there was no more tree in that particular direction.

---

well I called that "a sort of tree" because it was not a regular tree and I had no idea if it had other names

so how is this thing used in the program and why it has to be in that way?

Code:

---

while (level<ordmax)
  {
  curs = (DBimages*)curs->NextLevel;
  level++;
  }

---

ordmax is the height of the tree so with that as I've said in the previous answer you go to the last level

Code:

---

right = curs;
back = curs;
while (right)
  {
  back = right;
  while (back->PreviousLevel != NULL)
      {   
      do something;
      back = (DBimages*)back->PreviousLevel;
      }
    do something else;
    right = (DBimages*)right->NextSameLevel;
}

---

it is complicated I guess because it has to be
of course I have no idea if there is a easier way to do that, as I've said I'm not the one who wrote the program, but it works and that is enough for me

but now to add what I need to add if I don't free those trees when I don't use them anymore I'll run short of memory and since what I've tried to write to free it it doesn't work I'm here to ask some help

I'm sorry again if my previous explanations weren't clear enough

the tree should look like this
http://img223.imageshack.us/my.php?image=treevp7.jpg

I've also tried with this:

Code:

---

void FreeDBimages (ptr,maxlev)
DBimages *ptr;
int maxlev;

{
DBimages *curs,*temp;
int level;
level=0;
curs=ptr;

while(level<maxlev){
  curs=(DBimages*)curs->NextLevel;
  level++;
}

while(curs!=NULL){
  temp=(DBimages*)curs->NextSameLevel;
  FreedVector(curs->point,3);
  FreeiVector(curs->face,2);
  free(curs);
  curs=temp;
}

printf("%d\n",maxlev);

if(maxlev>0)
        FreeDBimages(ptr,maxlev-1);
}

---

freeing level by level starting from the last one, but it does not work

And how does it "not work"?

Quote:

---

Originally Posted by tabstop

And how does it "not work"?

---

i get a segmentation fault

I've tried to do some print on screen to understand why
as it seems it occurs while trying to run a FreedVector(curs->point,3);
and it is not possible to print out that vector point even if curs is not a NULL pointer

So that node apparently doesn't have a point vector? Is that expected? If so, you'll have to deal with that. If not, you should check that you didn't forget to do so?

Quote:

---

Originally Posted by tabstop

So that node apparently doesn't have a point vector? Is that expected? If so, you'll have to deal with that. If not, you should check that you didn't forget to do so?

---

it is not expected and it shouldn't be possible
the vector point is the information of the node without that the node shouldn't even exist

edit
and I find quite strange that if there is no point vector in that node I don't get an error previously in the program while trying to use that vector that don't exist

some news, I don't know if good or bad ones
as it seems if I change the input file to an easier one, it works
or at least it does not give me the segmentation fault

so it might be a problem in the allocation rather than in freeing the memory, am I wrong?

edit

there is a way to check if the memory is freed for real? (to check if the function actually works)

Quote:

---

Originally Posted by stealthisnick

some news, I don't know if good or bad ones
as it seems if I change the input file to an easier one, it works
or at least it does not give me the segmentation fault

so it might be a problem in the allocation rather than in freeing the memory, am I wrong?

edit

there is a way to check if the memory is freed for real? (to check if the function actually works)

---

Most implementations of the C runtime library has some functions that tell you the state of the heap. However, those are unique to the C runtime library, and non-standard, so you'd have to tell us which C library (which compiler) you are using.

--
Mats

Quote:

---

Originally Posted by matsp

Most implementations of the C runtime library has some functions that tell you the state of the heap. However, those are unique to the C runtime library, and non-standard, so you'd have to tell us which C library (which compiler) you are using.

--
Mats

---

well, I run that program on a UNIX station so I have a command to compile and that's it, as far as I know

Quote:

---

Originally Posted by stealthisnick

well, I run that program on a UNIX station so I have a command to compile and that's it, as far as I know

---

That's not quite enough information to tell us what C library you are using, and as it's unique to each C library, we can't tell.

Alternatively, you could make your own malloc/free replacement functions that keep track of how much you've allocated and how much you've freed.

--
Mats

Quote:

---

Originally Posted by matsp

That's not quite enough information to tell us what C library you are using, and as it's unique to each C library, we can't tell.

---

so how can I see what C library I'm using?

Quote:

---

Originally Posted by stealthisnick

so how can I see what C library I'm using?

---

By either telling us what compiler it is, or by looking at the linker stage of the compilation (which you may not normally see, so you may have to change your makefile or such to get that out).

What flavour of Unix is it?

--
Mats

Quote:

---

Originally Posted by matsp

By either telling us what compiler it is, or by looking at the linker stage of the compilation (which you may not normally see, so you may have to change your makefile or such to get that out).

What flavour of Unix is it?

--
Mats

---

as I've said I have no idea what compiler it is, I just have a file with the command

Code:

---

cc -g namefile.c ./lib/sol/*.o -lm -o namefile

---

and that's all I know about how I compile it

about UNIX it should be (actually I'm using it remotely with X-Win32) Solaris OS (if that was the question)

Maybe this page (I didn't actually read much of it) will help:
http://developers.sun.com/solaris/ar...m_library.html

--
Mats

I'll have a look, thanks