CS50 Speller Not Free of Memory Errors

Question

When I run check50 on my code, valgrind says:

Conditional jump or move depends on uninitialised value(s): (file: dictionary.c, line: 34) 112 bytes in 2 blocks are still reachable in loss record 1 of 1: (file: dictionary.c, line: 88)

Line 34 refers to: while (strcasecmp(word, c->word) != 0 && c->next != NULL)

Line 88 refers to: node *n = malloc(sizeof(node));

I have tried running my code with valgrind on my own, but these errors don't appear then.

This is my code:

// Implements a dictionary's functionality

#include <stdbool.h>

#include <stdio.h>

#include <stdlib.h>

#include <string.h>

#include <ctype.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;

// Number of buckets in hash table

const unsigned int N = 26;

// Hash table

node *table[N];

int count = 0;

// Returns true if word is in dictionary else false

bool check(const char *word) { // TODO

int place = hash(word);

node *c = table[place];

while (strcasecmp(word, c->word) != 0 && c->next != NULL)
{
    c = c->next;
}

if (strcasecmp(word, c->word) == 0)
{
    return true;
}

else
{
    return false;
}

}

// Hashes word to a number

unsigned int hash(const char *word)

{ // TODO

char alphabet[26];

for (int x = 0; x < 26; x++) //fills solution[] with acii values of the alphabet in capital letters
{
    alphabet[x] = 65 + x;
}

for(int y = 0; y < 26; y++)
{
    if (toupper(word[0]) == alphabet[y])
    {

        return y;
    }
}

return 0;

}

// Loads dictionary into memory, returning true if successful else false

bool load(const char *dictionary) { // TODO

int index = 0;

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

if (file == NULL)
{
    return false;
}

char array[LENGTH];

while (fscanf(file, "%s", array) != EOF)
{
    node *n = malloc(sizeof(node));

    if (n == NULL)
    {
        return false;
    }
    
    strcpy(n->word, array);

    index = hash(array);
    
    if (table[index] == NULL)

    {
        table[index] = n;
    }
    
    else
    {
        n->next = table[index];

        table[index] = n;
    }

    count++;
}

fclose(file);

return true;

}

// Returns number of words in dictionary if loaded else 0 if not yet loaded

unsigned int size(void)

{ // TODO

return count;

}

// Unloads dictionary from memory, returning true if successful else false

bool unload(void)

{ // TODO

node *cursor = table[0];

node *temp = table[0];

for (int x = 0; x < N; x++)

{
    while(cursor != NULL)
    {

    cursor = table[0]->next;

    free(temp);
    }
}

return true;

}

Answer 1

I would expect this program to seg fault.

With the small dictionary, check will segfault here

while (strcasecmp(word, c->word) != 0 && c->next != NULL)  

If table[place] is not poplulated (ie NULL), c->word (and c->next) do not exist. Start comparing words at the start of the list (ie table[place], ie c) and push c (ie c = c->next) when the word doesn't match.

With the large dictionary (or any dictionary that has 2 or more "a" words), unload will seg fault here free(temp); when it tries to free table[0] the second time (temp never changes value). This function needs work. Since all nodes need to be freed, it shouldn't name table[0] explicitly. The head of each list should be based on N (ie table[N]).