Pset5 speller getting valgrind error

Question

My code

// Implements a dictionary's functionality

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

#include "dictionary.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 = 65536;

// Hash table
node *table[N];



// Intializing int variable to keep track of number of words
int word_count = 0;

// Returns true if word is in dictionary else false
bool check(const char *word)
{
    char word_copy[LENGTH + 1];
    int n = strlen(word);
    for (int i = 0; i < strlen(word); i++)
    {
        word_copy[i] = word[i];
    }

    word_copy[n] = '\0';

    int h = hash(word);

    if (table[h] == NULL)
    {
        return false;
    }
    node *cursor = table[h];

    while (cursor != NULL)
    {
        if (strcasecmp(cursor->word, word_copy) == 0)
        {
            return true;
        }
        else
        {
            cursor = cursor->next;
        }

        return false;
    }

    return true;

}
// Hashes word to a number
unsigned int hash(const char *word)
{

    // 32-bit MurmurHash

    unsigned int h = 3323198485;
    while (*word)
    {
        h ^= tolower(*word);
        h *= 0x5bd1e995;
        h ^= h >> 15;
        word++;
    }
    return h % N;
}


// Loads dictionary into memory, returning true if successful else false
bool load(const char *dictionary)
{
    FILE *file = fopen(dictionary, "r");
    if (file == NULL)
    {
        unload();
        return false;
    }

    for (int i = 0; i < N; i++)
    {
        table[i] = NULL;
    }

    char word[LENGTH + 1];
    while (fscanf(file, "%s", word) != EOF)
    {
        node *new_node = malloc(sizeof(node));
        if (new_node == NULL)
        {
            unload();
            return false;
        }

        strcpy(new_node->word, word);

        int h = hash(new_node->word);

        node *head = table[h];

        if (head == NULL)
        {
            table[h] = new_node;
            word_count++;
        }

        else
        {
            new_node->next = table[h];
            table[h] = new_node;
            word_count++;
        }

    }

    fclose(file);
    return true;
}

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

// Unloads dictionary from memory, returning true if successful else false
bool unload(void)
{

    for (int i = 0; i < N; i++)
    {

        node *cursor = table[i];

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

    }

    return true;
}

This is what valgrind showing

I'm not able understand my mistake. Please elaborate whats wrong in it. Thank You :-)

Answer 1

Although the answer at CS50 pset5 program is free of memory errors valgrind tests failed; is very close, it's not exactly the problem. In that code, the ->next struct element is initialized inside an if code block.

In this code, the problem is a little different. If the node happens to be the first in a linked list, i.e., table[h] = NULL, then ->next is never set.

This is why it is critical to initialize values, especially inside structs, with either a call to calloc or an explicit assignment statement.

Programming note: the pointer head is completely unnecessary. It is used in one place only. It would be more efficient and obvious what is being done to use table[h] directly and eliminate head.

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