Speller beyond my reach: all words marked as misspelled

Question

The spectre of Speller is haunting me. The code below compiles fine, but comes a cropper in at least two ways - first, it marks all words as misspelled (is my hash function flawed? or am I loading incorrectly? Or is check to blame?), and second, the program doesn't end, but hangs, such that I have to exit with a crestfallen control-C in the terminal (am I leading it into an infinite loop somewhere?). Any guidance massively appreciated.

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

unsigned int word_count = 0;

// 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 = 100000; // I will change this...

// Hash table (create and initialise) - I may want to change the 26 if I change N, number of buckets, above.
node *table[N];
void initialise(void)
{
    for (int i = 0; i < N; i++)
    {
        table[i] = NULL;
    }
}

// Returns true if word is in dictionary else false
bool check(const char *word)
{
    // word to lowercase
    int len = strlen(word);
    char lowerword[len + 1];

    for (int i = 0; i < len; i++)
    {
        lowerword[i] = tolower(word[i]);
    }
    lowerword[len] = '\0';

    // hash the word
    unsigned int h = hash(lowerword);

    // access the linked list at the hash value // traverse the linked list, looking for the word with strcasecmp function (which is case-insensitive)
    node *cursor = table[h];
    if (table[h] == NULL)
    {
        return false;
    }
    while (cursor->next != NULL) // wonder if this should be while (cursor != NULL) ?
    {
        if (strcasecmp(cursor->word, lowerword) == 0)
        {
            return true;
        }
        cursor = cursor->next;
    }
    return false;
}

// Hashes word to a number
unsigned int hash(const char *word)
{
    // TODO
    unsigned int hh = 0;
    for (int i = 0; word[i] != '\0'; i++)
    {
        hh = 37*hh + word[i];
    }
    return hh % 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 file is empty
    if (file == NULL)
    {
        return false;
    }

    // Create a charachter array of size 46
    char buffer[LENGTH+1];

    // Read strings from file one at a time
    while (fscanf(file, "%s", buffer) != EOF)
    {
        node *temp_node = malloc(sizeof(node));
        if (temp_node == NULL)
        {
            printf("You've run out of memory! \n");
            return false;
        }
        strcpy(temp_node->word, buffer);
        temp_node->next = NULL;

        // Hash word to obtain hash value
        unsigned int hashnum = hash(buffer); // used to be hash((const char *)buffer)

        //Insert node at table[hash_value]//
        if(table[hashnum] == NULL)
        {
            table[hashnum] = temp_node;
        }
        else
        {
            node *temp_node2 = table[hashnum];
            if(temp_node2 == NULL)
            {
                *temp_node2 = *temp_node;
            }
            else
            {
                while(temp_node2->next != NULL)
                {
                    temp_node2 = temp_node2->next;
                }
                temp_node2->next = temp_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)
{
    // call free on all the nodes on the hash
    node *cursor;

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

        while (cursor != NULL)
        {
            for (node *temp = table[i]; temp->next != NULL; temp = cursor)
            {
                cursor = cursor->next;
                free(temp);
            }
        }

    }
    return true;
}

Answer 1

The problem with the misspelled words lies in check, specifically with this:

while (cursor->next != NULL) // wonder if this should be while (cursor != NULL) ?

Your wondering is exactly on target. ;-)

The infinite loop lies in the unload function. perhaps you've made it a little overcomplicated?

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