0

My code was working perfectly until I tried to implement the unload function, the load, check and size functions all match the staff output for misspelled words, number of words loaded in dictionary etc. After spending many many hours trying to get my head around using recursion for the unload function (Im still very new to programming) and reading countless posts on this site on the topic, my code for the recursive function appears to me to be correct (accornding to the advice given in this forum.)

Valgrind however, doesn't see things the same way. It gives up counting the errors there are so many! (all relating to the unload function lines of the program) I have posted my code below. Could someone please help by giving me some hints about where things are going horribly wrong. More specifically, valgrind reports many many more frees than mallocs, but I don't understand why this is? Thank you in advance.

#include <stdlib.h>
#include <stdbool.h>
#include <ctype.h>
#include "dictionary.h"
#include <stdio.h>
#include <string.h>

// declare trie node data structure
typedef struct node
{
    bool is_word;
    struct node *children[27];
}
node;

// function declaration to unload trie structure from memory
void free_trie(node* ptr);

// function declaration returning pointer to new node whose node pointers 
   are initialized to NULL
node* get_node();

// declare global variable representing sizeof node to minimise running time 
   of program  
int nodesize = sizeof(node);

// declare global variables
FILE *dictptr = NULL;
node *root = NULL;
int element;
int chr;
unsigned int wordcount = 0;


bool check(const char *word)
{
node *trav = root;
int length = strlen(word);

for (int i = 0; i < length; i++)
{
    if (isalpha(word[i]))
    {
        element = (tolower(word[i])) - 'a';

        if (trav->children[element] == NULL)
        {
            return false;
        }
        if (trav->children[element] != NULL)
        {
            trav = trav->children[element];        
        }
    }
    if (word[i] == '\'')
    {
        if (trav->children[26] == NULL)
        {
            return false;
        }
        if (trav->children[26] != NULL)
        {
            trav = trav->children[26];        
        }
    }
    if (word[i+1] == '\0')
    {
        if (trav->is_word == true)
        {
            return true;
        }
    }

    }
    return false;
}


bool load(const char *dictionary)
{
    dictptr = fopen(dictionary, "r");
    if (dictptr == NULL)
    {
        return false;
    }

// intitialise root node and traversal node
root = get_node();

if (root == NULL)
{
    return false;
}

node *trav = root;

// iterate through every characrter in dictionary
for (int chr = fgetc(dictptr); chr != EOF; chr = fgetc(dictptr))
{
    if (isalpha(chr))
    {   // assign each letter to correct node pointer in array, whether 
        upper/lower case
        element = ((tolower(chr)) - 'a');

        // if this elements node pointer is NULL, create new node and have 
        pointer point to it 
        if (trav->children[element] == NULL)
        {
            trav->children[element] = get_node();

            if (trav->children[element] == NULL)
            {
                return false;
            }

            trav = trav->children[element];
        }
        // if pointer != NULL set trav pointer to be equal to this element 
        in array
        // thus iterating through the trie    
        else if (trav->children[element] != NULL)
        {
            trav = trav->children[element];
        }
    }
    // handle apostrophe's in the same way as a character
    if (chr == '\'')
    {
        if (trav->children[26] == NULL)
        {
            trav->children[26] = get_node();

            if (trav->children[26] == NULL)
            {
                return false;
            }

            trav = trav->children[26];
        }
        else if (trav->children[26] != NULL)
        {
            trav = trav->children[26];
        }
    }
    if (chr == '\n')
    {
        // set is_word boolean to true to indicate the completion of a word
        trav->is_word = true;
        // increment wordcount value
        wordcount++; 

        // reset trav pointer to point at root node
        trav = root;
    }
}
fclose(dictptr);
return true;
}


unsigned int size(void)
{
    if (&load == 0)

        return 0;

   else

        return wordcount;
}   


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

    free_trie(root);

    return true;
}



node* get_node()
{
    node* newnode = calloc(1, nodesize);

    return newnode;
}

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

        free(ptr);
    }
}
1

First of all, valgrind is detecting a lot of memory allocations left because the program is erroring out with almost all memory still allocated. So let's move on to the problem.

Let's take a close look at free_trie() and what it does.

void free_trie(node* ptr)
{
    for (int i = 0; i < 27; i++)
    {
        if(ptr->children[i] != NULL)
        {
            free_trie(ptr->children[i]);
        }    
        free(ptr);
    }
}

This is a recursively called function, so there are a number of scenarios that will generate the fail, but let's keep it simple and assume that there are no words that start with a, b or c. So let's see what happens. It will check for child 'a' or 0, find it is null, and will execute free(ptr). It will then circle back, find that child 'b' is null too, and will then try to execute free(ptr) again! This is the double free or corruption error. ptr still contains the same address, which has now bee freed. (free doesn't reset pointers to NULL, it leaves the address data intact in the var, and just releases the memory.)

ptr cannot be freed until all 27 children have been found to be NULL or have been recursively walked and processed. It's a simple fix that I'll let you try to figure out. If you can't leave a comment and I'll help you get it. ;-)

If this answers your question, please click on the check mark to accept. Let's keep up on forum maintenance. ;-)

| improve this answer | |
  • You're 100% right, I just moved the free(ptr); call outside of the for loop and now everything works, no errors from valgrind, and all smilies from check50! Thanks for pinpointing so accurately where I was going wrong, amazing how you can miss something staring you in the face so easily! – adam kirsch Jun 28 '17 at 21:33
  • Yeah, those are usually the ones that'll drive you insane for 3 days. :-) – Cliff B Jun 29 '17 at 4:32

You must log in to answer this question.

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