0

I am really stuck at why my cursor is set to NULL in check. This is my code

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

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

#define ALPHABET 26
#define BUCKETS 1000


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

// create hashtable array
node *hashtable[BUCKETS];



// hash function from http://stackoverflow.com/questions/7666509/hash-function-for-string
unsigned long hash(const char *word)
{
    unsigned long hash = 5381;
    int c = 0;
    c = tolower(c);

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

    return (hash % BUCKETS);
}

int counter = 0;

/**
 * Returns true if word is in dictionary else false.
 */
bool check(const char *word)
{

    int val = hash(word);

    node *cursor = hashtable[val];

    while (cursor != NULL)
    {

        // if we found the word
        if(strcasecmp(word, cursor->word) == 0)
        {
            return true;
        }

        // if we haven't, iterate to the next one
        cursor = cursor->next;
    }
    return false;
}


/**
 * Loads dictionary into memory. Returns true if successful else false.
 */
bool load(const char *dictionary)
{
    FILE *dict = fopen(dictionary, "r");
    if (dict == NULL)
    {
        printf("Could not open %s.\n", dictionary);
        return false;
    }

    char BUFFER[LENGTH + 1];

    while (fscanf(dict, "%s", BUFFER) != EOF)
    {
        node *new_node = malloc(sizeof(node));

        // free node if allocated null space
        if (new_node == NULL)
        {
            unload();
            return false;
        }

        //fscanf(dict, "%s", new_node->word);
        int value = hash(new_node->word);

        hashtable[value] = new_node;
        strcpy(new_node->word, BUFFER);

        //int value = hash(new_node->word);

        new_node->next = hashtable[value];
        //hashtable[value] = new_node;

        // count this for the total number of words
        counter++;


        return true;
    }

    return true;
}


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

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

There are a number of issues in this code. Starting with load(), it will only process one word from the dictionary because of the return true; statement inside the while loop. Next, since new_node is not initialized, it contains garbage data. The contents of new_node->word is being sent to the hash function before the word is actually copied into new_node->word, so it's returning garbage! Interestingly, it hashes the same value on my system on each pass, after the return statement is removed. Nevertheless, it's not hashing the dictionary words.

Next, each time a new node is added to the hash table, any prior entries for that hash will be lost. The problem is ordering. The code first sets hashtable[hash] = new_node and then sets new_node->next = hashtable[hash], in other words, points new_node->next at new_node. This is essentially a very small circular linked list of 1 element. Prior entires are lost. The order of these two actions are reversed.

In either check or hash, the letters of the word being hashed need to be converted to lower case. It isn't happening. You may think you have done it in hash, but no. Look at the following lines:

int c = 0;
c = tolower(c);

while ((c = *word++))

c is an int and is set to 0, it isn't a letter. When passed anything that is not an uppercase letter, tolower() will simply return whatever it was passed - in this case, 0. No letters are ever passed to tolower(). Instead, tolower() should be applied to the value being assigned to c. I'll let you figure out to code it. ;-) It is absolutely critical that a given word, regardless of letter case, returns the same hash value from both load and from check.

The seg fault is occurring in unload. I'm not sure, but I suspect that the circular linking described earlier may be the cause. Once you fix load, this problem may disappear on it's own. (Given the number of issues and code fixes that you may implement, and that they may be very different from what I might do, I'll pass on doing any extensive debugging here.) Until you fix load(), I would simply put a return true statement in as the first line of unload(), and debug it last.

There may or may not be more problems, but these have to be fixed first. How you fix them will surely impact whether there are other issues, or whether new ones are introduced. Once you've done the major recoding, if you get blocked again, it'll be time for a new question. But this should get you going again.

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

You must log in to answer this question.

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