freeing is not freeing !

This is a discussion on freeing is not freeing ! within the C Programming forums, part of the General Programming Boards category; Hi everyone, wondering if a malloc genius could help me here.. I'm working with a trie structure in order to ...

  1. #1
    Registered User
    Join Date
    Oct 2009
    Posts
    3

    freeing is not freeing !

    Hi everyone,

    wondering if a malloc genius could help me here..

    I'm working with a trie structure in order to represent a dictionary. So each node contains a letter, and if the words 'cats' 'catch' and 'dog' were inserted the trie would look like this:

    Code:
                                        -(dummy root)
                                        |
                                        |
                                       (d)  ---  (c)
                                        |           |
                                        |           |
                                       (o)        (a)
                                        |           |
                                        |           |
                                       (g)        (t)
                                                    |
                                                    |
                                                   (c)  ---  (s)
                                                    |
                                                    |
                                                   (h)
    - **so nodes g, h, and s have children and sibling pointers that point to NULL.

    I've had issues writing a function which deletes the entire trie. I tried to write a recursive function, but would get double free errors, because everytime it found a dead end (like the letter 's'), it would call free(node) to delete it, but 's' wouldn't leave the list. The error then occured because the function traversed the list again to find the next dead end in that path, and came across 's' again and tried to free it again.

    So i took to writing a non-recursive function. The function works, in that it finds a dead end, makes it's parent or previous sibling point to NULL, then frees the node, an in the end I end up with an 'empty list'. But valgrind is still complaining that I'm not actually freeing anything.
    The only free which works seems to work is when I call free(root) at the very end. And root is a global var.

    Any suggestions on why its 'freeing' but not freeing ?

    The non-recursive function is below. I know its very hacky, I was just trying to locate the bug.

    Code:
    void freeTrie (){
    
    dictLink header = root;
      if((root != NULL)&&(root->child != NULL)) {
        dictLink curr = NULL;
        dictLink temp = NULL;
        while((header->child->sibling != NULL)&&(header->child->child != NULL)) { //because this will be the last non-dummy node to be deleted.
          
          curr = root->child;      
          while((curr->sibling != NULL)) {
            if((curr->sibling->sibling == NULL)&&(curr->sibling->child==NULL)) {
              temp = curr;
            }  
            curr = curr->sibling;
            if(temp != NULL) {
              temp->sibling = NULL;
            }
          }
          while(curr->child != NULL) {
            if((curr->child->sibling == NULL)&&(curr->child->child==NULL)) {
              temp = curr;
            } 
            curr = curr->child;
            if(temp != NULL) {
              temp->child = NULL;
            }  
          }
          if((curr->child == NULL)&&(curr->sibling == NULL)&&(curr != root->child)) {
          free(curr);   //IS NOT ACTUALLY FREEING (BUT COMPILER DOESN'T COMPLAIN)
          curr = NULL;    
          }      
      }
      free(curr);
      curr = NULL;
      root->child = NULL;
      free(root);
      root = NULL; 
      }
      
    }

  2. #2
    and the Hat of Guessing tabstop's Avatar
    Join Date
    Nov 2007
    Posts
    14,185
    You correctly identify (and even italicize!) the important point -- you must make the parent or sibling point to NULL. Unfortunately for you, you never even come close to actually doing so. If you want to get rid of a leaf node, you need to walk curr to be the next-to-last object, free (curr->sibling) or free (curr->child) as the case may be and then set curr->sibling or curr->child to NULL.

  3. #3
    Registered User
    Join Date
    Oct 2009
    Posts
    3
    Yes!

    You are a genius. Thank you for the advice.

  4. #4
    Algorithm Dissector iMalc's Avatar
    Join Date
    Dec 2005
    Location
    New Zealand
    Posts
    6,305
    That is extremely over complicated, even for an iterative solution.
    Here is a simple recursive solution that deletes your trie:
    Code:
    void freeTrie(dictLink *nPtr) {
        dictLink n = *nPtr;
        if (n == NULL)
            return;
        freeTrie(&n->child);
        freeTrie(&n->sibling);
        free(n);
        nPtr = NULL;
    }
    Call it like this:
    Code:
    freeTrie(&root);
    Hint: Recursive solutions are virtually always simpler.
    I would personally probably implement a hybrid recursive/iterative solution, which is barely longer than the recursive solution I just posted, and yet barely less efficient than a purely iterative solution.

    What's more is that although you are representing this as a trie with horizontal and vertical links, it is structurally no different from a binary tree. Each node has up to two links, and no node can point to a predecessor (i.e. it is not a graph).
    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"

Popular pages Recent additions subscribe to a feed

Similar Threads

  1. Freeing a char**
    By +Azazel+ in forum C Programming
    Replies: 3
    Last Post: 02-26-2008, 06:27 PM
  2. Freeing Linked Lists
    By mrpickle in forum C Programming
    Replies: 4
    Last Post: 01-21-2004, 06:57 PM
  3. Debug Assertion error when freeing memory
    By foniks munkee in forum C Programming
    Replies: 2
    Last Post: 02-28-2002, 04:57 PM
  4. freeing list that gets nodes from block
    By Unregistered in forum C Programming
    Replies: 2
    Last Post: 02-01-2002, 09:16 AM
  5. freeing list
    By Unregistered in forum C Programming
    Replies: 2
    Last Post: 01-31-2002, 05:45 PM

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21