Pset5 speller segmentation fault when loading

Question

When I run speller, I get a segmentation fault. I have played around with the code a little bit and nothing so far has changed. Using help50, this is the result I got:

Looks like you're trying to modify 8 bytes of memory that isn't yours? Did you try to store something beyond the bounds of an array? Take a closer look at line 94 of dictionary.c.

The issue occurs somewhere on line 94, when I set the node's pointer to NULL, and I believe the issue is within the load function. I am not quite sure what the issue is still, if anyone can explain this error message to me, that would be amazing.

Code:

// Implements a dictionary's functionality

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

#include "dictionary.h"

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

// TODO: Choose number of buckets in hash table
const unsigned int N = 26000;

// Create a variable to keep track of the number of words in the text
unsigned int wordCount = 0;

// Hash table
node *table[N];

// Returns true if word is in dictionary, else false
bool check(const char *word)
{
    // Get the hash value of the word
    unsigned int hashVal = hash(word);

    // Iterate through a linked this creating a node var that will travel through each point in the hash table
    for (node *destination = table[hashVal]; destination != NULL; destination = destination->next)
    {
        // Check if the word is found, that is if it equals the current destination's word
        if (strcasecmp(destination->word, word) == 0)
        {
            return true;
        }
    }
    // If the word is not found, return false
    return false;
}

// Hashes word to a number
// Deeper understanding of hash tables from here: https://www.youtube.com/watch?v=2Ti5yvumFTU
unsigned int hash(const char *word)
{
    unsigned int hashVal = 0;
    for (int i = 0; i < strlen(word); i++)
    {
        hashVal += word[i];
    }

    if (hashVal >= N)
    {
        hashVal = hashVal % strlen(word);
    }

    return hashVal;
}

// Loads dictionary into memory, returning true if successful, else false
bool load(const char *dictionary)
{
    char word[LENGTH + 1];
    FILE *text = fopen(dictionary, "r");

    if (dictionary == NULL)
    {
        printf("Could not open\n");
        return false;
    }

    while (fscanf(text, "%s", word) != EOF)
    {
        // Create a node for the word
        node *node = malloc(sizeof(node));

        // Get the hash value for the word we are looking at
        unsigned int hashVal = hash(word);

        if (node == NULL)
        {
            fclose(text);
            return false;
        }

        // Set the node to the word and set its destination
        strcpy(node->word, word);
        node->next = NULL;
        node->next = table[hashVal];

        // Increase word count
        wordCount++;
    }
    fclose(text);
    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, returning true if successful, else false
bool unload(void)
{
    for (int i = 0; i < N; i++)
    {
        // Create a ptr node to store data
        node *cursor = table[i];

        // Create a tmp node to make sure that no mem is leaked
        node *tmp = cursor->next;

        // Free the data of the current cursor
        free(cursor);

        // Set the cursor to thhe temp ptr
        cursor = tmp;
    }
    return false;
}

Answer 1

Hmmm, help50 wasn't very helpful. The problem sorta lies with line 94, but not really. All that valgrind and help50 is telling you is that the problem memory was allocated on line 94. That gives you a clue about what to look at, but not where the problem truly lies.

In fact, if you were to toss in a couple of printf statements to see how far the code progresses, you'd see that it gets all the way to unload. If you were to insert a "return true;" statement as the first line of unload to test, you'd see that the rest of the program appears to execute to completion (not saying it does or doesn't have any issues.)

So, looking at the unload functions, there are a lot of problems there. The var cursor is initialized inside the for loop. This guarantees that the code will never get past the first node of any linked list. Next, this process requires at least two loops, one nested inside the other. Question for you to figure out: Should the inner loop be a for loop or a while loop? ;-)

I suggest that you go back and rewatch all of the lectures and videos directly related to this pset and try again. Pay special attention to how to traverse a linked list. If you still can't sort it, post a new question with your revised code.

BTW, the array "table[ ]" is an array of pointers. Pointers are not initialized by default. They just contain whatever garbage data happens to be left in those memory locations from whatever used them before. Where in the code is table[] initialized, preferably to NULL for each element?

Finally, there's line 94 itself. It's totally not needed.

    node->next = NULL;   // line 94
    node->next = table[hashVal];

Since the next line assigns a value to node->next, line 94 is a waste of computing cycles and can be deleted. Now, if line 95 were in an if statement, that would be a different story.

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