# How to free a dynamically allocated kdtree ?

This topic is 3857 days old which is more than the 365 day threshold we allow for new replies. Please post a new topic.

## Recommended Posts

Hi, I have created a kdtree (dynamically) using median cut approach and now i want to free it. Here's my data structure :
typedef struct kdnode_s
{
bbox box; /* Bounding box */
char split_plane; /* 0:- x, 1:- y, 2 : z  -1 : leaf*/
union
{
struct
{
struct kdnode_s *child[2]; /* two child nodes
double split; /* split point */

}nonleaf;

struct
{
unsigned long nt; /* no: of triangles in node */
triangle **tpa; /* triangle list */

}leaf;

}u;

}kdnode;
I tried to think over a few methods like postorder traversal etc but it won't work in this scenario. what to do ?

##### Share on other sites
You could do it with a recursive function to traverse the tree depth first, then freeing the nodes as it climbs back up.

Something like:

void free_kd_tree(kdnode *node){    int is_leaf = node->split_pane == -1;    if (is_leaf)    {        free_trangles(node->u.leaf.tpa, node->u.leaf.nt);    }    else    {        free_kd_tree(node->u.nonleaf.child[0]);        free_kd_tree(node->u.nonleaf.child[1]);    }    free(node);}

If I were using your structure, I'd make the union anonymous and probably rename nonleaf to composite, or group.

##### Share on other sites
Quote:
 Original post by dmatterYou could do it with a recursive function to traverse the tree depth first, then freeing the nodes as it climbs back up.Something like:void free_kd_tree(kdnode *node){ int is_leaf = node->split_pane == -1; if (is_leaf) { free_trangles(node->u.leaf.tpa, node->u.leaf.nt); } else { free_kd_tree(node->u.nonleaf.child[0]); free_kd_tree(node->u.nonleaf.child[1]); } free(node);}

Thanks, but shouldn't there be a if (node != NULL) test in the body of your function.

I have also tried an implementation, not sure if it would work though:

void kill kd tree(kdnode *kd){    if(*kd != NULL)    {        if ((*kd)->split_plane == -1)        {            kill_kd_tree(*kd);            *kd = NULL;        }        else        {            kill_kd_tree(&kd->u.nonleaf.child[0]);            kill_kd_tree(&kd->u.nonleaf.child[1]);                    if ((*kd)->u.nonleaf.child[0] == NULL             && (*kd)->u.nonleaf.child[1] == NULL)            {                kill_kd_node(*kd);                *kd = NULL;            }        }    }}

Quote:
 If I were using your structure, I'd make the union anonymous and probably rename nonleaf to composite, or group.

I understand but I'm using C langauge and it seems anonymous structures and unions within structures are only allowed by *some* implementations. It is not considered as standard.

##### Share on other sites
Quote:
 Original post by broli86Thanks, but shouldn't there be a if (node != NULL) test in the body of your function.

Yeah, I left out error checking...

void free_kd_tree(kdnode *node){    if (node == NULL)        return;    /* same as before */}

The reason I left this out is two fold: one for clarity, and two because the above check is a bit sub-optimal if you can guarantee your kdtree's composite nodes will never have null children.

Quote:
 I have also tried an implementation, not sure if it would work though:

There are allusions to a working function there but not quite.
Two things I notice are that, based on your dereferences, you perhaps meant to make *kd a pointer to a pointer, **kd. Also if the split_pane is -1 then you get stuck in a recursive loop with no base case to stop it.

Quote:
 I'm using C langauge and it seems anonymous structures and unions within structures are only allowed by *some* implementations. It is not considered as standard.

Seems that anonymous structures and unions are actually a C++ feature - I had thought they were a carry-over from C or at least in C99, oh well.

##### Share on other sites
Quote:
 Original post by broli86I understand but I'm using C langauge and it seems anonymous structures and unions within structures are only allowed by *some* implementations. It is not considered as standard.

I don't know of any modern C compilers which don't allow it. It may not be in the C89 standard, but it's a de facto standard.

##### Share on other sites
Quote:
Original post by dmatter
Quote:
 Original post by broli86Thanks, but shouldn't there be a if (node != NULL) test in the body of your function.

Yeah, I left out error checking...

void free_kd_tree(kdnode *node){    if (node == NULL)        return;    /* same as before */}

The reason I left this out is two fold: one for clarity, and two because the above check is a bit sub-optimal if you can guarantee your kdtree's composite nodes will never have null children.

Quote:
 I have also tried an implementation, not sure if it would work though:

There are allusions to a working function there but not quite.
Two things I notice are that, based on your dereferences, you perhaps meant to make *kd a pointer to a pointer, **kd. Also if the split_pane is -1 then you get stuck in a recursive loop with no base case to stop it.

Quote:
 I'm using C langauge and it seems anonymous structures and unions within structures are only allowed by *some* implementations. It is not considered as standard.

Seems that anonymous structures and unions are actually a C++ feature - I had thought they were a carry-over from C or at least in C99, oh well.

Yes, its a double pointer i.e. **kd sorry for that mistake. IF that is solved, I think it should work.

##### Share on other sites
Quote:
 Original post by SneftelI don't know of any modern C compilers which don't allow it. It may not be in the C89 standard, but it's a de facto standard.

I use Pelles C and it doesn't allow that.

• ### What is your GameDev Story?

In 2019 we are celebrating 20 years of GameDev.net! Share your GameDev Story with us.

• 28
• 16
• 10
• 10
• 11
• ### Forum Statistics

• Total Topics
634113
• Total Posts
3015570
×