How do i solve this segmentation fault in my code

Question

Hi I am doing the speller question from problem set 5 of cs50 and have run into a segmentation fault but I do not understand why. The error I have obtained is this:

MISSPELLED WORDS

==18659== Invalid read of size 8
==18659==    at 0x40102C: check (dictionary.c:32)
==18659==    by 0x400C49: main (speller.c:112)
==18659==  Address 0x75cfc8 is not stack'd, malloc'd or (recently) free'd
==18659== 
==18659== 
==18659== Process terminating with default action of signal 11 (SIGSEGV)
==18659==  Access not within mapped region at address 0x75CFC8
==18659==    at 0x40102C: check (dictionary.c:32)
==18659==    by 0x400C49: main (speller.c:112)
==18659==  If you believe this happened as a result of a stack
==18659==  overflow in your program's main thread (unlikely but
==18659==  possible), you can try to increase the size of the
==18659==  main thread stack using the --main-stacksize= flag.
==18659==  The main thread stack size used in this run was 8388608.
==18659== 
==18659== HEAP SUMMARY:
==18659==     in use at exit: 552 bytes in 1 blocks
==18659==   total heap usage: 4 allocs, 3 frees, 6,224 bytes allocated
==18659== 
==18659== 552 bytes in 1 blocks are still reachable in loss record 1 of 1
==18659==    at 0x4C2FB0F: malloc (in /usr/lib/valgrind/vgpreload_memcheck-amd64-linux.so)
==18659==    by 0x5258E49: __fopen_internal (iofopen.c:65)
==18659==    by 0x5258E49: fopen@@GLIBC_2.2.5 (iofopen.c:89)
==18659==    by 0x4009E3: main (speller.c:55)
==18659== 
==18659== LEAK SUMMARY:
==18659==    definitely lost: 0 bytes in 0 blocks
==18659==    indirectly lost: 0 bytes in 0 blocks
==18659==      possibly lost: 0 bytes in 0 blocks
==18659==    still reachable: 552 bytes in 1 blocks
==18659==         suppressed: 0 bytes in 0 blocks
==18659== 
==18659== For counts of detected and suppressed errors, rerun with: -v
==18659== ERROR SUMMARY: 1 errors from 1 contexts (suppressed: 0 from 0)
/etc/profile.d/cli.sh: line 94: 18659 Segmentation fault      valgrind ./speller texts/cat.txt

This is my code:

// Implements a dictionary's functionality

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

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

int word_count;

// Number of buckets in hash table
const unsigned int N = 1;

// Hash table
node *table[N];

// Returns true if word is in dictionary else false
bool check(const char *word)
{
    // Hash word to obtain hash value
    int index = hash(word);
    // Access linked list at that index
    node* cursor = table[index];
    while(cursor != NULL)
    {
        if(strcasecmp(word, cursor->word) == 0)
        {
            return true;
        }
        // Traverse linked list
        else
        {
            cursor = cursor->next;
        }
    }
    return false;
}

// Hashes word to a number
//Hash table that I got from https://stackoverflow.com/questions/7666509/hash-function-for-string
unsigned int hash(const char *word)
{
    unsigned int hash = 5381;
    int c;

    while ((c = *word++))
        hash = ((hash << 5) + hash) + c; /* hash * 33 + c */

    return hash;
}

// Loads dictionary into memory, returning true if successful else false
bool load(const char *dictionary)
{
    // Open dictionary file
    FILE* memory = fopen(dictionary, "w");
    word_count = 0;
    if(memory == NULL)
    {
        return false;
    }
    char word[LENGTH + 1];
    while((fscanf(memory, "%s", word) != EOF))
    {
        node* n = malloc(sizeof(node));
        if(n == NULL)
        {
            return false; 
        }
        strcpy(n->word, word);
        word_count++;
        int index = hash(n->word);
        // Inserting into start of linked lists with no elements
        if(table[index]->next == NULL)
        {
            table[index] = n;
        }
        //Inserting into start of linked lists with elements
        else
        {
            n->next = table[index];
            table[index] = n;
        }
        
        
    }
    
    
    fclose(memory);
    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)
{
    int counter = 0;
    for(int i = 0; i < N; i++)
    {
        while(table[i] != NULL)
        {
            node* temp = table[i]->next;
            free(table[i]);
            table[i] = temp;
        }
        counter++;
    }
    if(counter == N)
    {
        return true;
    }
    return false;
}

I do not understand why there is a segmentation fault as i have provided a while loop to stop when the cursor is at the end of the loop. Could someone tell me where I have gone wrong please? Thanks!

Answer 1

It looks like your issue is occurring here :

    int index = hash(word);
    // Access linked list at that index
    node* cursor = table[index];

Specifically, looking at your hash function, it doesn't seem like you take any precaution to ensure the hash will be within N, the size of the table. This means when you hash the word, index might be greater than N, and the subsequent index access to table will cause your fault.

Try returning hash % N from the hash function instead.