Speller Valgrind Issues

Question

I've been trying to finish up the speller pset, and while everything works well, I keep getting a memory leak. When I rerun check50 with --log, I get:

checking for valgrind errors...
    56 bytes in 1 blocks are definitely lost in loss record 1 of 3: (file: dictionary.c, line: 132)
    56 bytes in 1 blocks are definitely lost in loss record 2 of 3: (file: dictionary.c, line: 139)
    336 bytes in 6 blocks are definitely lost in loss record 3 of 3: (file: dictionary.c, line: 35)

My code is:

// Implements a dictionary's functionality

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

// Represents a node in a hash table
typedef struct node
{
    char word[LENGTH + 1];
    struct node *next;
}
node;

// Number of buckets in hash table
const unsigned int N = 26;

// Hash table
node *table[N];

//variable to store the number of words
unsigned int wordcount = 0;

// Returns true if word is in dictionary else false
bool check(const char *word)
{
    //Hash the word to get the index value
    int index = hash(word);

    //Create a pointer to search at that index
    node *cursor = malloc(sizeof(node));
    //Immediately check if a correct node is made
    if (cursor == NULL)
    {
        return false;
    }

    //Loop to search
    for (cursor = table[index]; cursor != NULL; cursor = cursor->next)
    {
        if (strcasecmp(cursor->word, word) == 0)
        {
            return true;
        }
    }
    free(cursor);
    return false;
}
-----------------------------------------------------------------------------------------
// Hashes word to a number
unsigned int hash(const char *word)
{
    if (islower(word[0]))
    {
        return ((int) word[0] - 97);
    }
    else
    {
        return ((int) word[0] - 65);
    }
}
----------------------------------------------------------------------------------------
// Loads dictionary into memory, returning true if successful else false
bool load(const char *dictionary)
{
    //Making a file pointer to open file
    FILE *file = fopen(dictionary, "r");

    //Checking if file is NULL
    if (!file)
    {
        printf("Could not open file\n");
        return false;
    }

    //variable to store the characters of a word
    char part[LENGTH + 1];

    //Scanning from the file until you reach EoF
    while(fscanf(file, "%s", part) != EOF)
    {
        //Create a node to store that word
        node *new_node = malloc(sizeof(node));
        //Immediately check if return NULL
        if (new_node == NULL)
        {
            return false;
        }

        //Copying from word to node
        strcpy(new_node->word, part);
        wordcount++;

        //Figuring out the index to know where to insert node
        int index = hash(part);

        //INSERTING NODE
        //If it isn't pointing to anything
        if (table[index] == NULL)
        {
            //Point at what n is pointing at
            table[index] = new_node;
            new_node->next = NULL;
        }
        //If it is already pointing at something
        else
        {
            //Point new node's next at what original table is pointing at
            new_node->next = table[index];
            //Point table at what n was originally addressing
            table[index] = new_node;
        }
    }
    fclose(file);
    return true;
}
----------------------------------------------------------------------------------------------
// Returns number of words in dictionary if loaded else 0 if not yet loaded
unsigned int size(void)
{
    return wordcount;
}
----------------------------------------------------------------------------------------------
// Unloads dictionary from memory, returning true if successful else false
bool unload(void)
{
    //Node pointer 1
    node *cursor = malloc(sizeof(node));
    if (cursor == NULL)
    {
        return false;
    }

    //Node pointer 2
    node *temp = malloc(sizeof(node));
    if (temp == NULL)
    {
        return false;
    }

    //For every bucket in the hashtable
    for (int i = 0; i < N; i++)
    {
        if (table[i] != NULL)
        {
            //temp points to what table points to
            temp = table[i];
            //cursor points to what table points to
            cursor = table[i];

            do
            {
                //cursor goes to the next node
                cursor = cursor->next;
                free(temp);
                temp = cursor;
            } while (cursor != NULL);
        }
    }
    free(cursor);
    return true;
}

I'm not sure why I'm getting errors for the malloc() lines if I've used the free ones after - I could be missing something. Any help is appreciated!

Answer 1

The problem lies in each of the malloc's in check and unload. All three node pointer vars that are created are used to process existing nodes, yet all three are initialized with malloc calls. They should be set/initialized to NULL instead.

This is a common error by new programmers. They believe that memory must be allocated to any pointer that is created. This is not true.

Pointer creation and initialization are two different and distinct processes, but almost always done in the same line of code. When a pointer is created it is always a best practice to initialize it. If you don't initialize it, the pointer will contain whatever garbage data that was in the physical memory at the time it is created.

Here's the important part, relevant to your problems. A pointer can be initialized in one of 3 ways.

1. It can have memory malloc'd to it.
2. It can have an existing memory address assigned to it.
3. It can be set to NULL.

In all three cases, the pointers should ALL be set to NULL. (But, not new_node in load.) The check for null that immediately follows each case should be removed too.

Since this code allocates memory to these pointers and then immediately reassigns the pointers, that memory that was just assigned is lost, creating 3 separate leaks.

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

Answer 2

I believe there's still an error here, though I'm not entirely sure in this case:

for (int i = 0; i < N; i++)
{
    if (table[i] != NULL)
    {
        //temp points to what table points to
        temp = table[i];
        //cursor points to what table points to
        cursor = table[i];

        do
        {
            //cursor goes to the next node
            cursor = cursor->next;
            free(temp);
            temp = cursor;
        } while (cursor != NULL);
    }
}

Basically, I think you are setting variables in the incorrect order. First of all, since you are going to be updating temp based on cursor, this line:

temp = table[i];

is unnecesary. Secondly, I think

temp = cursor;

should be the first thing on the do while loop. Let me know if it works, if not I'll look at the rest of the code.