1

all I understand about the unload function is that I should traverse every children node in a node with a loop and check if they point to NULL. if so ,the node will be freed and make it point to NULL.if we found a children node that doesn't point to null, I call the recursive function again. at the end, root points to NULL. I'm using a trie structure a dictionary and the root is a global pointer. the problem is that the function doesn't work properly . valgrind shows me that i have 14 alloc and 13 frees. so here's the recursive function and the unload function

  /**
  *free nodes of dictionary
  *
  */
  void free_memory(node* current_node)
  {
      for(int i = 0 ; i < 27 ; i++)
       {
           if(current_node->children[i] != NULL)
           {
               free_memory(current_node->children[i]);       
           }

       }
      free(current_node);

      return;    

  }

/**
* Unloads dictionary from memory.  Returns true if successful else false. 
*/
   bool unload(void)
  {    

    free_memory(root);
    root = NULL;


    return true ;
    fclose(dic);
  }

and that's the trie structure

  typedef struct node
  {
      bool is_word;
      struct node* children[27];

  }
  node;
  node* root;

valgrind shows me this enter image description here

  • Are your nodes initialized with all elements of .children NULL? – Sam Gerber Sep 21 '15 at 13:39
  • yes i used calloc instead of malloc to allocate memory – kawegan Sep 21 '15 at 14:29
  • I think maybe the issue is that setting current_node to NULL may not actually set temp to NULL. I believe current_node is a separate pointer, with scope only in free_memory(), that is set to point to the same thing as temp. – Sam Gerber Sep 21 '15 at 14:40
  • current_node is just a parameter in free_memory(). and i passed temp as an argument when i called free_memory() in unload(). i don't see anything wrong with that. – kawegan Sep 21 '15 at 14:47
  • Did you close your dictionary file? Can that be the 14th alloc that wasn't freed? – Sam Gerber Sep 21 '15 at 15:36
2

Ok, a couple of notes first to clear the field. Starting from easy:

According to man 3 free:

The free() function frees the memory space pointed to by ptr, which must have been returned by a previous call to malloc(), calloc(), or realloc(). Otherwise, or if free(ptr) has already been called before, undefined behavior occurs. If ptr is NULL, no operation is performed.

It is nowhere said that when the memory pointed to by ptr is free()d, ptr is also set to NULL. ptr will keep pointing to this place in memory even though the memory has been free()d.

Now as you see you have declared root as node *. So root is a pointer to a node, not a node itself.. In your unload() you make a node* temp point to root. What this means exactly, is that now temp points to the same point in heap root points. They are not the same pointers. If I make temp point to NULL, root will be still pointing at the same place in heap, it won't get NULL too. That's why, when you pass temp in free_memory(), even though that pointer, passed by value, points to NULL, the temp in unload() still points where root points. Let me make it a little more clear.

  • Let's say root points at 0x5202040 (in my PC it really does)
  • In unload() you make a pointer temp that points at 0x5202040 too.
  • When you pass temp to free_memory(), a copy of temp is made let's call it temp_copy (although you refer to it as temp) and that too points at 0x5202040.
  • Now at the end of free_memory(), you free() the memory pointed to by temp_copy() and you make temp_copy point to NULL.

But still after all these, temp and root both still point at 0x5202040. That's why your condition if (temp == NULL) is false.

I integrated your unload() function in place of mine, and I used a dictionary with the words cat and caterpillar inside. valgrind reports:

==3674== HEAP SUMMARY:
==3674==     in use at exit: 0 bytes in 0 blocks
==3674==   total heap usage: 13 allocs, 13 frees, 3,568 bytes allocated
==3674== 
==3674== All heap blocks were freed -- no leaks are possible
==3674== 
==3674== For counts of detected and suppressed errors, rerun with: -v
==3674== ERROR SUMMARY: 0 errors from 0 contexts (suppressed: 0 from 0)

So you allocate one more time somewhere in your code and you don't free() that memory. Maybe somewhere inside load()? To see where this allocation is happening, run:

valgrind --leak-check=full --show-leak-kinds=all ./speller [dictionary] [text]

replacing [dictionary] and [text] of course.

So after all, your unload() works great, if you change the following:

  • Remove the node* temp = root; from your unload()
  • Call free_memory() by free_memory(root). You get rid of one pointer you don't really need.
  • After that make root = NULL. Don't worry. If free_memory() doesn't free all nodes and you lose them because of that, valgrind will let you know. But free_memory() does work.
  • Change if (temp == NULL) to if (root == NULL)
  • Inside free_memory() lose the current_node = NULL;. It's just a copy of the pointer passed in the function, so it does nothing meaningful.

Let me know if you pinpoint your problem or you need more advice.


If this answers your question please accept it by clicking the gray check-mark to the left, so that it becomes green. You can also vote it up by pressing the up arrow above the check-mark. And don't forget to keep coding!

| improve this answer | |
  • Much clearer! Thanks! – Sam Gerber Sep 22 '15 at 1:34
  • you say that when I pass temp to free_memory(), a copy of temp is made but pointers are not passed by value they're only passes by reference .so using temp to traverse the trie and free memory will affect root too because i passed the address of both.they're the same thing – kawegan Sep 22 '15 at 8:53
  • 1
    No, that's wrong. Pointers too are passed by value. Don't confuse the pointer with the memory it points to. If I create an int a and store its address on a pointer int* ptr = &a, and then pass ptr to a function, a copy of ptr is made, so you have a int* ptr_copy = ptr. So ptr_copy points to the same memory as ptr does, but it's not the same pointer. – ChrisG Sep 22 '15 at 9:14
2

Check that you've closed your dictionary file.

Passing temp to free_memory() might not change temp to NULL. (Hopefully someone smarter can confirm via comments, or a better answer)

bool unload(void)
{    
     node* temp = root;
     free_memory(temp);
     if ( temp == NULL)
     {
         return true;
     }
     else
     {
         return false;
     }
}

Perhaps change free_memory() to node* type and make it return NULL; when it hits the end:

 node* free_memory(node* current_node)
 {
     for(int i = 0 ; i < 27 ; i++)
     {
        if(current_node->children[i] != NULL)
        {
            current_node->children[i] = free_memory(current_node->children[i]);       
        }

    }
    free(current_node);
    return NULL;    
 }

Then just update unload() to:

bool unload(void)
{    
     node* temp = root;
     temp = free_memory(temp);
     if ( temp == NULL)
     {
         return true;
     }
     else
     {
         return false;
     }
}

Then see how it goes in valgrind?

HTH


If this answers your question please accept it by clicking the gray check-mark to the left, so that it becomes green. You can also vote it up by pressing the up arrow above the check-mark

| improve this answer | |

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .