Struggling with PSET5 Speller valgrind problems (& possibly more)

Question

I've been working on PSET5 for weeks now on & off and I'm becoming really frustrated. I think I'm lacking some understanding of the malloc/free relationship, I'm not sure. Here's all of my code. Valgrind returns issues at line 70 & 124. Speller combines but check50 has sad faces for almost everything (although it had fewer sad faces a few days ago, and I haven't changed anything since!). I have no idea what to do or where my problems are. I compared my code against some online solutions and could not find anything significantly logically different. I'm finding this extremely challenging and would appreciate any help.

// Implements a dictionary's functionality

#include <stdbool.h>
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <strings.h>
#include <stdint.h>
#include <ctype.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];

//Dictionary word count
int wordcount = 0;

// Returns true if word is in dictionary else false
bool check(const char *word)
{
    //Get hash value of the word
    unsigned int h = hash(word);
    
    //Access linked list at that index in the hash table
    node *cursor = malloc(sizeof(node));
        
    //Check in case there is not enough memory
    if (cursor == NULL)
    {
        return false;
    }
    
    //Initialise cursor to traverse the linked list
    cursor = table[h];
    
    //Compare the contents of the linked list with the word
    while (cursor != NULL)
    {
        if (strcasecmp(cursor->word, word) == 0) //If the words match
        {
            return true;
        }
        else //If the words don't match
        {
            cursor = cursor->next;
        }
    }
    
    //Otherwise, return false
    return false;
    
}

// Hashes word to a number
unsigned int hash(const char *word)
{
    //New lowercase word
    char *lword = malloc(strlen(word) + 1);
    
    //Copy the word
    strcpy(lword, word);
    
    //Make all words lowercase
    for (int i = 0; i < strlen(lword); i++)
    {
         if (isalpha(lword[i]))
         {
             lword[i] = tolower(lword[i]);
         }
    }
    
    //Hash function credit: djb2 by Dan Bernstein
    unsigned long hash = 5381;
    int c;

    while ((c = *lword++))
        hash = ((hash << 5) + hash) + c; /* hash * 33 + c */

    free(lword);
    return hash % N;
}

// Loads dictionary into memory, returning true if successful else false
bool load(const char *dictionary)
{
    //Open dictionary file
    FILE *file = fopen(dictionary, "r");
    
    //Check if a return value is NULL
    if (file == NULL)
    {
        return false;
    }
    
    //Declare new variable
    char word[LENGTH + 1];
    
    //Read strings from file one at a time
    while (fscanf(file, "%s", word) != EOF)
    {
        fscanf(file, "%s", word);
        
        //Allocate memory to store a new node
        node *n = malloc(sizeof(node));
        
        //Check in case there is not enough memory
        if (n == NULL)
        {
            return false;
        }
        
        //Hash word to obtain a hash value
        unsigned int index = hash(word);
        
        //If first element of the linked list
        if (table[index] == NULL)
        {
            table[index] = n;
            n->next = NULL;
        }

        //If the linked list is already populated
        else
        {
            n->next = table[index];
            table[index] = n;
        }
        
        //Copy word into the node
        strcpy(n->word, word);
        wordcount++;
        
    }
    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)
{
    for (int i = 0; i < N; i++)
    {
        //Initialise cursor
        node *cursor = table[i];
    
        //Until cursor is NULL
        while(cursor != NULL)
        {
            node *tmp = cursor;
            cursor = cursor->next;
            free(tmp);
        }
    }
    
    return true;
}

Answer 1

I see a few problems in the code that are causing problems.

First, table[] is not initialized. That means that all the pointers in the array contain garbage data instead of NULL when the program starts.

Second, there's this:

while (fscanf(file, "%s", word) != EOF)
{
    fscanf(file, "%s", word);

This is executing two sequential reads. That means that half of the words are not being processed. They're just being discarded. When an fscanf() call is embedded in a while statement, it's not just providing a return value to test. It's actually executing the fscanf call to get that return value to test. Remove the second fscanf.

Third, there's this:

//Access linked list at that index in the hash table
node *cursor = malloc(sizeof(node));
...
//Initialise cursor to traverse the linked list
cursor = table[h];

This code is allocating memory to cursor and then discarding that memory. That's a big memory leak. It's leaking the memory space of one node each time check is called. When creating a temp pointer like a cursor that will have an existing memory address assigned to it later, initialize it by setting it to NULL instead.

Finally, the hash function has several problems. That's one that I'm going to let you figure out. I suggest replacing your current hash with a simpler hash function until you get the other problems fixed and then try to implement djb2 hash.

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