pset 5 check function

Question

I used hash table to store dictionary in pset5. In order to minimize run time, I chose to cite a hash function online instead of writing my own hash table of maybe 26 rows for 26 letters. I wrote the load, check, and size function. Haven't started unload yet. But when I tried the large dictionary and a short text, it seems the dictionary is loaded successfully (not quite sure), but nothing is checked. All words are listed in the terminal window. Global variables are int word_counter (used to count words in the dictionary loaded) and struct node.

#define DICTIONARY_SIZE 143091

typedef struct node
{
    char word[LENGTH+1];
    struct node* next;
}
node;

//prototype
int word_counter;
node* hashtable[DICTIONARY_SIZE];
int hash (const char* word);

/**
 * Returns true if word is in dictionary else false.
 */
bool check(const char* word)
{
    char lower_word[LENGTH+1];
    for (int i = 0, i < LENGTH+1; i++)
        lower_word[i] = 0;

    //decapatalize words in text
    for (int i = 0, n = strlen(word); i < n; i++)
    {
        if (isupper (word[i]))
        {
            lower_word[i] = tolower(word[i]);
        }
        else
        {
            lower_word[i] = word[i];
        }
    }

    int hashcode = hash(lower_word);

    node* traversal = hashtable[hashcode];

    while (traversal != NULL)
    {
        if (strcmp(lower_word, traversal->word) == 0)
        {
            return true;
        }
        else
        {
            traversal = traversal->next;
        }
    }

    free(traversal);

    return false;
}

/**
 * Loads dictionary into memory.  Returns true if successful else false.
 */
bool load(const char* dictionary)
{
    //open dictionary file
    FILE* in_file = fopen(dictionary, "r");

    //check if the file can be open
    if (in_file == NULL)
    {
        printf("cannot open dictionary file\n");
        return 1;
    }

    word_counter = 0;

    char new_word[LENGTH+1];
    for(int i = 0; i < LENGTH+1; i++)
        new_word[i] = 0;       

    while (fscanf(in_file, "%s", new_word) == 1)
    {
        node* new_node = malloc(sizeof(node));
        strcpy(new_node->word, new_word);

        int hashcode = hash(new_node->word);

        if (hashtable[hashcode] == NULL)
        {
            hashtable[hashcode] = new_node;
            new_node->next = NULL;
            word_counter++;
        }
        else
        {
            new_node->next = hashtable[hashcode];
            hashtable[hashcode] = new_node;
            word_counter++;
        }
    }

    free(new_node);

    fclose(in_file);

    return true;
}

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

bool unload(void)
{
    for (int i = 0; i < DICTIONARY_SIZE; i++)
    {
        node* cursor = hashtable[i];

        while (cursor != NULL);
        {
            node* tmp = cursor;
            cursor = cursor->next;
            free(tmp);
        }

        free(cursor);
    }

    return true;
}

//hash function from http://stackoverflow.com/questions/20462826/hash-function-for-strings-in-c
int hash (const char* word)
{
    int hash = 0;
    int n;
    for (int i = 0; word[i] != '\0'; i++)
    {
        // alphabet case
        if(isalpha(word[i]) || word[i] == '\'')
        {   
            n = word[i] - 'a' + 1;
        }
        //apostrophe case
        else
        {
            n = 27;
        }

        hash = ((hash << 3) + n) % DICTIONARY_SIZE;
    }
    return hash;
}

Answer 1

First of all, you are doing an amazing job! I really like your program and all the information you provide in the question.

I was debugging your program with gdb. In order to "solve" the problem of the misspelled words you can do the following:

Line numbering is based on the code your provided. For example:

#define DICTIONARY_SIZE 143091          // Line #   1

new_node->next = hashtable[hashcode];   // Line #  88

if(isalpha(word[i]) || word[i] == '\'') // Line # 116

1.- Clean lower_word in the check() function with something like this:

for(int i = 0; i < LENGTH+1; i++)
     lower_word[i] = 0;

You can write this code between your lines 20 and 23.

2.- Don't free nodes anywhere other than in the unload() function:

Delete or comment lines 51 and 93:

free(traversal); // 51

free(new_node);  // 93

3.- Create a string variable in the load function so we don't overwrite the words of previous nodes. Also we need to place the malloc() line inside the while loop so we malloc a new node for every new word:

Change these lines ( 72-84 ):

node* new_node = malloc(sizeof(node));

while (fscanf(in_file, "%s", new_node->word) == 1)
{
    int hashcode = hash(new_node->word);

    if (hashtable[hashcode] == NULL)
    {
        hashtable[hashcode] = new_node;
        new_node->next = NULL;
        word_counter++;
    }

To something like this:

// Create string variable.
char lower_word[LENGTH+1];

// Clean string.
for(int i = 0; i < LENGTH+1; i++)
    lower_word[i] = 0;

while (fscanf(in_file, "%s", lower_word) == 1)
{
    // Have malloc line inside loop to malloc for every word.
    node* new_node = malloc(sizeof(node));

    // Copy the contents of the string into the node's word.
    strcpy(new_node->word, lower_word);

    // Continue code as before.
    int hashcode = hash(new_node->word);

    if (hashtable[hashcode] == NULL)
    {
        hashtable[hashcode] = new_node;
        new_node->next = NULL;
        word_counter++;
    }

These changes will allow you to load and check small dictionaries. However I still get a segmentation fault with the large dictionaries.

After I debugged your program, I found with gdb that the hash() function is returning -12572 on the word d'art in the large dictionary. This causes a segmentation fault since we don't have an array with a valid index of -12572.

You might want to review your hash() function.

Also, I don't know how are you debugging you hash function. But in case you find this useful, this is how I thought I could isolate the hash function:

Make a c program called hash.c. Write something like this:

#include <stdio.h>
#include <ctype.h>

int main(int argc, char* argv[]){

    if(argc != 2)
        return 1;

    char* word = argv[1];
    int hash = 0;
    int n;
    for (int i = 0; word[i] != '\0'; i++)
    {
        // alphabet case
        if(isalpha(word[i]) || word[i] == '\'')
        {
            n = word[i] - 'a' + 1;
        }

        hash = ((hash << 3) + n) % 143091;
    }
    printf("%i\n", hash);
}

Compile like this:

make hash

Run like this:

./hash "d'art"