pset5 speller memory errors with valgrind

Question

i've been working in pset5 and cannot make it work. I've read some similar questions and made some improvements to my code, but still can't figure what is wrong. Any tips are welcomed!

Here is my code:

// Implements a dictionary's functionality
#include <stdio.h>
#include <stdbool.h>
#include <strings.h>
#include <string.h>
#include <ctype.h>
#include "dictionary.h"
#include <stdlib.h>


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

// Prototypes
bool traverse(node *head, const char *lookup);
void freelist(node *list);

// Number of buckets in hash table
const unsigned int N = 93;
unsigned int numofwords = 0;

// Hash table
node *table[N];

bool traverse(node *head, const char *lookup)
{
    if (strcasecmp(head->word, lookup) == 0)
    {
        return true;
    }
    else if(head->next == NULL)
    {
        return false;
    }
    else
    {
      return  traverse(head->next, lookup);
    }
}

// Returns true if word is in dictionary, else false
bool check(const char *word)
{
    // Handle case difference
    char *tmp = malloc(8 * strlen(word)) + 1;
    strcpy(tmp,word);
    *tmp = tolower(*tmp);
    unsigned int checkHash = hash(tmp);
    node *checkNode = table[checkHash];
    return traverse(checkNode, word);
    free(tmp);

}

// Hash function (djb2 by Dan Bernstein)
unsigned int hash(const char* str)
{
    unsigned int hash = 5381;
    int c;

    while ((c = *str++))
        hash = ((hash << 5) + hash) + c; /* hash * 33 + c */
    return hash % N;
}

// Loads dictionary into memory, returning true if successful, else false
bool load(const char *dictionary)
{
    for (int i = 0; i < N; i++)
    {
        table[i] = NULL;
    }

    FILE *dic = fopen(dictionary, "r");

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

    char *word = malloc(LENGTH + 1);
    if(word == NULL)
    {
        return false;
    }
    node *newNode = malloc(sizeof(node));
    if(newNode == NULL)
    {
        return false;
    }
    unsigned int currHash;
    while(fscanf(dic,"%s",word) != EOF)
    {
        numofwords++;
        strcpy(newNode->word, word);
        newNode->next = NULL;

        currHash = hash(newNode->word);
        //First appearence of Hash Index
        if (table[currHash] == NULL)
        {
            table[currHash] = newNode;
        }
        //Collisions. Add to the list.
        else
        {
            newNode->next = table[currHash]->next;
            table[currHash]->next = newNode;
        }

    }
    free(word);
    free(newNode);
    fclose(dic);
    return true;
}

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

// Unloads dictionary from memory, returning true if successful, else false
bool unload(void)
{
    for (int i = 0; i < N; i++)
    {
        freelist(table[i]);
    }
    return true;
}

void freelist(node *list)
{
    while (list->next != NULL)
    {
        freelist(list->next);
    }
    free(list);
}

And a summary of ./speller texts/cat.txt :

==1159== Memcheck, a memory error detector
==1159== Copyright (C) 2002-2017, and GNU GPL'd, by Julian Seward et al.
==1159== Using Valgrind-3.15.0 and LibVEX; rerun with -h for copyright info
==1159== Command: ./speller texts/cat.txt
==1159== 

MISSPELLED WORDS

==1159== Invalid read of size 1
==1159==    at 0x483F85C: strcasecmp (in /usr/lib/x86_64-linux-gnu/valgrind/vgpreload_memcheck-amd64-linux.so)
==1159==    by 0x4019BC: traverse (dictionary.c:32)
==1159==    by 0x401A87: check (dictionary.c:55)
==1159==    by 0x40160B: main (speller.c:113)
==1159==  Address 0x4b992d0 is 0 bytes inside a block of size 56 free'd
==1159==    at 0x483CA3F: free (in /usr/lib/x86_64-linux-gnu/valgrind/vgpreload_memcheck-amd64-linux.so)
==1159==    by 0x401C7C: load (dictionary.c:118)
==1159==    by 0x4012CE: main (speller.c:40)
==1159==  Block was alloc'd at
==1159==    at 0x483B7F3: malloc (in /usr/lib/x86_64-linux-gnu/valgrind/vgpreload_memcheck-amd64-linux.so)
==1159==    by 0x401B91: load (dictionary.c:91)
==1159==    by 0x4012CE: main (speller.c:40)
==1159== 
==1159== Invalid read of size 8
==1159==    at 0x4019D3: traverse (dictionary.c:36)
==1159==    by 0x401A87: check (dictionary.c:55)
==1159==    by 0x40160B: main (speller.c:113)
==1159==  Address 0x4b99300 is 48 bytes inside a block of size 56 free'd
==1159==    at 0x483CA3F: free (in /usr/lib/x86_64-linux-gnu/valgrind/vgpreload_memcheck-amd64-linux.so)
==1159==    by 0x401C7C: load (dictionary.c:118)
==1159==    by 0x4012CE: main (speller.c:40)
==1159==  Block was alloc'd at
==1159==    at 0x483B7F3: malloc (in /usr/lib/x86_64-linux-gnu/valgrind/vgpreload_memcheck-amd64-linux.so)
==1159==    by 0x401B91: load (dictionary.c:91)
==1159==    by 0x4012CE: main (speller.c:40)
==1159== 

The record was much longer, but very repetitive, and had some errors coming from the distributed speller.c, so I guess it was just error propagation.

Answer 1

There are a number of problems in this code. For starters, it's generating a seg fault in freelist. Fixing that leads to an infinite loop, indicating issues elsewhere. Additionally, it seems to be finding that every word is misspelled. All of these issues are likely intertwined.

This will be an excellent learning experience in debugging!

My suggestion at this point is to simply put a return true; statement at the beginning of the unload function for now. This will allow you to debug the rest of the code and eliminate any issues in load and check. Once that's all fixed, come back to unload and resolve the remaining issues there. The unload issues likely can't be fixed until the earlier issues are dealt with.

If you can't work through those issues, post new questions to deal with each issue and they can be worked through in order.