Unable to deallocate memory for a tree structure.

Discussion in 'C Programming' started by pereges, Jul 6, 2008.

  1. pereges

    pereges Guest

    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 ?
     
    pereges, Jul 6, 2008
    #1
    1. Advertising

  2. pereges <> 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 ___
    \__________________________ http://toerring.de
     
    Jens Thoms Toerring, Jul 6, 2008
    #2
    1. Advertising

  3. pereges

    pereges Guest

    On Jul 6, 11:01 pm, (Jens Thoms Toerring) wrote:

    > > 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, Jul 6, 2008
    #3
  4. pereges

    pereges Guest

    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.
     
    pereges, Jul 6, 2008
    #4
  5. pereges

    santosh Guest

    pereges wrote:

    > 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.
     
    santosh, Jul 7, 2008
    #5
  6. pereges

    Bartc Guest

    "santosh" <> wrote in message
    news:g4rugj$r5b$...
    > pereges wrote:
    >
    >> 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.


    [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;
    }
    }

    --
    Bartc
     
    Bartc, Jul 7, 2008
    #6
  7. pereges

    santosh Guest

    Bartc wrote:

    >
    > "santosh" <> wrote in message
    > news:g4rugj$r5b$...
    >> pereges wrote:
    >>
    >>> 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.

    >
    > [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>
     
    santosh, Jul 7, 2008
    #7
    1. Advertising

Want to reply to this thread or ask your own question?

It takes just 2 minutes to sign up (and it's free!). Just click the sign up button to choose a username and then you can ask your own questions on the forum.
Similar Threads
  1. Eric Lilja
    Replies:
    2
    Views:
    3,651
    Victor Bazarov
    Mar 14, 2005
  2. Replies:
    20
    Views:
    1,380
    Heiko Wundram
    May 12, 2006
  3. Tony Johansson
    Replies:
    3
    Views:
    337
    Old Wolf
    Aug 13, 2005
  4. Replies:
    2
    Views:
    359
    Ron Natalie
    Apr 3, 2008
  5. alessio211734

    handle deallocate memory on return

    alessio211734, Jun 30, 2009, in forum: C++
    Replies:
    3
    Views:
    585
    Thomas J. Gritzan
    Jul 3, 2009
Loading...

Share This Page