0

I've been trying to figure this out, I followed walkthrough step by step, but can't find the answer.

When I run the code with debug50 using large dictionary and some small size text file it works, reports misspelled words, size of dict, time etc. But when I run ./speller textfile.txt it throws segmentation fault.

Here is the code...

    /**
     * Implements a dictionary's functionality.
     */

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

    #include "dictionary.h"

    // create node structures for linked lists
    typedef struct node
    {
        char word[LENGTH + 1];
        struct node *next;
    }
    node;

    // create hashtable with 50 buckets
    #define HASHSIZE 50
    node *hashtable[HASHSIZE];

    // djb2 hash function
    unsigned long hash(const char *str)
    {
        unsigned long hash = 5381;
        int c = 0;

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

        return hash;
    }

    // keep track of number of words in dictionary
    int wordCount = 0;

    /**
     * Returns true if word is in dictionary else false.
     */
    bool check(const char *word)
    {
        // find in which bucket word should be
        int i = hash(word);

        // define first node of linked list (head) and cursor
        node *head = hashtable[i];
        node *cursor = head;

        // iterate through linked list and compare strings
        while(cursor != NULL)
        {
            if(strcasecmp(word, cursor->word) == 0)
            {
                return true;
            }
            else
            {
                cursor = cursor->next;
            }
        }
        return false;
    }

    /**
     * Loads dictionary into memory. Returns true if successful else false.
     */
    bool load(const char *dictionary)
    {
        // try to open dictionary
        FILE *dct = fopen(dictionary, "r");
        if(dct == NULL)
        {
            return false;
        }

        // declare variable to store words from dictionary
        char dctWord[LENGTH + 1];

        // scan dictionary word by word
        while(fscanf(dct, "%s", dctWord) != EOF)
        {
            // get memory for node to store words into
            node *new_node = malloc(sizeof(node));

            // if returns NULL, quit the speller, else set dctWord as 
            // new_node value
            if(new_node == NULL)
            {
                unload();
                return false;
            }
            // else copy word from dictionary to node, find its position in 
            // hashtable,
            // link it to first node in that linked list, and move head to 
            // that node. increment word count
            else
            {
                strcpy(new_node->word, dctWord);
                int head = hash(dctWord);
                new_node->next = hashtable[head];
                hashtable[head] = new_node;
                wordCount++;
            }
        }
        fclose(dct);
        return true;
    }

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

    /**
     * Unloads dictionary from memory. Returns true if successful else 
     * false.
     */
    bool unload(void)
    {
        // iterate through hashtable and free all nodes in each bucket 
        // (linked list)
        for(int i = 0; i < HASHSIZE; i++)
        {
            node *cursor = hashtable[i];

            while(cursor != NULL)
            {
                node *temp = cursor;
                cursor = cursor->next;
                free(temp);
            }
        }
        return true;
    }
1

The reason it does not give a seg fault under gdb is because of different memory usage than when it's run from the command line. The problem lies in the hash function. You might have started out with the line while (c = *str++), but the compiler complained and gave 2 possible solutions either place parentheses around assignment or use '==' to turn this assignment into an equality comparison. The correct choice is the first, because you want to use the result of the assignment as the condition. To see this in action, put breakpoints in the hash function and you'll see that the while loop never executes and the function always returns hash a 5381, it's initial value. Which segues nicely to a second problem.

hashtable is defined with 50 elements. If program returns hash of 5381, boom, seg fault (again, under gdb/debug50 memory management is different). You are going to need a way to make sure that hash is in the range 0 - 49. Think modulo.

1
  • Thank you very much. Because in walkthrough they said you can use already made hash functions, i just found this one which seemed least complicated, but didn't quite understand the whole syntax. But modulo sure solved it.
    – I J
    Sep 11 '17 at 4:53

You must log in to answer this question.

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