1

I am very close to solving this, my code is returning 0 errors from Valgrind when I run that on its own, but its not passing the memory errors parameter in check50, so I'm very confused. Any help would be much appreciated!

Here is my code:

// Implements a dictionary's functionality

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

#include "dictionary.h"

// Number of buckets in hash table
#define N 26

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

// Hash table
node *table[N];

//Set word count to 0
int wordcount = 0;

// Hashes word to a number (TAKEN FROM GITHUB)
unsigned int hash(const char *word)
{
    // Hash function taken from github
    return tolower(word[0]) - 'a';

}

// Returns true if word is in dictionary, else false
bool check(const char *word)
{
    // TODO

    //Hash word using hash function
    int n = hash(word);

    //Create a cursor value to traverse linked list at hash value
    //Set to first node of hash value
    node *cursor = table[n];

    //Compare word to words in linked list at hash value
    while (cursor != NULL)
    {
        //Compare word to words in linked list at hash value
        if (strcasecmp(cursor->word, word) == 0)
        {
            return true;
        }
        else
        {
            //Assign cursor value to the next node
            cursor = cursor->next;
        }
    }

    return false;
}


// Loads dictionary into memory, returning true if successful, else false
bool load(const char *dictionary)
{
    // Initialize hash table
    for (int i = 0; i < N; i++)
    {
        table[i] = NULL;
    }

    //Open dictionary file
    FILE *file = fopen(dictionary, "r");
    //Check if file exists
    if (file == NULL)
    {
        unload();
        return false;
    }

    //Buffer for a word
    char word[LENGTH + 1];

    //Read strings from file
    while (fscanf(file, "%s", word) != EOF)
    {

        //Create a new node for the word
        node *n = malloc(sizeof(node));

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

        //Copy word into node
        strcpy(n->word, word);
        n->next = NULL;

        int i = hash(word);

        //Check if hashtable at hash is empty
        if (table[i] == NULL)
        {
            table[i] = n;
        }
        else
        {
            n->next = table[i];
            table[i] = n;
        }

        wordcount++;
    }

    //Close dictionary file
    fclose(file);

    //Return true if dictionary was loaded
    return true;
}

// Returns number of words in dictionary if loaded, else 0 if not yet loaded
unsigned int size(void)
{
    //If dictionary is loaded
    if (wordcount > 0)
    {
        return wordcount;
    }
    //Else
    return 0;
}

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

    for (int i = 0; i < (N + 1); i++)
    {
        //Create cursor variable to cycle through linked list
        node *cursor = table[i];

        while (cursor != NULL)
        {
            //Move temp to where cursor is
            node *tmp = cursor;
            //Point cursor to next node
            cursor = cursor->next;
            //Free node using temp value
            free(tmp);

        }
        return true;

    }

    return false;
}

1

The bug is in your unload function. You return after cleaning up just 1 list. But you have 26 of them to get through. The outer loop is also out of bounds. You iterate up to N + 1 for some reason.

// Unloads dictionary from memory, returning true if successful, else false
bool unload(void)
{
    for (int i = 0; i < (N + 1); i++) // Out of bounds. Should just be N.
    {
        //Create cursor variable to cycle through linked list
        node *cursor = table[i];

        while (cursor != NULL)
        {
            //Move temp to where cursor is
            node *tmp = cursor;
            //Point cursor to next node
            cursor = cursor->next;
            //Free node using temp value
            free(tmp);
        }
        return true; // Abort after just 1 list?! Delete this line!
    }
    return false; // This is where you return true. There is no reason to ever return false in this function.
}
1
  • Agh - thank you so much! Had been staring at it too long to really think these through :) May 3 at 0:09
0

I'm sorry, but this code is not passing valgrind.

~/go/test/pset5/ $ valgrind ./speller small
==223== Memcheck, a memory error detector
==223== Copyright (C) 2002-2017, and GNU GPL'd, by Julian Seward et al.
==223== Using Valgrind-3.15.0 and LibVEX; rerun with -h for copyright info
==223== Command: ./speller small
==223== 

MISSPELLED WORDS


WORDS MISSPELLED:     0
WORDS IN DICTIONARY:  143091
WORDS IN TEXT:        7
TIME IN load:         1.26
TIME IN check:        0.05
TIME IN size:         0.00
TIME IN unload:       0.01
TIME IN TOTAL:        1.32

==223== 
==223== HEAP SUMMARY:
==223==     in use at exit: 7,501,928 bytes in 133,963 blocks
==223==   total heap usage: 143,096 allocs, 9,133 frees, 8,023,256 bytes allocated
==223== 
==223== 7,501,928 bytes in 133,963 blocks are still reachable in loss record 1 of 1
==223==    at 0x483B7F3: malloc (in /usr/lib/x86_64-linux-gnu/valgrind/vgpreload_memcheck-amd64-linux.so)
==223==    by 0x401ABB: load (dictionary.c:94)
==223==    by 0x4012BE: main (speller.c:40)
==223== 
==223== LEAK SUMMARY:
==223==    definitely lost: 0 bytes in 0 blocks
==223==    indirectly lost: 0 bytes in 0 blocks
==223==      possibly lost: 0 bytes in 0 blocks
==223==    still reachable: 7,501,928 bytes in 133,963 blocks
==223==         suppressed: 0 bytes in 0 blocks
==223== 
==223== For lists of detected and suppressed errors, rerun with: -s
==223== ERROR SUMMARY: 0 errors from 0 contexts (suppressed: 0 from 0)
~/go/test/pset5/ $ 

Think about it. There's a massive amount of data that's still reachable - 7,501,928 bytes!!!

That means that it hasn't been freed. Given the amount of data, it should be obvious that unload is failing somehow. HINT: Maybe it's terminating early?

If you can't figure it out, leave a comment and I'll help you find the error. ;-)

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

2
  • May I respectfully remind all that this is a teaching/learning forum? I give big hints and put people on course to figure out problems on their own, with guidance. Simply posting a solution, (especially without explanation, as sometimes done) doesn't help the questioner learn. It also borders on or crosses the line against forum rules about posting solutions.I posted this answer like this to give Seamus the chance to track the problem down. It's possible he didn't know it existed. @Fuelled_By_Coffee,not aimed at you. You explained the problem without actually posting solution code.
    – Cliff B
    May 1 at 0:07
  • 1
    Thank you for this! My tired brain was just seeing 0 errors - not reading the entirety of the results :) May 3 at 0:09

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .