0

I've finally got my speller to work for the large dictionary and the given texts. Valgrind doesn't give any errors anymore. However, check50 fails, because the 'actual output' received there does not match the expected output. When I run speller, the output does match the expected output, which puzzles me. I found out that somehow, speller does not work when I use a small dictionary - it will return a segmentation fault when reading the unload function (line: while(cursor->next != NULL)). I'm puzzled. Any hints, advice or help would be greatly appreciated.

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

#include "dictionary.h"


//define node structure to make linked lists possible. A node consist of a dicword (char) and a pointer to another node.
typedef struct node
{
    char dicword[LENGTH+1];
    struct node *next;
}
node;

//create a hash table (size 2)
#define HASHMAX 32
node *hashtable[HASHMAX];
// hash function by Gabriel Staples: https://stackoverflow.com/questions/7666509/hash-function-for-string

unsigned int hash(const char *str)
{
    unsigned hashval;

    for (hashval = 0; *str != '\0'; str++)
        hashval = *str + 31*hashval;
    return hashval % HASHMAX;
}

//create counter for dictionary words
int dicwords = 0;

//CHECK Returns true if word is in dictionary else false.

bool check(const char *word)
{
    //hash the word to receive index for hashtable
    int index = hash(word);
    //input index in hashtable to retrieve the right llist. If the llist is empty, return false.
    if(hashtable[index]==NULL)
    {
        return false;
    }
    //if llist is not empty, run through list and compare word with each element of that list, untill end of list (null) is reached.
    else
    {
       node *cursor = hashtable[index];
       while(cursor != NULL)
       {
           if(strcasecmp(cursor->dicword, word) ==0)
           {
               return true;
           }

           cursor = cursor->next;
       }
       return false;
    }
}

//LOAD Loads dictionary into memory. Returns true if successful else false.    
bool load(const char *dictionary)
{
    //set values in hash table to null
    for(int h = 0; h < HASHMAX; h++)
    {
        hashtable[h] = NULL;
    }
    //open dictionary for reading
    FILE *dic = fopen(dictionary, "r");
     if (dic == NULL)
     {
         return false;
     }
    char newword[LENGTH+1];

    //scan dictionary (dic) and store each string until space in 'newword'
    while (fscanf(dic,"%s", newword)!=EOF)
    {
        node *new_node = malloc(sizeof(node));
        new_node->next=NULL;
        //if malloc fails, return false
        if(new_node == NULL)
        {
           unload();
           return false;
        }
        //if malloc works, copy 'newword' to the word-space in the new node
        else
        {
            strcpy(new_node->dicword, newword);
            dicwords++;
             //allocate the new node to the correct list, using hash(word).
            new_node->next=hashtable[hash(newword)];
            hashtable[hash(newword)]=new_node;
        }
     }

fclose(dic);
return true;
}  

/**
 * Returns number of words in dictionary if loaded else 0 if not yet loaded.
 */
unsigned int size(void)
{
    if (dicwords>0)
    {
        return dicwords;
    }
    else
    {
      return 0;  
    }
}

/**
 * Unloads dictionary from memory. Returns true if successful else false.
 */
bool unload(void)
{
    for (int u = 0; u<HASHMAX; u++)
    {
        node *cursor = hashtable[u];
        while(cursor->next != NULL)
        {
            node *temp = cursor;
            cursor = cursor->next;
            free(temp);
        }
        free(cursor);

    }
    return true;

}
3

Think about what's happening. When using the full dictionary, there are words for every letter of the alphabet. Since your hashmax is 32, there's also a really good chance that every possible hash number is used.

Now, think about what happens when you use a small dictionary with a few words. Some of the hash numbers will not be used. The hashtable is initialized with all its pointers set to NULL, and will remain unchanged. Next, look at the code that is throwing the error: while(cursor->next != NULL). If cursor == NULL, cursor->next doesn't exist. That's what causes the seg fault. That's why the small dictionary fails and the large one passes.

Finally, what happens in check50? It uses several small dictionaries to test for specific corner cases. Because of that, it's throwing seg faults. You know the rest. ;-)

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

| improve this answer | |
  • Thanks! I reached the same conclusion after thinking it over once more. Thanks for you clear explanation! Changed cursor->next != NULL to cursor != NULL, works like a charm :) – AmLam Aug 16 '17 at 20:15
  • Thought it would. Now, can you please accept my answer so that the question doesn't sit in the unanswered question pool forever? thanks. – Cliff B Aug 16 '17 at 20:25

You must log in to answer this question.

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