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)
{
}

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
{
// Initialize hash table
for (int i = 0; i < N; i++)
{
hashtable[i] = NULL;
}

// Open dictionary
FILE *file = fopen(dictionary, "r");
if (file == NULL)
{
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
{

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

• can you post the whole dictionary.c file? alternatively, you can copy and paste your dictionary.c to segfault.stensal.com/test_your_cs50_code to find out what may cause the segfault. – stensal Feb 9 '19 at 19:42
• Yes, please post the rest of the related code. I tested the code above and it works for me. Usually, this error comes from trying to access an element of a null node (a node that doesn't exist.) Could come from any number of problems. – Cliff B Feb 9 '19 at 21:02
• Actually, the strcpy looks more suspicious. strcpy takes two char* arguments. The word argument is a char array. If it is not properly null-terminated, the strcpy is vulnerable to a crash. As alluded to in the prior comments, not enough code posted to evaluate. – DinoCoderSaurus Feb 9 '19 at 21:04

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.

• So obvious in hindsight. – CSumter Feb 11 '19 at 9:50

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.