0

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

3
  • 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
2

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.

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

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.

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .