Pset5: Not able to free allocated heap space in dictionary.c load function

Question

I have implemented all 4 functions and the program seems to be working without issues. Here's the result for austinpowers.txt:

WORDS MISSPELLED:     644
WORDS IN DICTIONARY:  143091
WORDS IN TEXT:        19190
TIME IN load:         0.05
TIME IN check:        0.63
TIME IN size:         0.00
TIME IN unload:       0.00
TIME IN TOTAL:        0.68

The code also passes all the check50 conditions.

But the compiler gives me an error(use of undeclared identifier 'new_node') when I try to free the space allocated using malloc for new_node at the end of the load function. And when I try to free it inside the while loop, it compiles but takes far too long to execute.

I tried running it under valgrind without freeing new_node and no leaks were detected. There does not seem to be any problem when I don't free new_node. I'm not able to understand how this is working without any leaks. Am I overlooking any free operations elsewhere in the program that takes care of this?

Here's my code for dictionary.c:

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

#include "dictionary.h"

node* hashtable[26];
unsigned int counter = 0;

/**
 * Returns true if word is in dictionary else false.
 */
bool check(const char* word)
{
    char temp_word[LENGTH+1];
    strcpy(temp_word, word);
    node* cursor = hashtable[hash(temp_word)];

    while(cursor!=NULL)
    {
        if(strcmp(cursor->word, temp_word)==0)
        {
            return true;
        }
        cursor = cursor->next;
    }
    return false;
}

/**
 * Loads dictionary into memory.  Returns true if successful else false.
 */
bool load(const char* dictionary)
{
    for(int i = 0; i < 26; i++)
    {
        hashtable[i] = NULL;
    }

    int hash_index;
    char load_word[LENGTH+1];
    FILE* load_ptr = fopen(dictionary, "r");

    while(fscanf(load_ptr, "%s", load_word)!=EOF)
    {
        counter++;
        node* new_node = malloc(sizeof(node));
        if(new_node==NULL)
        {
            printf("Out of heap memory");
            return false;
        }

        strncpy(new_node->word, load_word, sizeof(load_word));
        hash_index = hash(new_node->word);
        if(insert(new_node, hash_index)==false)
            return false;
    }

    free(new_node);//program works when this line is avoided.
    fclose(load_ptr);
    return true;
}

/**
 * Returns number of words in dictionary if loaded else 0 if not yet loaded.
 */
unsigned int size(void)
{
    return counter;
}

/**
 * Unloads dictionary from memory.  Returns true if successful else false.
 */
bool unload(void)
{
    for(int i = 0; i < 26; i++)
    {
        node* cursor = hashtable[i];

        while(cursor!=NULL)
        {
            node* temp = cursor;
            cursor = cursor->next;
            free(temp);
        }
    }
    return true;
}

/**
 * Inserts a new word into the appropriate position in the hashtable.
 */
bool insert(struct node* new_node, int index)
{
    if(hashtable[index]==NULL)
    {
        new_node->next = NULL;
        hashtable[index] = new_node;
        return true;
    }

    else
    {
        new_node->next = hashtable[index];
        hashtable[index] = new_node;
        return true;
    }

    return false;
}

/**
 * The hash function.
 */
int hash(char word[LENGTH+1])
{
    for(int i = 0; i < strlen(word); i++)
    {
        word[i] = toupper(word[i]);
    }

    return (word[0] - 'A') % 26;
}

P.S: I am also having a hard time trying to figure out exactly why before and after are passed by reference in speller.c. Any pointers regarding this would also be much appreciated.

Answer 1

Simply put, new_node should not be freed in load(). Think about what is happening. With each pass through the while loop, a new node is created, a word is read from the dictionary file and copied into the new_node, and the new_node is inserted into the tree. By calling free(new_node) at the end of load, you would be trying to free the last node that was created, which now holds the last word in the dictionary. This would delete the last word from the tree.

Remember, the pointer variable new_node is used over and over, and there's no need to destroy a pointer variable itself. Generally speaking, nothing should need to be freed in load(), if it's done right. That's what unload() is for. ;-)

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