0

this is my first post to this forum so I hope I've followed correct procedure.

I get a segmentation fault when I run speller. Valgrind says the problem is "Invalid read of size 8" at line 114 in the load function:

==70635== Invalid read of size 8
==70635==    at 0x4011FC: load (dictionary.c:114)
==70635==    by 0x40092D: main (speller.c:40)
==70635==  Address 0x5ca34888 is not stack'd, malloc'd or (recently) free'd
==70635== 
==70635== 
==70635== Process terminating with default action of signal 11 (SIGSEGV)
==70635==  Access not within mapped region at address 0x5CA34888
==70635==    at 0x4011FC: load (dictionary.c:114)
==70635==    by 0x40092D: main (speller.c:40)
==70635==  If you believe this happened as a result of a stack
==70635==  overflow in your program's main thread (unlikely but
==70635==  possible), you can try to increase the size of the
==70635==  main thread stack using the --main-stacksize= flag.
==70635==  The main thread stack size used in this run was 8388608.
==70635== 
==70635== HEAP SUMMARY:
==70635==     in use at exit: 624 bytes in 2 blocks
==70635==   total heap usage: 2 allocs, 0 frees, 624 bytes allocated
==70635== 
==70635== 56 bytes in 1 blocks are still reachable in loss record 1 of 2
==70635==    at 0x4C2AB80: malloc (in /usr/lib/valgrind/vgpreload_memcheck-amd64-linux.so)
==70635==    by 0x4011B0: load (dictionary.c:101)
==70635==    by 0x40092D: main (speller.c:40)
==70635== 
==70635== 568 bytes in 1 blocks are still reachable in loss record 2 of 2
==70635==    at 0x4C2AB80: malloc (in /usr/lib/valgrind/vgpreload_memcheck-amd64-linux.so)
==70635==    by 0x4EA537C: __fopen_internal (iofopen.c:73)
==70635==    by 0x401111: load (dictionary.c:78)
==70635==    by 0x40092D: main (speller.c:40)
==70635== 
==70635== LEAK SUMMARY:
==70635==    definitely lost: 0 bytes in 0 blocks
==70635==    indirectly lost: 0 bytes in 0 blocks
==70635==      possibly lost: 0 bytes in 0 blocks
==70635==    still reachable: 624 bytes in 2 blocks
==70635==         suppressed: 0 bytes in 0 blocks

Nothing is being read at line 114, so maybe it refers to the reading of the word in fscanf? It's not clear to me where the invalid read is happening or what's causing it.

There may be other problems with my load code that are contributing to this error as I haven't been able to test whether load works. I saw in a post that you could print the word count calculated by the size function to see if load worked, but I can obviously only print the word count out if the load and size functions are working!

My dictionary.c code is below. If anyone has time to help me with this error (and any other problems you spot with with my code) I'd really appreciate it:

/**
 * Implements a dictionary's functionality.
 */
#include <stdio.h>
#include <stdlib.h>
#include <stdbool.h>
#include <string.h>
#include <strings.h>
#include <cs50.h>
#include "dictionary.h"

#define SIZE 26

// declare a linked list node structure
typedef struct node
{
    char word[LENGTH+1];
    struct node* next;
}
node;

// declare counter variable to keep track of words
unsigned int wordCount = 0;

// declare hash table (array of node pointers)
node* hashtable[SIZE];

// Hash function (djb2 by Dan Bernstein)
unsigned int hash(const char* str)
{
unsigned int hash = 5381;
int c;

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

return hash;
}

/**
 * Returns true if word is in dictionary else false.
 */
bool check(const char *word)
{
// head pointer points at first node in list 
node* head = hashtable[hash(word)];

// cursor pointer now points at first node in list too
node* cursor = head;

// traverse the linked list for the word
while (cursor != NULL)
{
    // compare text word with dictionary word
    int result = strcasecmp(word, cursor->word);

    // if words are same length, return true
    if (result == 0)
    {
        return true;
    }
    // else, move to next node in linked list
    else
    {
        cursor = cursor->next;
    }
}
// if word not in dictionary
return false;
}

/**
 * Loads dictionary into memory. Returns true if successful else 
false.
 */
bool load(const char* dictionary)
{
// open dictionary
FILE* dict = fopen(dictionary, "r");
if (dict == NULL)
{
    printf("Could not open dictionary %s.\n", dictionary);
    return 1;
}

// initialize elements in hashtable to null
for (int i = 0; i < SIZE; i++)
{
    hashtable[i] = NULL;
}

// variable to store word from text
char dictWord[LENGTH+1];

// declare variable before while loop to prevent 'implicit declaration' error
node* wordNode = NULL;

// get a word from the dictionary file
while (fscanf(dict, "%s\n", dictWord) != EOF) // how does this know when a word ends without using the string null terminator?
{
    // malloc a new node to hold the word
    wordNode = malloc(sizeof(node));
    if (wordNode == NULL)
    {
        unload();
        return 2;
    }
    // copy the word scanned from the dictionary into the new node
    strcpy(wordNode->word, dictWord);

    // get index of hashtable array to put wordNode in
    int index = hash(dictWord);  // returns an int between 0 and 26

    // if no linked list at array index, add new new node
    if (hashtable[index] == NULL)
    {
        hashtable[index] = wordNode; // hashtable[index] points at wordNode
        wordNode->next = NULL; // no second node so doesn't hold memory address
    }
    // if linked list at array index, prepend
    else
    {
        wordNode->next = hashtable[index]; // new node points at head of linked list (i.e. at hash table pointer)
        hashtable[index] = wordNode; // head of linked list points at new node
    }

    // increment word count to use in size function
    wordCount++;

}
free(&wordNode);

// close file
fclose(dict);

// return true if successful
return true;
}

/**
 * Returns number of words in dictionary if loaded else 0 if not yet 
loaded.
 */
unsigned int size(void)
{
// if loaded, return number of words in dictionary
if (wordCount > 0)
{
    return wordCount;
    eprintf("Word count: %d", wordCount);
}
// else, return 0
else
    return 0;
}

/**
 * Unloads dictionary from memory. Returns true if successful else 
false.
 */
bool unload(void)
{
    // TODO
    return false;
}
0

I worked out the source of the segmentation fault / valgrind error so I thought it might be useful to answer my own question in case someone else has the same problem.

The problem was with the hash function as valgrind identified this line:

int index = hash(dictWord);

I don't know what the hash function was returning (an 8 byte int or other value?), but when I replaced it with a different hash function I stopped getting the error.

You must log in to answer this question.

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