Pset5 - Problem with hash table load(), malloc, and segmentation-fault

Question

I am having problem with the load function. When I run:

valgrind --leak-check=full ./speller texts/austinpowers.txt

it gives me the following report (I am using the small dictionary to test my code) :

==12409== 
==12409== HEAP SUMMARY:
==12409==     in use at exit: 48 bytes in 4 blocks
==12409==   total heap usage: 6 allocs, 2 frees, 1,184 bytes allocated
==12409== 
==12409== 48 (32 direct, 16 indirect) bytes in 2 blocks are definitely lost in loss record 2 of 2
==12409==    at 0x4C2AB80: malloc (in /usr/lib/valgrind/vgpreload_memcheck-amd64-linux.so)
==12409==    by 0x40137C: load (dictionary.c:91)
==12409==    by 0x400A0D: main (speller.c:45)
==12409== 
==12409== LEAK SUMMARY:
==12409==    definitely lost: 32 bytes in 2 blocks
==12409==    indirectly lost: 16 bytes in 2 blocks
==12409==      possibly lost: 0 bytes in 0 blocks
==12409==    still reachable: 0 bytes in 0 blocks
==12409==         suppressed: 0 bytes in 0 blocks
==12409== 
==12409== For counts of detected and suppressed errors, rerun with: -v
==12409== ERROR SUMMARY: 5 errors from 3 contexts (suppressed: 0 from 0)

But at line 91 of dictionary.c, it is just a malloc function:

node* newNode = malloc(sizeof(node));

Also, when I run the following command with the large dictionary file, it's segmentation fault:

./speller texts/austinpowers.txt

I've tried my best to understand pointers, linked lists and others in the recent weeks. But I still find it hard and really couldn't figure out the problem. Could someone please help?

Here is my full code:

/**
 * dictionary.c
 *
 * Computer Science 50
 * Problem Set 5
 *
 * Implements a dictionary's functionality.
 */

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

#include "dictionary.h"

#define HASHTABLE_SIZE 1024

int hash(const char *word);

char word[LENGTH + 1];
int wordCount = 0;

typedef struct node { 
    char* word; 
    struct node* next;
} node;

node* hashTable[HASHTABLE_SIZE];

/**
 * Returns hash value for the word.
 */ 
int hash(const char* word) {
    int sum = 0;

    for (int i = 0; word[i] != '\0'; i++) {
        sum += word[i];
    }

    return sum % HASHTABLE_SIZE;
}

/**
 * Returns true if word is in dictionary else false.
 */
bool check(const char* word)
{
    char tmpWord[LENGTH + 1];
    int wordLen = strlen(word);

    int hashValue = hash(word);
    node* targetList = hashTable[hashValue];

    for (int i = 0; i < wordLen; i++) {
        int lowerChar = tolower(word[i]);
        tmpWord[i] = (char) lowerChar;
    }

    while (targetList != NULL) {
        if (strcmp(word, tmpWord) == 0) {
            return true;
        }
        targetList = targetList->next;
    }

    return false;
}

/**
 * Loads dictionary into memory. Returns true if successful else false.
 */
bool load(const char* dictionary)
{
    FILE* dictionaryPtr = fopen(dictionary, "r");

    // check if the dictionary is successfully opened
    if (dictionaryPtr == NULL) {
        fclose(dictionaryPtr);
        printf("Could not open %s.\n", dictionary);
        return false;
    }

    // init buckets in hash table
    for (int i = 0; i < HASHTABLE_SIZE; i++) {
        hashTable[i] = NULL;
    }

    while (fscanf(dictionaryPtr, " %s\n", word) != EOF) {
        node* newNode = malloc(sizeof(node));
        newNode->word = malloc(sizeof(strlen(word) + 1));

        // copy word into new node
        strcpy(newNode->word, word);

        int hashValue = hash(word);
        node* targetNode = hashTable[hashValue];

        // when targetNode is already the head of list
        if (targetNode == NULL) { 
            targetNode = newNode;
            newNode->next = NULL;
        } else { 
            newNode->next = targetNode;
            targetNode = newNode;
        }

        wordCount++;
    }

    fclose(dictionaryPtr);

    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. Returns true if successful else false.
 */
bool unload(void)
{
    node *targetList, *tmpListHolder;

    for (int i = 0; i < HASHTABLE_SIZE; i++) {
        targetList = hashTable[i];
        while (targetList != NULL) {
            tmpListHolder = targetList;
            targetList = targetList->next;

            free(tmpListHolder->word);
            free(tmpListHolder);
        }
    }

    return true;
}

Answer 1

In check, you don't copy the terminator, you could add a tmpWord[wordLen] = 0; between the for- and the while loop.

It makes little to compare word and tmpWord (the lowercase version of word), but strcmp(targetList->word, tmpWord) might be work.

Also, you never store anything in your hash table. After copying the word to the structure, I'd expect something like

newNode->next = hashTable[hashValue];
hashTable[hashValue] = newNode;

(prepending newNode to the list, which is the easiest insert operation on a linked list) and not some targetNode.

Answer 2

What's causing your seg fault on this line is the sizeof operator:

newNode->word = malloc(sizeof(strlen(word) + 1));

What you really meant here was:

malloc((strlen(word) + 1) * sizeof(char));