segmentation fault in speller cs50

Question

Currently, I am working on pset5 and whenever I try to compile, I get a segmentation fault. I could not find where the mistake lies and I would appreciate the help of an expert here very much. Hinting the mistakes is totally fine.

Code:

// Implements a dictionary's functionality

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

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 = 27;

// Hash table
node *table[N];

// Returns true if word is in dictionary else false
bool check(const char *word)
{
    // Converting word to lower case
    char *lower_word = NULL;
    strcpy(lower_word, word);
    int len = 0;
    len = sizeof(lower_word);
    for (int i = 0; i < len; i++)
    {
        lower_word[i] = tolower(lower_word[i]);
    }

    node *head = NULL;
    node * cursor = NULL;
    cursor = head;

    while (cursor != NULL)
    {
        cursor = head;
        if (cursor -> word == lower_word)
        {
            return true;
        }
        else
        {
            cursor = cursor -> next;
        }
    }
    return false;
}

// Hashes word to a number
unsigned int hash(const char *word)
{
    // TODO
    // From: http://www.cse.yorku.ca/~oz/hash.html
    unsigned long sdbm(char *word);
    {
        unsigned long hash = 0;
        int c;
        while ((c = *word++))
        {
            hash = c + (hash << 6) + (hash << 16) - hash;
            // Deleted free(word);

        }
        return hash;
    }
    return 0;
}

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

    // Read strings from file
    char word[LENGTH + 1];

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

    while (fscanf(dict, "%s", word) == EOF)
    {
        // Create a new node
        node *n = malloc(sizeof(node));
        n -> next = NULL;

        if (n == NULL)
        {
            return 1;
        }

        // Insert word into node
        int x = hash(word);

        strcpy(n -> word, word);

        // Set position x in table equal to node

        if(table[x] == NULL)
        {
            table[x] = n;
        }
        else
        {
            n = table[x];
            table[x] = n;
        }

        // Count word for size function
        word_count++;
    }
    fclose(dict);
    return true;
}

// Returns number of words in dictionary if loaded else 0 if not yet loaded
unsigned int size(void)
{
    // TODO
    int table_size = 0;
    table_size = sizeof(table)/sizeof(table[0]);
    int count = 0;
    for (int i = 0; i < table_size; i++)
    {
        count++;
    }
    return count;
    return 0;
}

// Unloads dictionary from memory, returning true if successful else false
bool unload(void)
{
    // TODO
    int table_size = 0;
    table_size = sizeof(table)/sizeof(table[0]);

    node *cursor = NULL;
    node* tmp = NULL;
    for (int i = 0; i < table_size; i++)
    {
        while (cursor != NULL)
        {
            tmp = cursor;
            cursor = cursor -> next;
            free(tmp);
        }
    }
    return true;
}

Input:

./speller texts/lalaland.txt

Output:

MISSPELLED WORDS

Segmentation fault

Did someone come across CS50 pset5 and could me? For further information please refer to: https://cs50.harvard.edu/x/2020/psets/5/speller/

I have watched the walkthroughs many times and also went through the shorts, but I am not making progress.

update check function:

{
    // Hash word to obtainhash value

    int bucket = hash(word);

    // Traverse linked list and look for the word using strcmp

    node *cursor = NULL;
    node *head = table[bucket];
    cursor = head;

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

}

update 2:

// Implements a dictionary's functionality

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

#define HASHMAX 1000

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 = 143091;


// Hash table
node *table[N];

// Returns true if word is in dictionary else false
bool check(const char *word)
{
    // Hash word to obtainhash value

    int bucket = hash(word);

    // Traverse linked list and look for the word using strcmp

    node *cursor = NULL;
    node *head = table[bucket];
    cursor = head;

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

}

// Hashes word to a number
unsigned int hash(const char *word)
{
    // TODO
    // From: http://www.cse.yorku.ca/~oz/hash.html
    unsigned long sdbm(char *word);
    {
        unsigned long hash = 5381;
        int c;
        while ((c = *word++))
        {
            hash = c + (hash << 6) + (hash << 16) - hash;
            // Deleted free(word);

        }
        return hash % HASHMAX;
    }
    return 0;
}

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

    // Read strings from file
    char word[LENGTH + 1];

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

    while (fscanf(dict, "%s", word) != EOF)
    {
        // Create a new node
        node *n = malloc(sizeof(node));
        n -> next = NULL;

        if (n == NULL)
        {
            return 1;
        }

        // Insert word into node
        int x = hash(word);

        strcpy(n -> word, word);

        // Set position x in table equal to node

        if(table[x] == NULL)
        {
            table[x] = n;
        }
        else
        {
            n = table[x];
            table[x] = n;
        }

        // free(n);

        // Count word for size function
        word_count++;
    }
    fclose(dict);
    return true;
}




// Returns number of words in dictionary if loaded else 0 if not yet loaded
unsigned int size(void)
{
    // TODO
    int table_size = sizeof(table)/sizeof(table[0]);
    int count = 0;
    for (int i = 0; i < table_size; i++)
    {
        count++;
    }
    return count;
    return 0;
}

// Unloads dictionary from memory, returning true if successful else false
bool unload(void)
{
    // TODO
    int table_size = sizeof(table)/sizeof(table[0]);
    node *cursor = NULL;
    node* tmp = NULL;
    for (int i = 0; i < table_size; i++)
    {
        node *head = table[i];
        while (cursor != NULL)
        {
            tmp = cursor;
            cursor = cursor -> next;
            free(tmp);
        }
    }
    return true;
}

Results:

WORDS MISSPELLED:     17263
WORDS IN DICTIONARY:  143091
WORDS IN TEXT:        17756
TIME IN load:         0.02
TIME IN check:        0.01
TIME IN size:         0.00
TIME IN unload:       0.00
TIME IN TOTAL:        0.03

Answer 1

The proximate cause of the error: NULL is a constant, which means it cannot be changed, this line char *lower_word = NULL; sets lower_word to NULL, this line strcpy(lower_word, word); tries to change it. Seg fault.

Perhaps consider simply iterating over word and setting each char to lower "in place".

After edit:

table is allocated for N (27) elements. The hash function is returning values WAY bigger than 27. You could either change the hash function to a simple alphabet index (something like tolower(word[i]) - 'a') OR use the modulo (%) operator to limit bucket size.

These are probably not the only problems in the program, but of course the seg fault needs to be fixed before you can make real progress. debug50 is your friend (and much easier to use with the small dictionary!)