0

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!

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. ;-)

3
  • I know that this was answered a while back, but can you explain why converting to lower-case is necessary? If we are using the 'strcasecmp' function, shouldn't that handle upper and lowercase differences? – QueenofQuantum Oct 2 '20 at 3:18
  • Also since the word is accessed via a pointer, wouldn't converting it to lowercase permanently change the word? – QueenofQuantum Oct 2 '20 at 4:34
  • The use of strcasecmp() is only half the picture. The other half is that the code needs to produce the same hash number no matter what case is used. In most hash functions, "Cat" and "cat" will produce different hash numbers. If it doesn't produce the correct hash, the code will never find the word in the dictionary. As for changing the case of the word, it really doesn't matter. The only issue is whether the spelling is correct, not the case of the letters. Note that this only applies here. If we were discussing a dictionary where it mattered whether a word started with a cap, it would. – Cliff B Oct 2 '20 at 5:59

You must log in to answer this question.

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