CS50 pset5 speller line 54 conditional jump error

Question

When I compile and run my code it sort of looks like the code works, but when I run Valgrind with help50, it says "==1295== Conditional jump or move depends on uninitialized value(s)" I don't get how to fix this problem. Help50 tells me to focus on line 54 of my code, but I don't understand what is wrong, it was working before, now it is a mistake. What I don't understand is what the mistake is/

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

// 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 = 10000;
int i = 0;

// Hash table
node *table[N];

// Returns true if word is in dictionary else false
bool check(const char *word)
{
    char lword[LENGTH+1];
    for(i = 0; i < strlen(word); i++)
    {
        lword[i] = word[i];
        lword[i] = tolower(lword[i]);
    }
    node *current;
    int hashnum = hash(lword);
    if(table[hashnum] == NULL)
    return false;
    current = table[hashnum];
    while(current->next != NULL)
    {
        if(strcmp(current->word, word) == 0)
        return true;
        else
        current = current->next;
    }
    return false;
}

// Hashes word to a number
// Hash function from cs50.stackexchange
unsigned int hash(const char *word)
{
    int n;
    unsigned int hash_value = 0;
    for (i = 0, n = strlen(word); i < n; i++)
    {
         hash_value = (hash_value << 2) ^ word[i];
    }
    return hash_value % N; //N is size of hashtable
}
// Loads dictionary into memory, returning true if successful else false
// adopted from github user
int word_count = 0;
bool load(const char *dictionary)
{
    FILE *file = fopen(dictionary, "r");
    if (file == NULL)
    {
        return false;
    }
    char word[LENGTH + 1];
    while (fscanf(file, "%s", word) != EOF)
    {
        node *new_node = malloc(sizeof(node));
        if (new_node == NULL)
        {
            free(new_node);
            return false;
        }
        strcpy(new_node->word, word);
        int h = hash(new_node->word);
        node *head = table[h];
        if (head == NULL)
        {
            table[h] = new_node;
            word_count++;
        }
        else
        {
            new_node->next = table[h];
            table[h] = new_node;
            word_count++;
        }
    }
    fclose(file);
    return true;
}


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

// Unloads dictionary from memory, returning true if successful else false
bool unload(void)
{
    for(i=0;i<10000;i++)
    {
        for(i = 0; i < 10000; i++)
    {
        while(table[i] != NULL)
        {
            char *retval = NULL;
            if (table[i]->next == NULL)
            {
                retval = table[i]->word;
                free(table[i]);
                return retval;
            }
            else
            {
                node * current = table[i];
                while (current->next->next != NULL)
                {
                    current = current->next;
                }
                retval = current->next->word;
                free(current->next);
                current->next = NULL;
            }
        }
    }
    }
return true;
}

Answer 1

You have a large number of problems. The primary problem leading to the valgrind conditional move based on uninitialized value is your failure to initialize the ->next pointer NULL in load(), e.g.:

        node *new_node = malloc(sizeof(node));
        if (new_node == NULL)
        {
//             free(new_node);                  /* not necessary */
            return false;
        }
        strcpy(new_node->word, word);
        new_node->next = NULL;                  /* must initialize NULL */

That will resolve the valgrind issues.

C is not C++. const unsigned int N = 10000; does not create an integer constant resulting in node *table[N]; being a VLA (Variable Length Array) of pointers to node rather than an array of pointers to node. This is a problem resulting in the error:

error: variably modified ‘table’ at file scope

(it is unclear how you were able to compile with gcc with the VLA. See C11 Standard - 6.7.6.2 Array declarators(p2))

Instead, you need to #define the value for N, use a global enum or move the declaration of table to block or function scope. (note, N should be at least ten-times as large to keep the number of hash collisions -- and the hash table Load Factor [buckes_used/total_buckets] below 0.7)

Type Matters

Your hash function is declared as:

unsigned int hash(const char *word)

It returns type unsigned int, you should not be assigning the result to int. While the modulo will keep the value returned in the range of positive integer values, that is playing with fire.

//     int hashnum = hash(lword);
    unsigned int hashnum = hash(lword);

In other circumstances, if bit-31 is 1, your assignment to int will result in the value being negative -- and if used as an array index, results in Undefined Behavior.

The unload() function is much much more convoluted that necessary. You have a global array table used as your hash table. The only thing that needs to be freed are any nodes in buckets that are not empty. So you simply need to loop over each bucket and check if it is empty. If not, then traverse the list that starts with the bucket element freeing each node, e.g.:

bool unload(void)
{
//     for(size_t i=0; i<10000;i++)       /* you have a constant -- use it */
    for(size_t i=0; i<N;i++)
    {
        node *n = table[i];
        while (n) {
            node *victim = n;
            n = n->next;
            free (victim);
        }
    }
    
    word_count = 0;
    
    return true;
}

Unnecessary Code

There are several places where you code isn't wrong, but involves additional copying or unnecessary calls to free(), etc.. For example in check(), there is no need to assign to lword[i] just to assign the value again after converting to lowercase. Just convert to lowercase and assign:

    for (size_t i = 0; i <= strlen(word); i++)
        lword[i] = tolower(word[i]);
//     {
//         lword[i] = word[i];
//         lword[i] = tolower(lword[i]);
//     }

In load(), if the allocation of new_node fails, there isn't any need to free(new_node);, as shown earlier. Why? When malloc() fails, it returns NULL. There is nothing allocated. Though free(NULL); is harmless (free() will check for you), it's simply unnecessary.

Resulting Memory Use

If you make all of the changes, your code will now run without memory error and will free the memory it allocated, e.g.

$ valgrind ./bin/speller texts/lalaland.txt > test/lalaland.txt
==28984== Memcheck, a memory error detector
==28984== Copyright (C) 2002-2017, and GNU GPL'd, by Julian Seward et al.
==28984== Using Valgrind-3.13.0 and LibVEX; rerun with -h for copyright info
==28984== Command: ./bin/speller texts/lalaland.txt
==28984==
==28984==
==28984== HEAP SUMMARY:
==28984==     in use at exit: 0 bytes in 0 blocks
==28984==   total heap usage: 143,095 allocs, 143,095 frees, 8,022,392 bytes allocated
==28984==
==28984== All heap blocks were freed -- no leaks are possible
==28984==
==28984== For counts of detected and suppressed errors, rerun with: -v
==28984== ERROR SUMMARY: 0 errors from 0 contexts (suppressed: 0 from 0)

I haven't check correctness of all answers, but for lalaland.txt the answer appears correct.

Look things over and let me know if you have further questions.