(CS50/pset5/speller) I have a memory leak issue, according to check50 and valgrind. I think I'm using a variable that doesn't have a value

Question

I have a memory leak issue, according to check50 and valgrind. It looks like I'm trying to use a variable that might not have a value. Everything else works correctly, according to check50, the only issue is with memory. Here is valgrind's error message:

==3243== Conditional jump or move depends on uninitialised value(s)
==3243==    at 0x520A60F: tolower (ctype.c:46)
==3243==    by 0x4010CD: check (dictionary.c:36)
==3243==    by 0x400CD9: main (speller.c:112)
==3243==  Uninitialised value was created by a stack allocation
==3243==    at 0x4008E4: main (speller.c:21)
==3243== 
==3243== Use of uninitialised value of size 8
==3243==    at 0x520A623: tolower (ctype.c:46)
==3243==    by 0x4010CD: check (dictionary.c:36)
==3243==    by 0x400CD9: main (speller.c:112)
==3243==  Uninitialised value was created by a stack allocation
==3243==    at 0x4008E4: main (speller.c:21)
==3243== 

WORDS MISSPELLED:     0
WORDS IN DICTIONARY:  143091
WORDS IN TEXT:        6
TIME IN load:         1.46
TIME IN check:        0.00
TIME IN size:         0.00
TIME IN unload:       0.21
TIME IN TOTAL:        1.67

==3243== 
==3243== HEAP SUMMARY:
==3243==     in use at exit: 0 bytes in 0 blocks
==3243==   total heap usage: 143,097 allocs, 143,097 frees, 8,023,462 bytes allocated
==3243== 
==3243== All heap blocks were freed -- no leaks are possible
==3243== 
==3243== For counts of detected and suppressed errors, rerun with: -v
==3243== ERROR SUMMARY: 492 errors from 2 contexts (suppressed: 0 from 0)

Asking for help...

==3243== Conditional jump or move depends on uninitialised value(s)

Looks like you're trying to use a variable that might not have a value? Take a closer look at line 36 of dictionary.c.

Here is my code (I would love if you could help ;))

// Implements a dictionary's functionality

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

#include "dictionary.h"

#define HASHTABLE_SIZE 65536

// 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 = HASHTABLE_SIZE;

// Hash table
node *table[N];
unsigned int totalWords = 0;

// Returns true if word is in dictionary else false
bool check(const char *word)
{
    //Initialize lower case word
    char lcword[LENGTH + 1];

    for (int i = 0; i < LENGTH + 1; i++)
        lcword[i] = tolower(word[i]);


    node *cursor = table[hash(lcword)];

    while (cursor != NULL)
    {
        if (strcasecmp(word, cursor->word) == 0)
        {
            return true;
        }

        cursor = cursor->next;
    }

    return false;
}

// Hashes word to a number
unsigned int hash(const char *word)
{
    //https://www.reddit.com/r/cs50/comments/1x6vc8/pset6_trie_vs_hashtable/cf9nlkn/
    unsigned int hash_value = 0;

    for (int i = 0, n = strlen(word); i < n; i++)
        hash_value = (hash_value << 2) ^ word[i];

    return hash_value % HASHTABLE_SIZE;
}

// Loads dictionary into memory, returning true if successful else false
bool load(const char *dictionary)
{

    FILE *dicfile = fopen(dictionary, "r");
    char *word = malloc(LENGTH + 1);

    //Check if word is null
    if (word == NULL)
        return false;

    //Check if the fopen function opened a not NULL file
    if (dicfile == NULL)
       return false;

    //Iterate over dictionary until fscanf return EOF (meaning it's the end of the file)
    while (fscanf(dicfile, "%s", word) != EOF)
    {
        //Create a node to store the current word
        node *new_node = malloc(sizeof(node));

        if (new_node == NULL)
            return false;

        //Copy the new_node's word into the current word
        strcpy(new_node->word, word);

        //Get the index (hash the current word and store it in n)
        int n = hash(new_node->word);

        //Insert the new_node into the linked list
        new_node->next = table[n];
        table[n] = new_node;

        //Add to the total number of words in the text file
        totalWords++;
    }

    fclose(dicfile);
    free(word);
    return true;
}

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

// Unloads dictionary from memory, returning true if successful else false
bool unload(void)
{

    for (int i = 0; i < HASHTABLE_SIZE; i++)
    {
        node* cursor = table[i];
        node* tmp;

        while (cursor != NULL)
        {
            tmp = cursor;
            cursor = cursor->next;
            free(tmp);
        }
        free(cursor);
    }
    return true;
}

And if you want to know, line 36 of my code is this one: lcword[i] = tolower(word[i]);

Thank you!!!

Answer 1

regarding:

for (int i = 0; i < LENGTH + 1; i++)

in C, the valid range of indexes into an array are 0...(number of elements in array-1 ) Note the -1

Note: the macro: LENGTH is not defined anywhere in the posted code.

the function: check() is implemented in the posted code, but never called.

regarding:

for ( int i = 0, n = strlen(word); i < n; i++)

The function: strlen() returns a size_t, so the statement should be:

for ( size_t i = 0, n = strlen(word); i < n; i++ )

The function: size() is implemented but never called.

it is a very poor programming practice to include header files those contents are not used. for instance:

#include <strings.h>

regarding;

if (dicfile == NULL)
   return false;

This should be immediately after;

FILE *dicfile = fopen(dictionary, "r");

and should include the statement:

perror( "fopen to read dictionary file failed" );

regarding:

while (fscanf(dicfile, "%s", word) != EOF)

there are other reasons that a call to fscanf() can fail. Should be checking for success.

the %s input format conversion specifier can input more characters than there are in the array word(). Also, that specifier always appends a NUL byte to the input. To avoid any buffer overflow problems, always use a modifier that 1 less than the length of the buffer. Suggest:

while (fscanf(dicfile, "%" LENGTH "s", word) == 1)

regarding your question about a memory leak:

The posted code modifies pointers (by overlaying them) in table[] without first checking of there is already an active entry there. If there is an active entry already at the 'hashed' index into the table, then the new entry must be linked after (could be linked before) the current entry, at the same index into table[]

Of course, when an active entry is overlayed, the result is a memory leak.