Unable to deallocate memory for a tree structure.

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:

Code:

---

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 :

Code:

---

/* 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.

Code:

---

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:

Code:

---

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 ? I removed the free statement and then tried to run the function and there were no errors whatsoever. Which means the problem arose because of the free(p) statement.

Code:

---

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

---

should be:

Code:

---

node *next_node = p->next;
free(p);
p = next_node;

---

since you should not be accessing p->next after freeing p.

Quote:

---

Originally Posted by laserlight

Code:

---

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

---

should be:

Code:

---

node *next_node = p->next;
free(p);
p = next_node;

---

since you should not be accessing p->next after freeing p.

---

sorry, i realized it now and fixed it. It was a silly mistake. Unfotunately, my pelles C compiler never reports such dangerous situations. Can you please tell me of some easy to use debugger in windows mode which will give warnings and stuff ? Pelles C has a debugger but it produces enormous amount of illegible assembly code and various stack information.

modified code :

Code:

---

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

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

---

Good windows debugger for C? Microsoft Visual Studio ;D

Quote:

---

Originally Posted by broli86

Can you please tell me of some easy to use debugger in windows mode which will give warnings and stuff ? Pelles C has a debugger but it produces enormous amount of illegible assembly code and various stack information.

---

Compilers can't in general give warnings for a problem like that. Code between deallocation and realocation into the same pointer that may or may not have a dereference in between can be infinitely complex. It's too difficult to prove that it will or will not occur.
It is only at run-time that one could detect such a problem. You just have to be careful and good at debugging.

There are plenty of memory debuggers that will alert you at run time if you attempt to access a variable which you have already freed. They work best when they are part of the compile-time chain (so they can analyse your source code and modify the compilers output to get more information).