Re: Unable to deallocate memory for a tree structure.

pereges <Broli00@xxxxxxxxx> wrote:
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
--
\ Jens Thoms Toerring ___ jt@xxxxxxxxxxx
\__________________________ http://toerring.de
.

Relevant Pages

  • Re: hacker challenge - traverse a list
    ... Here is a little challenge - print the contents of a binary tree ... I assume there are no up links, otherwise the algorithm is trivial. ... space hence unbounded number of bits in a pointer? ... Left branch *not* leaf, rotate: ...
    (comp.programming)
  • Re: question of style
    ... end of the day the quality of the code depends more on the quality of ... or the equivalent null pointer exceptions in Java, C, or whatever? ... But you have implemented a mutable tree. ...     def get: ...
    (comp.lang.python)
  • Re: Help me come up with a few and simple programming challenges
    ... >Dave Vandervies wrote: ... >> language, I'd probably pass around a pointer to the list's head pointer ... >(define (sublist tree lo hi) ...
    (comp.lang.scheme)
  • Re: Reading XML stream using unmanaged c++
    ... You don't need a back pointer to implement tree structures. ... but a back pointer is a handy thing to have when using a DOM node. ... XML is metadata, but an XML document is an XML metadata structure with actual data ...
    (microsoft.public.vc.mfc)
  • Re: hacker challenge - traverse a list
    ... void deleteEl; ... mangle and print the binary tree, then demangle it back to its ... node * tmptop = treetop; ... The basic idea is to convert the right pointer into a directly ordered ...
    (comp.programming)