0

I get all test results correct except the Valgrind error as follows, does anyone know why is it so and share some insights please? thanks!

running valgrind --show-leak-kinds=all --xml=yes --xml-file=/tmp/tmpx_or2m8s -- ./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...
112 bytes in 2 blocks are still reachable in loss record 1 of 1: (file: dictionary.c, line: 79)

I had a look into the malloc and tried to free in the load function but couldn't figure it out. If I free(n) in the load function, that will actually free the word list stored from the dictionary, hence the test results for checking the words will fail instead.

Here's my full code:

// Implements a dictionary's functionality

#include <stdbool.h>
#include <ctype.h>
#include <stdio.h>
#include <stdlib.h>
#include <strings.h>
#include <string.h>
#include <cs50.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;

int word_count = 0;

// Hash table
node *table[N];

// Returns true if word is in dictionary, else false
bool check(const char *word)
{
    // get the head of the node of the linked list for the word based on its hash value
    node *ptr = table[hash(word)];

    //while it hasn't reach end of the linked list which has null value
    while (ptr != NULL)
    {
        //check if the word matches any of the word in the dictionary stored in the table
        if (strcasecmp(word, ptr->word) == 0)
        {
            return true;
        }
        //progress to next node
        ptr = ptr->next;
    }
    unload();
    return false;
}

// Hashes word to a number
unsigned int hash(const char *word)
{
    // return a number specifying the bucket the word should be stored in
    unsigned long hash = 5381;
    int c;
    while ((c = tolower(*word++)))
    {
        hash = ((hash << 5) + hash) + c; /* hash * 33 + c */
    }
    return hash % N;
    return 0;
}

// Loads dictionary into memory, returning true if successful, else false
bool load(const char *dictionary)
{
    // open a dictionary file
    FILE *dict = fopen(dictionary, "r");
    if (dict == NULL)
    {
        printf("Could not open %s.\n", dictionary);
        return false;
    }

    char word[LENGTH + 1];
    // read strings from file one at a time until reach EOF
    while(fscanf(dict, "%s", word) != EOF)
    {
        //read string and store in the var word
        // malloc a new node for each word if malloc doesn't return NULL.
        node *n = malloc(sizeof(node));

        if (n == NULL)
        {
            free(n);
            fclose(dict);
            return false;
        }
        else
        {
            //get hash number of the bucket for the word from hash function
            int hash_number = hash(word);

            //copy the string value of the word into the node's word value
            strcpy(n->word, word);

            //set the pointer of the new node to the returned hash number
            n->next = table[hash_number];

            //set the head of the table pointing to the new node
            table[hash_number] = n;

            //increase number of word count
            word_count++;
        }
    }

    fclose(dict);
    return true;
}

// Returns number of words in dictionary if loaded, else 0 if not yet loaded
unsigned int size(void)
{
    // return word_count which has been incrementing in the load function
    return word_count;
}

// Unloads dictionary from memory, returning true if successful, else false
bool unload(void)
{
    //iterate through each of the bucket
    for (int i = 0; i < N; i++)
    {
        //cursor at the initial table location
        node *cursor = table[i];

        //while yet to reach end of the linked list (which has value of null)
        while (cursor != NULL)
        {
            // Create a temporary cursor to store address of the current node
            node *tmp = cursor;
            // Move the actual cursor to next node
            cursor = cursor->next;
            // Free up the node that the temporary cursor is pointing to
            free(tmp);
        }
        free(cursor);
        return true;
    }
    return false;
}

Running help50 valgrind ./speller texts/cat.txt returns

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

MISSPELLED WORDS


WORDS MISSPELLED:     0
WORDS IN DICTIONARY:  143091
WORDS IN TEXT:        6
TIME IN load:         1.37
TIME IN check:        0.02
TIME IN size:         0.00
TIME IN unload:       0.01
TIME IN TOTAL:        1.40

==2214== 
==2214== HEAP SUMMARY:
==2214==     in use at exit: 7,702,464 bytes in 137,544 blocks
==2214==   total heap usage: 143,096 allocs, 5,552 frees, 8,023,256 bytes allocated
==2214== 
==2214== 7,702,464 bytes in 137,544 blocks are still reachable in loss record 1 of 1
==2214==    at 0x483B7F3: malloc (in /usr/lib/x86_64-linux-gnu/valgrind/vgpreload_memcheck-amd64-linux.so)
==2214==    by 0x401B7C: load (dictionary.c:80)
==2214==    by 0x4012BE: main (speller.c:40)
==2214== 
==2214== LEAK SUMMARY:
==2214==    definitely lost: 0 bytes in 0 blocks
==2214==    indirectly lost: 0 bytes in 0 blocks
==2214==      possibly lost: 0 bytes in 0 blocks
==2214==    still reachable: 7,702,464 bytes in 137,544 blocks
==2214==         suppressed: 0 bytes in 0 blocks
==2214== 
==2214== For lists of detected and suppressed errors, rerun with: -s
==2214== ERROR SUMMARY: 0 errors from 0 contexts (suppressed: 0 from 0)

Asking for help...

Sorry, help50 does not yet know how to help with this!
2
  • Why use upload() in check()?I don't know its reason clearly. I think it should not use it here. – Kai Xu Feb 19 at 20:06
  • the unload() is to free the memory after performing the checking in the dictionary. – unacorn Feb 21 at 8:17
0

Got some help from [reddit][1]

It's due to a small mistake I did in the for loop in my unload function. I accidentally included return true in the for loop when I was meant to return true after the cursor reached null which means at the end of the linked list.

the final unload function becomes:

bool unload(void)
{
    //iterate through each of the bucket
    for (int i = 0; i < N; i++)
    {
        //cursor at the initial table location
        node *cursor = table[i];

        //while yet to reach end of the linked list (which has value of null)
        while (cursor != NULL)
        {
            // Create a temporary cursor to store address of the current node
            node *tmp = cursor;
            // Move the actual cursor to next node
            cursor = cursor->next;
            // Free up the node that the temporary cursor is pointing to
            free(tmp);
        }
        if (i == N - 1 && cursor == NULL)
        {
            return true;
        }
    }
    return false;
}
0

enter image description here

I use your code, but the result is like the picture. I think check is used for each word, so maybe it does not need to free dictionary after checking each word.I tried to run the code and find another problem node *ptr = table[hash(word)];in check(), but if word is uppercase, the result of check() is false because hash() can not deal with uppercase. Maybe before this statement, we need to make them lowercase.

You must log in to answer this question.

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