Cant create linked list node

Question

For speller (hash table implementation) i keep getting a segfault that is coming from the line in this code where i set node->next = NULL

struct node* createNode(char word[])
{

    node *node = NULL;

    node = malloc(sizeof(node));


    if (node != NULL)
    {

         strcpy(node->word, word);

         node->next = NULL;

    }

    return node;

}

given that this is how it was explained to create a node, as well as demonstrated in the lecture. Would appreciate any pointers as to where i am making my mistake.

Here is dictionary.c (as an aside i am really annoyed at having to post all this code here, i have managed all the other psets without any help whatsever, this pset however well and truly puts students down the river without a paddle. Because of the way its structured, its extremely difficult to iteratively build up your solution and 'unit test' as you go along. its a complete hail mary for an inexperienced C programmer. Im sure there are some obvious errors in the code below but i honestly feel like i do not have the tools to figure out on my own what they may be...rant over)

// Implements a dictionary's functionality

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

#include "dictionary.h"

// Represents number of buckets in a hash table
#define N 26

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

// Represents a hash table
node *hashtable[N];

// Hashes word to a number between 0 and 25, inclusive, based on its first letter
unsigned int hash(const char *word)
{
    return tolower(word[0]) - 'a';
}

unsigned int getListLength(node *node)
{

    unsigned int wordCount = 0;

    while(node != NULL)
    {
        wordCount ++;

        node = node->next;
    }

    return wordCount;

}

struct node* createNode(char word[])
{

    node *node = NULL;

    node = malloc(sizeof(node));

    if (node != NULL)
    {

         strcpy(node->word, word);

         node->next = NULL; //SEGFAULT HAPPENS HERE

    }

    return node;

}

struct node* insertNode(node *list, node *node)
{

    node->next = list;

    return node;

}


int freeList(node *node)
{

    if (node == NULL)
    {
        return 0;

    }

    struct node *nxtNode = NULL;

    while(node != NULL)
    {

        nxtNode = node->next;

        free(node);

        node = nxtNode;

    }

    return 1;

}

// Loads dictionary into memory, returning true if successful else false
bool load(const char *dictionary)
{
    // Initialize hash table
    for (int i = 0; i < N; i++)
    {
        hashtable[i] = NULL;
    }

    // Open dictionary
    FILE *file = fopen(dictionary, "r");
    if (file == NULL)
    {
        unload();
        return false;
    }

    // Buffer for a word
    char word[LENGTH + 1];

    // Insert words into hash table
    while (fscanf(file, "%s", word) != EOF)
    {
         unsigned int i = hash(word);

         node *node = createNode(word);

         hashtable[i] = insertNode(hashtable[i], node);

    }

    // Close dictionary
    fclose(file);

    // Indicate success
    return true;
}

// Returns number of words in dictionary if loaded else 0 if not yet loaded
unsigned int size(void)
{

    unsigned int wordCount = 0;

    for (int i = 0; i<N; i++)
    {

        wordCount += getListLength(hashtable[i]);

    }

    return wordCount;
}

// Returns true if word is in dictionary else false
bool check(const char *word)
{
    int i = hash(word);

    node *node = hashtable[i];

    while (node != NULL)
    {
        printf("Word1 : %s \n", node->word);

        if (strcasecmp(node->word, word) == 0)
        {
           return true;

        }

        node = node->next;

    }

    return false;
}

// Unloads dictionary from memory, returning true if successful else false
bool unload(void)
{

    for (int i = 0; i<N; i++)
    {
        freeList(hashtable[i]);
    }

    return true;
}

Running the stensal tool:

./stensal-c -ggdb3 -O0 -Qunused-arguments -std=c11 -Wall -Werror -Wextra -Wno-sign-compare -Wshadow -o speller speller.o dictionary.o 

DTS_MSG: Stensal DTS detected a fatal program error!
DTS_MSG: Continuing the execution will cause unexpected behaviors, abort!
DTS_MSG: Out-of-bounds write is detected.
DTS_MSG: Writing 4 bytes at 0x9f17960 will corrupt the adjacent data.
DTS_MSG: Diagnostic information:

- The object to-be-written (start:0x9f17930, size:4 bytes) is allocated at
-     file:/dictionary.c::53, 12
-  0x9f17930               0x9f17933
-  +------------------------+
-  |the object to-be-written|......
-  +------------------------+
-                               ^~~~~~~~~~
-           the write starts at 0x9f17960 that is 44 bytes after the object end.
- Stack trace (most recent call first):
-[1]  file:/dictionary.c::60, 10
-[2]  file:/dictionary.c::129, 23
-[3]  file:/speller.c::40, 19

If i am interpreting this correctly, when trying to write to the 4 bytes allocated for the node->next pointer the write is happening somewhere else in memory. I do not know why this is occurring, and it only happens after a few thousand words have been loaded into the dictionary. Any assistance would be appreciated

Answer 1

This is a really tricky mistake happened around line 50-53. A live test of your code is available here: segfault fixed, I made a fix at line 52-53 and commented out the faulty code. It works correctly.

An explanation of the bug:

at line 50

  node * node = NULL;

at line 53

  node = malloc(sizeof(node));

here node in sizeof(node) is not the node type, it's the node pointer variable declared at line 50. the sizeof a node pointer is only 4 byte, hence you insufficiently allocate the memory for the node pointer.

If you change line 53 as the following, you will get the correct memory allocation:

  node = malloc(sizeof(struct node)); 

Alternative, use a different variable name at line 50.

Answer 2

The first thing I noticed is that the hashtable array is not allocated here hashtable[i] = NULL;. Remember, each index can hold a node. I fixed that in my repro case, but the error persisted.

I created a small two-word dictionary (which of course did not seg fault), and ran it through valgrind (as both dictionary and text). It reported an Invalid write of size 8 on the same line that segfaults. Huh? It's malloc'd right here node = malloc(sizeof(node)); in createNode. But which node is which in that sentence? I changed the function to create and return a node called newnode, and the program ran. And did not seg fault with the "large" dictionary. Progress.

It was my instincts as a programmer that led me to try "newnode". But it was the tools that got me there. The thing that gave me a break in the case was running valgrind on the very small file.

Some free advice (and you know what that's worth :), start small. Create your own text file, in dictionary format, and run ./speller smallfile smallfile. That will make valgrind and debug50 much easier to digest.