PSET5 speller segmentation fault

Question

Can anyone help with segmentation fault. I have tried running debug50 and aparently the fault hits at line "if (head -> next != NULL)" in the load function. Aparently "table" is null despite already being declared.

// Implements a dictionary's functionality

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

#define HASHTABLE_SIZE 10000


unsigned int hash(const char *hash_this);
// Represents a node in a hash table
typedef struct node
{
    char word[LENGTH + 1];
    struct node *next;
}
node;
int values = 0;
// Number of buckets in hash table
const unsigned int N = 10000;

// Hash table
node *table[N];

// Returns true if word is in dictionary, else false
bool check(const char *word)
{
    // TODO
    
    char low_word[LENGTH + 1];

    for (int i = 0; i < LENGTH; i++)
        {
            if (isalpha(word[i]))
            {
                low_word[i] = tolower(word[i]);
            }
        }
    int hash_index = hash(low_word);
    node *cursor = table[hash_index] -> next;
    if (cursor -> next != NULL)
    {
        while (cursor -> next != NULL)
        {
            if (cursor -> word == low_word)
            {
                return true;
            }
            else
            {
                cursor = cursor -> next;
            }
        }
        return false;

    }
    else
    {
        return false;
    }

}

// Hashes word to a number
unsigned int hash(const char *hash_this)
{
    unsigned int hash = 0;
    for (int i = 0, n = strlen(hash_this); i < n; i++)
    {
        hash = (hash << 2) ^ hash_this[i];
    }
    return hash % HASHTABLE_SIZE;
}


// Loads dictionary into memory, returnina true if successful, else false
bool load(const char *dictionary)
{
    // TODO
    FILE *dict = fopen(dictionary, "r");
    if (dict == NULL)
    {
        printf("Invalid Dictionary\n");
        return false;
    }
    values = 0;
    char word[LENGTH + 1];
    while (fscanf(dict, "%s", word) != EOF)
    {
        for (int i = 0; i < LENGTH; i++)
        {
            if (isalpha(word[i]))
            {
                word[i] = tolower(word[i]);
            }
        }
        
        node *newNode = malloc(sizeof(node));
        if (newNode == NULL)
        {
            return false;
        }
        strcpy(newNode -> word, word);
        newNode -> next = NULL;

        int hash_index = hash(newNode -> word);
        node *head = table[hash_index];
        if (head -> next != NULL)
        {
            newNode -> next = head -> next;
        }
        head -> next = newNode;
        values++;
    }
    return true;
}

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


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

Answer 1

Initially you have declared node *table[N] as global pointer. As you might have already guessed, all global variables/ pointers are set to default values.(In this case, each pointer is set to NULL).

So head = table[hash_index]; // It's still NULL

When you do head->next, you're trying to de-reference NULL which results in seg-fault.

Answer 2

This is a common error in this pset. Let's look at these statements and think about what could happen:

    node *head = table[hash_index];
    if (head -> next != NULL)

Now, let's say that table[hash_index] is null. (This is very likely with a small dictionary or a very large table size.) If it is null, then table[hash_index]->next doesn't exist. That will cause a seg fault. The code needs to check whether head, or table[hash_index] is null first. I suggest checking if table[hash_index] is not null and put the code that follows inside the if code block.

You may find a similar issue in check().

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