Unable to deallocate memory for a tree structure.

[pereges]

Hi, I'm trying to deallocate a kd tree which I created dynamically.
There were no problems
creating the structure and I can access it easily but there is a
problem while trying to free
it. Here's the structure for the a single node in the tree:


typedef struct kdnode_s
{
bbox box; /* Bounding box */
int splitplane; /* -1 for leaf node*/
union
{
struct
{
struct kdnode_s *child[2]; /* Children node */
double split;

}nonleaf;

struct
{
size_t nt;
node *thead; /* Link list */

}leaf;

}info;

}kdnode;


Some other supporting data structures :

/* vector */

typedef struct
{
double coord[3];

}vector;

/* bounding box */

typedef struct
{
vector maxB, minB;

}bbox;

/* link list node */

typedef struct node_s
{
struct node_s *next;
void *data;

}node;


Heres the function I wrote to free the kdtree. I pass the address of
the root node pointer
and traverse the tree until I reach a leaf node which is characterised
by splitplane member
being -1. If it is not -1, then it has values 0,1,2 and it is a
nonleaf node. The leaf node
is freed and then I try to free other nodes as I climb back. Once a
leaf node is freed its
pointer is made NULL. This makes it easier to free other nodes once
their children have
been freed.

void free_kd_tree(kdnode **kd)
{
if (*kd != NULL)
{
if ((*kd)->splitplane == -1)
{
free_list((*kd)->info.leaf.thead);
*kd = NULL;
return ;
}
else
{
free_kd_tree(&(*kd)->info.nonleaf.child[0]);
free_kd_tree(&(*kd)->info.nonleaf.child[1]);

if ((*kd)->info.nonleaf.child[0] == NULL &&
(*kd)->info.nonleaf.child[1] == NULL)
{
free(*kd);
*kd = NULL;
}
}
}
}

In this program the free_list is a routine to free the link list given
its head pointer and this
is how I wrote it:

void free_list(node *head)
{
node *p;

p = head;
while (p != NULL)
{
free(p);
p = p->next;
}
}

For some reason I observed, the free(p) is not able to execute and the
program terminates
at the point without any warning or message. What could be wrong ?

 

[Jens Thoms Toerring]

Hi, I'm trying to deallocate a kd tree which I created dynamically. There
were no problems creating the structure and I can access it easily but
there is a problem while trying to free it. Here's the structure for the a
single node in the tree:

typedef struct kdnode_s
{
bbox box; /* Bounding box */
int splitplane; /* -1 for leaf node*/
union
{
struct
{
struct kdnode_s *child[2]; /* Children node */
double split;

}nonleaf;

struct
{
size_t nt;
node *thead; /* Link list */

}leaf;

}info;

}kdnode;

Some other supporting data structures :

/* vector */

typedef struct
{
double coord[3];
}vector;

/* bounding box */

typedef struct
{
vector maxB, minB;
}bbox;

/* link list node */

typedef struct node_s
{
struct node_s *next;
void *data;
}node;

Heres the function I wrote to free the kdtree. I pass the address of the
root node pointer and traverse the tree until I reach a leaf node which is
characterised by splitplane member being -1. If it is not -1, then it has
values 0,1,2 and it is a nonleaf node. The leaf node is freed and then I
try to free other nodes as I climb back. Once a leaf node is freed its
pointer is made NULL. This makes it easier to free other nodes once their
children have been freed.

void free_kd_tree(kdnode **kd)
{
if (*kd != NULL)
{
if ((*kd)->splitplane == -1)
{
free_list((*kd)->info.leaf.thead);
*kd = NULL;
return ;
}
else
{
free_kd_tree(&(*kd)->info.nonleaf.child[0]);
free_kd_tree(&(*kd)->info.nonleaf.child[1]);

if ((*kd)->info.nonleaf.child[0] == NULL &&
(*kd)->info.nonleaf.child[1] == NULL)

Why is this test necessary? Wouldn't it indicate that there's
a bug somewhere in your tree when this ever should test false?

{
free(*kd);
*kd = NULL;
}
}
}
}

In this program the free_list is a routine to free the link list given
its head pointer and this
is how I wrote it:

void free_list(node *head)
{
node *p;

p = head;
while (p != NULL)
{
free(p);
p = p->next;
}
}

For some reason I observed, the free(p) is not able to execute and the
program terminates at the point without any warning or message. What could
be wrong ?

Not sure if this is the only issue, but here you first free 'p'
and then you dereference it to get at the next pointer. But
using memory you already deallocted is not allowed (even though
you may get away with it often). Store the pointer to the next
element in a temporary variable before you free 'p'.

The other stuff looks ok at a first glance, so I would suspect
that there could be some bug in the code you don't sgow that
creates the linked list.
Regards, Jens

 

[pereges]

if ((*kd)->info.nonleaf.child[0] == NULL &&
(*kd)->info.nonleaf.child[1] == NULL)

Why is this test necessary? Wouldn't it indicate that there's
a bug somewhere in your tree when this ever should test false?

This test is absolutely necessary because you can detect a leaf node
with its splitplane member being -1. But when both the children of a
non leaf node have been freed, then that non leaf node must also be
freed. It is as good as a leaf node. You can't use the splitplane
criteria to free it because the tree was built in such a way that for
non leaf nodes the split plane value is always 0,1,2 not -1. So what I
do is when I free a leaf node, I make the value of that pointer null :

if ((*kd)->splitplane == -1)
{
free_list((*kd)->info.leaf.thead);
*kd = NULL;
return ;
}

Once both children of a nonleaf node become null, it fits the
criterion for deletion. Hence the check.

Not sure if this is the only issue, but here you first free 'p'
and then you dereference it to get at the next pointer. But
using memory you already deallocted is not allowed (even though
you may get away with it often). Store the pointer to the next
element in a temporary variable before you free 'p'.

The other stuff looks ok at a first glance, so I would suspect
that there could be some bug in the code you don't sgow that
creates the linked list.

oops, that was probably the problem. I changed it to the following and
it works now :

void free_list(node *head)
{
node *p;

while (head != NULL)
{
p = head->next;
free(head);
head = p;
}
}

 

[pereges]

Unfotunately, my pelles C compiler never reports such dangerous
situations. Can some one please tell me of some easy to use debugger
in windows mode which will give warnings and stuff ? I know valegrind
is a good one but its for linux. Pelles C has a debugger but it
produces enormous amount of illegible assembly code and various stack
information. I feel extremely frustrated because of these bugs.

 

[santosh]

Unfotunately, my pelles C compiler never reports such dangerous
situations. Can some one please tell me of some easy to use debugger
in windows mode which will give warnings and stuff ? I know valegrind
is a good one but its for linux. Pelles C has a debugger but it
produces enormous amount of illegible assembly code and various stack
information. I feel extremely frustrated because of these bugs.

Have you tried static code checking tools like PC-Lint or splint? They
would've caught the mistake you made.

 

[Bartc]

Have you tried static code checking tools like PC-Lint or splint? They
would've caught the mistake you made.

[original code..]

free(p);
p = p->next;

It's funny but setting p to NULL after the free() may well have helped here,
even though there was an opinion on clc a couple of weeks back that this was
a waste of time.

In fact, the error would then have been so obvious then no lint program or
even compilation would have been necessary:

free(p);
p=NULL;
p = p->next;

On following code, without the root=NULL, 2 compilers produced code that
seemed to work; 2 had code that hung. With root=NULL in place, all crashed
with an error message.

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

typedef struct {
int data;
void *next;
} node;

int main(void) {
int i;
node *p, *q, *r, *root;

root=NULL;

/* Create linked list */
for (i=1; i<=10; ++i) {
p=malloc(sizeof(node)); /* Assume this works */
p->data=i*100;
p->next=root;
root=p;
}

/* Print it */
p=root;
while (p) {
printf("Item: %d\n",p->data);
p=p->next;
}

/* Free it */
while (root) {
free(root);
// root=NULL;
root=root->next;
}
}

 

[santosh]

Have you tried static code checking tools like PC-Lint or splint?
They would've caught the mistake you made.

[original code..]

free(p);
p = p->next;

It's funny but setting p to NULL after the free() may well have helped
here, even though there was an opinion on clc a couple of weeks back
that this was a waste of time.

In fact, the error would then have been so obvious then no lint
program or even compilation would have been necessary:

free(p);
p=NULL;
p = p->next;

As was noted earlier, the C standard does not require null pointer
accesses to be caught or diagnosed, though many systems do so. But the
case where all pointers in a program are either valid or NULL is
simpler (if nothing else), than the case where they could, in addition,
have indeterminate values.

Setting pointers to NULL when they have nothing to point at is a good
debugging practise, I agree, but it's no substitute for correct code.

<snip>