Thread: Unable to deallocate memory for a tree structure.

  1. #1
    Registered User
    Join Date
    Apr 2008
    Posts
    87

    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.

  2. #2
    C++ Witch laserlight's Avatar
    Join Date
    Oct 2003
    Location
    Singapore
    Posts
    28,413
    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 Bjarne Stroustrup (2000-10-14)
    I get maybe two dozen requests for help with some sort of programming or design problem every day. Most have more sense than to send me hundreds of lines of code. If they do, I ask them to find the smallest example that exhibits the problem and send me that. Mostly, they then find the error themselves. "Finding the smallest program that demonstrates the error" is a powerful debugging tool.
    Look up a C++ Reference and learn How To Ask Questions The Smart Way

  3. #3
    Registered User
    Join Date
    Apr 2008
    Posts
    87
    Quote Originally Posted by laserlight View Post
    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;
        }
    }

  4. #4
    Registered User
    Join Date
    Jul 2008
    Posts
    22
    Good windows debugger for C? Microsoft Visual Studio ;D

  5. #5
    Algorithm Dissector iMalc's Avatar
    Join Date
    Dec 2005
    Location
    New Zealand
    Posts
    6,318
    Quote Originally Posted by broli86 View Post
    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.
    My homepage
    Advice: Take only as directed - If symptoms persist, please see your debugger

    Linus Torvalds: "But it clearly is the only right way. The fact that everybody else does it some other way only means that they are wrong"

  6. #6
    Registered User
    Join Date
    Jul 2008
    Posts
    26
    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).

Popular pages Recent additions subscribe to a feed

Similar Threads

  1. Binary Tree Search
    By C++Newbie in forum C++ Programming
    Replies: 7
    Last Post: 04-05-2011, 01:17 AM
  2. Deallocate Memory and reuse pointer
    By appleGuy in forum C++ Programming
    Replies: 9
    Last Post: 06-20-2007, 11:07 AM
  3. Manipulating the Windows Clipboard
    By Johno in forum Windows Programming
    Replies: 2
    Last Post: 10-01-2002, 09:37 AM
  4. Serial Communications in C
    By ExDigit in forum Windows Programming
    Replies: 7
    Last Post: 01-09-2002, 10:52 AM
  5. Array, Linked List, or Binary Tree?
    By Unregistered in forum C Programming
    Replies: 6
    Last Post: 01-05-2002, 10:07 PM