0

I'm currently at the CS50's pset5, and am working on the "Speller" problem. I managed to do all functions and don't have any compile or runtime errors. When using check50, though, I receive a sad face (:() on the last line, saying:

:( program is free of memory errors valgrind tests failed; see log for more information.

When I click on the link provided by check50, that's the output for the valgrind:

running valgrind --show-leak-kinds=all --xml=yes --xml-file=/tmp/tmph5epgoz9 -- ./speller substring/dict substring/text...
checking for output "MISSPELLED WORDS\n\nca\ncats\ncaterpill\ncaterpillars\n\nWORDS MISSPELLED: 4\nWORDS IN DICTIONARY: 2\nWORDS IN TEXT: 6\n"...
checking that program exited with status 0...
checking for valgrind errors...
168 bytes in 3 blocks are still reachable in loss record 1 of 1: (file: dictionary.c, line: 80)

Line 80 in my code is part of the load() function that I've completed. This is it:

node *new = malloc(sizeof(node)); // create a new last element in the linked list

Also, here's my full dictionary.c code:

// Implements a dictionary's functionality

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

#include "dictionary.h"

int sz = -1;

// 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];

// Returns true if word is in dictionary, else false
bool check(const char *word)
{
    // TODO
    int key = hash(word);
    node* curr = table[key];

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

// Hashes word to a number
unsigned int hash(const char *word)
{
    // TODO
    return tolower(word[0]);
}

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

    int isRoot[N];

    for (int i = 0; i < N; i++)
    {
        isRoot[i] = 1;
        table[i] = NULL;
    }

    FILE *f;
    if ((f = fopen(dictionary, "r")) == NULL)
    {
        return false;
    }

    char word[LENGTH+1];

    while (!feof(f)) // go through the whole dictionary file
    {
        fscanf(f, "%s", word);

        int key = hash(word); // hash the word

        node *new = malloc(sizeof(node)); // create a new last element in the linked list

        if (new == NULL) // check if malloc() worked properly
        {
            return false;
        }

        strcpy(new->word, word);

        // move the data into the new linked list element

        if (isRoot[key] == 1)
        {
            new->next = NULL;
            table[key] = new;
            isRoot[key] = 0;
        }
        else
        {
            new->next = table[key];
            table[key] = new;
        }

        sz++;
    }

    fclose(f);

    return true;
}

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

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

    for (i = 0; i < N; i++)
    {
        node* curr = table[i];
        while (curr != NULL)
        {
            node* tmp = curr;
            curr = curr->next;
            free(tmp);
        }
        if (curr != NULL)
        {
            return false;
        }
    }

    return true;
}

I firstly thought it might be from the unload() function, but looked up on several similar Stack Overflow questions and I had the exact algorithm for the unload() function (the right one). I don't know what I did wrong. Did I forget to free() memory somewhere? Doesn't my unload() function free all the memory I've allocated with malloc()?

Help would be appreciated. Thank you.

Mateaș Mario
  • 113
  • 1
  • 7
  • 3
    Well. start with [`while (!feof(f))` is wrong](https://stackoverflow.com/questions/5431941/why-is-while-feof-file-always-wrong). Also, the `isRoot` architecture is completely pointless. By definition, a node being put into a hashed-to slot in the table that is currently hosting null is going to be the root. – WhozCraig Jun 27 '21 at 08:17
  • Build with debug information enables (using the `-g` option when building) and Valgrind should be able to tell you exactly when and where the "leaks" happens. And don't write the Valgrind output to an XML file, but rather let it print it all out to the console (in its native non-XML form) so you can easier see it. And also easier to copy-paste it into the question so we can see it. – Some programmer dude Jun 27 '21 at 08:24
  • The code does not call `unload()` which is the only place where `free()` is called. – Weather Vane Jun 27 '21 at 08:25
  • Also, for us to be able to help you more you need to show us a [mcve], including the `main` function and how you use the code you do show. – Some programmer dude Jun 27 '21 at 08:25
  • @WhozCraig, he doesn't set `node->next` to null after malloc. That needs the`isRoot`. – Paul Ogilvie Jun 27 '21 at 08:26
  • Possibly the `!feof()` error reads too large a string, overwriting other stuff. – Paul Ogilvie Jun 27 '21 at 08:27
  • ...and if you do call `unload()` it will never `return false;` but if it did, it would skip the rest of the loop, and not `free()` any more. – Weather Vane Jun 27 '21 at 08:27
  • @PaulOgilvie Should i replace it with a `while(fscanf(f, "%s", word))`? – Mateaș Mario Jun 27 '21 at 08:29
  • @PaulOgilvie `table` is initially null-filled. That entire if-else can be reduced to `new->next = table[key]; table[key] = new;` As I said, that `isRoot` architecture is pointless. – WhozCraig Jun 27 '21 at 08:30
  • @WeatherVane code is calling `unload()` function, but in another `.c` file. That's some kind of makefile provided while `wget`-ing the zip archive given by CS50 – Mateaș Mario Jun 27 '21 at 08:30
  • 1
    Not `while(fscanf(f, "%s", word))` but `while(fscanf(f, "%s", word) == 1)` otherwise you'll trip on `EOF`. – Weather Vane Jun 27 '21 at 08:34
  • 1
    Memory that's still reachable isn't an error (Unless you intended to free it at some point because it's no longer being used). Memory that's not reachable at program exit, now... – Shawn Jun 27 '21 at 08:44
  • @WeatherVane that will return more errors than before. Everything's `:(` now, when typing the `check50` command – Mateaș Mario Jun 27 '21 at 08:49
  • @Shawn Yes, but I'm not receiving the full mark because of that "still reachable" stuff. That might be a problem in some cases :) – Mateaș Mario Jun 27 '21 at 11:23

0 Answers0