Pset5 Speller - Valgrind issue

Question

this one was tough. But in the end my code compiles fine and has no memory leaks, the hash function isn't very good but it works. Yet I still get an error message that I just don't understand. First, this is my dictionary.c code:

// Implements a dictionary's functionality

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

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

// TODO: Choose number of buckets in hash table
const unsigned int N = 100000;

// Hash table
node *table[N];

int dicsize = 0;

// Returns true if word is in dictionary, else false
bool check(const char *word)
{
    // TODO
    unsigned int hashed = hash(word);

    node *n = table[hashed];

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

        n = n->next;
    }

    return false;
}

// Hashes word to a number
unsigned int hash(const char *word)
{
    // TODO: Improve this hash function
    unsigned long h = 5678;
    int c = 0;

    while (c == *word++)
    {
        h = (5678*h + *word) * 2 + c;
    }

    return h % N;
}

// Loads dictionary into memory, returning true if successful, else false
bool load(const char *dictionary)
{
    // TODO load dic into hash table. output is a number corresponding to which bucket to store the word in
    FILE *dic = fopen(dictionary, "r");

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

    char dicbuffer[LENGTH + 1];

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

        if(n == NULL)
        {
            free(n);
            return false;
        }

        strcpy(n->word, dicbuffer);

        int index = hash(dicbuffer);

        n->next = table[index];
        table[index] = n;
        dicsize++;
    }

    fclose(dic);
    return true;
}

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

    return dicsize;
}

// Unloads dictionary from memory, returning true if successful, else false
bool unload(void)
{
    // TODO
    for(int i = 0; i < N; i++)
    {
        node *cursor = table[i];

        while (cursor != NULL)
        {
            node *tmp = cursor;
            cursor = cursor->next;
            free(tmp);
        }

        if (i == N - 1 && cursor == NULL)
        {
            return true;
        }
    }
    return false;
}

check50 says:

Results for cs50/problems/2023/x/speller generated by check50 v3.3.7
:) dictionary.c exists
:) speller compiles
:) handles most basic words properly
:) handles min length (1-char) words
:) handles max length (45-char) words
:) handles words with apostrophes properly
:) spell-checking is case-insensitive
:) handles substrings properly
:( program is free of memory errors
    valgrind tests failed; see log for more information.

And this is what valgrind spits out. I just don't understand what valgrind wants from me. debug50 and help50 were of no use either.

speller/ $ valgrind -s ./speller texts/cat.txt
==5576== Memcheck, a memory error detector
==5576== Copyright (C) 2002-2017, and GNU GPL'd, by Julian Seward et al.
==5576== Using Valgrind-3.18.1 and LibVEX; rerun with -h for copyright info
==5576== Command: ./speller texts/cat.txt
==5576== 

MISSPELLED WORDS

==5576== Syscall param openat(filename) points to unaddressable byte(s)
==5576==    at 0x4A5D6EB: open (open64.c:41)
==5576==    by 0x49D5135: _IO_file_open (fileops.c:188)
==5576==    by 0x49D5491: _IO_file_fopen@@GLIBC_2.2.5 (fileops.c:280)
==5576==    by 0x49C872D: __fopen_internal (iofopen.c:75)
==5576==    by 0x49C872D: fopen@@GLIBC_2.2.5 (iofopen.c:86)
==5576==    by 0x1099FB: load (dictionary.c:68)
==5576==    by 0x109AF0: size (dictionary.c:104)
==5576==    by 0x1096BD: main (speller.c:145)
==5576==  Address 0x0 is not stack'd, malloc'd or (recently) free'd
==5576== 

WORDS MISSPELLED:     0
WORDS IN DICTIONARY:  143091
WORDS IN TEXT:        6
TIME IN load:         1.37
TIME IN check:        0.48
TIME IN size:         0.01
TIME IN unload:       0.14
TIME IN TOTAL:        1.99

==5576== 
==5576== HEAP SUMMARY:
==5576==     in use at exit: 0 bytes in 0 blocks
==5576==   total heap usage: 143,097 allocs, 143,097 frees, 8,023,728 bytes allocated
==5576== 
==5576== All heap blocks were freed -- no leaks are possible
==5576== 
==5576== ERROR SUMMARY: 1 errors from 1 contexts (suppressed: 0 from 0)
==5576== 
==5576== 1 errors in context 1 of 1:
==5576== Syscall param openat(filename) points to unaddressable byte(s)
==5576==    at 0x4A5D6EB: open (open64.c:41)
==5576==    by 0x49D5135: _IO_file_open (fileops.c:188)
==5576==    by 0x49D5491: _IO_file_fopen@@GLIBC_2.2.5 (fileops.c:280)
==5576==    by 0x49C872D: __fopen_internal (iofopen.c:75)
==5576==    by 0x49C872D: fopen@@GLIBC_2.2.5 (iofopen.c:86)
==5576==    by 0x1099FB: load (dictionary.c:68)
==5576==    by 0x109AF0: size (dictionary.c:104)
==5576==    by 0x1096BD: main (speller.c:145)
==5576==  Address 0x0 is not stack'd, malloc'd or (recently) free'd
==5576== 
==5576== ERROR SUMMARY: 1 errors from 1 contexts (suppressed: 0 from 0)

Any idea what I'm missing?

Answer 1

The clues are in the result returned from valgrind:

==5576== by 0x1099FB: load (dictionary.c:68) ==5576== by 0x109AF0: size (dictionary.c:104)

The error is almost certainly going to be on one of these two lines. Since load() is being called and running, maybe the problem is on line 104 in size(). Let's look at the size function:

unsigned int size(void)
{
    if (load (false))  // line 104
    {
        return true;
    }

    return dicsize;
}

The code inside the if statement on line 104 calls load() with a parameter of false. The parameter should be a filename. So, the behavior is going to be unpredictable.

This is not the way to determine if the load function failed. While it is certainly possible to do so and it's good that you thought to do so, the main program already handles the error checking. The spec says only that the size() function should return the number of words in the dictionary. There's no requirement to validate whether load() ran correctly. Further, it would not be logical to make that check inside the size function. Rather, it should be checked in main, when load is called, or just after.

So, delete the if statement and the code block and do only what is required inside the size() function.

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