pset 5 - speller: Hash function gets stuck with strlen() and I don't know why. Furthermore I'm lacking memory

Question

I have several problems with my speller code and debug50 wont help me. I sat in front of it for hours now. Just want to know, where to start. Have no clue.

At first Debug50 gets stuck at strlen() in the hash function at line 7, at least I think that's the problem. Debug fifty just pauses with no error code. I think, there might be an issue with the word pointer?

// Hashes word to a number
unsigned int hash(const char *word)
{
    int sum = 0;
    unsigned int hash_sum = 0;
    //letters in passed *word may contain upper letters!
    int word_length = strlen(word);

    //everything to lower
    char letters[word_length + 1];
    for (int i = 0; i < word_length; i++)
    {
        letters[i] = tolower(word[i]);
    }

    //calculate hash_sum with lower letters
    for (int i = 0; i < word_length; i++)
    {
        sum += letters[i];
    }
    hash_sum = (sum * 999) % N;

    return hash_sum;
}

Furthermore I think there is a problem with my unload function? I'm lacking memory... I might have made a mistake with the for-loop and the pointers... The whole code:

// Implements a dictionary's functionality

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

#include "dictionary.h"

int dict_size = 0;

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

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

// Hash table
node *table[N];

// Returns true if word is in dictionary, else false
bool check(const char *word)
{
    int check_hash = hash(word);
    node* check_temp = malloc(sizeof(node));

    for (check_temp = table[check_hash]; check_temp->next != NULL; check_temp = check_temp->next)
    {
        if (strcasecmp(check_temp->word, word) == 0)
        {
            return true;
        }
    }
    return false;
}

// Hashes word to a number
unsigned int hash(const char *word)
{
    int sum = 0;
    unsigned int hash_sum = 0;
    //letters in passed *word may contain upper letters!
    int word_length = strlen(word);

    //everything to lower
    char letters[word_length + 1];
    for (int i = 0; i < word_length; i++)
    {
        letters[i] = tolower(word[i]);
    }

    //calculate hash_sum with lower letters
    for (int i = 0; i < word_length; i++)
    {
        sum += letters[i];
    }
    hash_sum = (sum * 999) % N;

    return hash_sum;
}

// Loads dictionary into memory, returning true if successful, else false
bool load(const char *dictionary)
{
    FILE* fileptr = fopen(dictionary, "r");
    if (fileptr == NULL)
    {
        unload();
        fclose(fileptr);
        return false;
    }

    char word[LENGTH + 1];
    while (fscanf(fileptr, "%s", word) != EOF)
    {
        //calculate hash value
        int hash_value = hash(word);

        //make new temp node 'temp' and assign values
        node* temp = malloc(sizeof(node));
        if (temp == NULL)
        {
            fclose(fileptr);
            return false;
        }

        strcpy(temp->word, word);

        //insert in linked list: if no other node at this location of table yet
        if (table[hash_value] == NULL)
        {
            temp->next = NULL;
        }
        else
        {
            temp->next = table[hash_value];
        }
        table[hash_value] = temp;
        free(temp);
        dict_size++;
    }

    //printf("first string of list is: %s\n", table[0]->word);

    fclose(fileptr);
    return true;
}

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

// Unloads dictionary from memory, returning true if successful, else false
bool unload(void)
{
    node* temp = malloc(sizeof(node));
    node* cursor = malloc(sizeof(node));
    if ((temp != NULL) && (cursor != NULL))
    {
        cursor = temp;
        for(int i = 0; i < N; i++)
        {
           for(temp = table[i]; cursor != NULL; temp = cursor)
           {
                cursor = temp->next;
                free(temp);
           }
        }
        free(cursor);
        return true;
    }
    else
    {
        free(temp);
        free(cursor);
        return false;
    }
}

Check50 states https://submit.cs50.io/check50/f749baea58d3cf6b3d17ee14477f0463697e348c

Answer 1

First, let me say that I'm responding to your specific questions, not doing a full analysis of your code. I want to give you the chance to work through your issues. ;-)

I've run into the same kind of problem with debug. It gets to a library function like strlen and stalls. I found that using the "step over" control instead of "step into" will usually bypass this stallout behavior.

Now, let's look at unload. It starts by creating a memory leak by mallocing memory to temp and cursor. When other addresses are assigned to these two vars, the original allocated memory is lost. Instant memory leak.

It's a common newbie mistake. Many new programmers believe that you must malloc memory to a pointer when it is created. Not true. Instead, it can be initialized to NULL and used later. Best practice is to initialize a pointer immediately when created by EITHER setting to NULL, allocating memory to it, or assigning an already allocated address from another pointer. Don't ever create a pointer and not assign something to it.

Once this is fixed, you should see that some of the code in unload can and should be removed. Consider how the function could be implemented with a for loop and a while loop nested inside.

Hint: when you need to implement a loop based on fixed number (including a value stored in a var), a FOR loop is usually the best tool. When looping based on a certain condition being true, but the number of iterations is indeterminate or unknown, a while loop is usually the tool of choice, even though it can be done with a for loop. It's still good to know how to implement a while loop's function as a for loop, as you have done with one of your loops. ;-)

I'll let you consider how to rewrite your unload function based on this info. ;-)

As for your check50 results, it appears that your code is finding all words misspelled. I would suggest that you set unload to return true without doing anything until you get everything else working, or working on memory leaks.

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