pset5/speller Check produces a segfault if I introduce hash function

Question

If I have a single bucket, the program runs seamlessly, however when I introduce the djb2 hash function as seen here the program produces a segfault. Here's my code with the hash function commented as tried last time. The problem has also got no problem actually hashing the values, which leads me to believe I migh have some kind of error in the check function.

// Implements a dictionary's functionality

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

#include "dictionary.h"

// Represents a node in a hash table
typedef struct node
{
    char word[LENGTH + 1];
    struct node *next;
}
node;

// Count words in dictionary
unsigned int w_count = 0;


// Number of buckets in hash table
const unsigned int N = 180000;

// Hash table
node *table[N];

// Returns true if word is in dictionary else false
bool check(const char *word)
{
    // these lines by themselves don't give segfault
    int hashed = hash(word);
    node *tmp = table[hashed];

    do
    {
        if (strcasecmp(tmp->word, word) == 0)
        {
            return true;
        }
        tmp = tmp->next;
    }
    while (tmp != NULL);
    return false;
}

// Hashes word to a number using the djb2 hash function as seen
// here: http://www.cse.yorku.ca/~oz/hash.html
unsigned int hash(const char *word)
{
    // unsigned long hash = 5381;
    // int c;

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

    // return (hash % N);
    return 0;
    }

// Loads dictionary into memory, returning true if successful else false
bool load(const char *dictionary)
{
    // load dictionary file
    FILE *fdict = fopen(dictionary, "r");
    if (fdict == NULL)
    {
        printf("Invalid file\n");
        return false;
    }

    // Allocate spacefor word
    char *word = malloc(LENGTH + 1);

    // scan file for each word until EOF
    while (fscanf(fdict, "%s", word) != EOF)
    {
        // declare a new node pointing to null with a word
        node *n = malloc(sizeof(node));
        if (n == NULL)
        {
            return false;
        }
        n->next = NULL;

        // copy string into node
        strcpy(n->word, word);

        // hash the word
        int hashed = hash(n->word);

        //place next at the first hashed value
        //then change value of head for current n
        n->next = table[hashed];
        table[hashed] = n;

        //add to word count
        w_count++;
    }

    //free word variable
    free(word);

    return true;
}

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

// Unloads dictionary from memory, returning true if successful else false
bool unload(void)
{
    // for (i = 0; i < N; i++)
    // {
    //     node
    // }
    return false;
}

All help is much appreciated. thank you very much!

Answer 1

The reason for the seg faults lies in check() It uses a do/while setup that checks whether temp is null after running the loop. If the bucket was empty and table[hashed] is NULL, then it's going to generate a seg fault. This is highly likely with a small dictionary. Use a standard while loop instead.

The next problem is that check() tries to hash whatever word is entered, but without converting to all lower case. That means that "cat" and "Cat" will generate two different hash values.

That should get you going.

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