0

I have trying to decode the information gathered through valgrind with no success. I followed the hints given by valgrind trying too free the malloc'ed node *checker but to no avail. I've searched related issues online, and found something related with using calloc instead of malloc, but using it changed nothing. Here's my code, the result of help50 valgrind and of check50 .

// Implements a dictionary's functionality

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

// Represents number of buckets in a hash table
#define N 26

//define loading status
bool loading_complete = false;
// declare words to count the words in the dictionary
int dic_size = 0;

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

// Represents a hash table
node *hashtable[N];

// Hashes word to a number between 0 and 25, inclusive, based on its first letter
unsigned int hash(const char *word)
{
    return tolower(word[0]) - 'a';
}

// 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++)
    {
        hashtable[i] = NULL;
    }

    // Open dictionary
    FILE *file = fopen(dictionary, "r");
    if (file == NULL)
    {
        unload();
        fprintf(stderr, "Cound not open %s.\n", dictionary);
        return false;
    }

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

    // Insert words into hash table
    while (fscanf(file, "%s", word) != EOF)
    {
        //create node and check malloc; copy word value
        node *new_node = malloc(sizeof(node));

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

        strncpy(new_node->word, word, sizeof(word));

        //get index of the hash function
        int index = hash(word);

        // if the corresponding index in hashtable is empty, assign it to the temp node
        if (hashtable[index] == NULL)
        {
            hashtable[index] = new_node;
        }

        // else append temp to the start of the linked list
        else
        {
            new_node->next = hashtable[index];
            hashtable[index] = new_node;
        }

        dic_size++;
    }

    // Close dictionary
    fclose(file);

    // Indicate success
    loading_complete = true;
    return true;
}

// Returns number of words in dictionary if loaded else 0 if not yet loaded
unsigned int size(void)
{
    if (loading_complete == true)
    {
        return dic_size;
    }

    else
    {
        return 0;
    }
}

// Returns true if word is in dictionary else false
bool check(const char *word)
{
    //alocate memory for checker
    node *checker = malloc(sizeof(node));

    //determine in which bucket is the word
    int index = hash(word);

    checker = hashtable[index];

    while (checker != NULL)
    {
        //compare use case insensitive function
        if (strcasecmp(checker->word,word) == 0)
        {
            free(checker);
            return true;
        }
        checker = checker->next;
    }
    free(checker);
    return false;
    // //malloc cursor
    // node *cursor = malloc(sizeof(node));
    // //hash word being checked and initialize cursor to respective linked list
    // int check_index = hash(word);
    // cursor = hashtable[check_index];

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

    //     else
    //     {
    //         cursor = cursor->next;
    //     }
    // }
    // free(cursor);
    // return false;
}

// Unloads dictionary from memory, returning true if successful else false
bool unload(void)
{
    for (int i = N; i == 0; i--)
    {
        //initialize for the first element of the linked list, for each one of the hashtable
        node *cursor = hashtable[i];
        while (cursor != NULL)
        {
            node *temp = cursor;
            cursor = cursor->next;
            free(temp);
        }
    }
    return true;
}

check50valgrind1 valgrind2

3
  • The code posted here does not give the same check50 results as posted (it fails 2 or 3 tests). The code posted here gives a runtime error in unload. The i loop is out of bounds; it loops from 27 to 1. Please make the appropriate corrections/updates to the code posted here. Dec 16 '19 at 15:24
  • I restarted the IDE, ran "make speller" again and everything repeated the previous results imgur.com/tGqlTLo
    – DGC
    Dec 16 '19 at 15:48
  • The code pasted into this question does not pass "handles most basic words properly", "spell-checking is case insensitive" or "program is free of memory errors" tests. Therefore it is not the same code that is running on your IDE. Dec 16 '19 at 17:52
1

Your code

    node *checker = malloc(sizeof(node));
    /* ... */
    checker = hashtable[index];

means you allocate a new node, and then you throw away the only reference to that node, leaving this node as "definitely lost". There is no need to malloc in check. You copy pointers (memory addresses), not nodes. Same goes for the free, remove it, you might accidentally free nodes still in use.

And in unload, remember that array index starts at 0. hashtable[N] is outside of the array. But since your condition is i == 0, that loop does not run even once.

5
  • When I stop malloc'ing checker it starts producing errors of "Invalid read size" when strcasecmp is executed.
    – DGC
    Dec 16 '19 at 17:42
  • How should I initialize node *checker without using malloc? When I try node *checker = malloc(sizeof(node)); I get "invalid read size" when strcasecmp is executed
    – DGC
    Dec 16 '19 at 18:17
  • Try node *checker = hashtable[index];
    – Blauelf
    Dec 16 '19 at 18:46
  • That's what I tried as soon as you told me to. I can't understand why but the program crashes.
    – DGC
    Dec 16 '19 at 19:03
  • If you correctly removed the malloc and free from check (fixing the memory leak you were asking about), you might have run into the mistake you made in load, I would expect a "condition depends on uninitialised value". Re-read the example on how to use strncpy man.cs50.io/3/strncpy#notes (as you use it, you have no protection against buffer overflow, you don't have that protection in fscanf either, and also you are not copying the null terminator)
    – Blauelf
    Dec 16 '19 at 21:16
0

Changing my code by:

  1. implementing the suggestions made by @Blauelf
  2. correcting the unload() loop

solved my issues.

    // Implements a dictionary's functionality

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

// Represents number of buckets in a hash table
#define N 26

//define loading status
bool loading_complete = false;
// declare words to count the words in the dictionary
int dic_size = 0;

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

// Represents a hash table
node *hashtable[N];

// Hashes word to a number between 0 and 25, inclusive, based on its first letter
unsigned int hash(const char *word)
{
    return tolower(word[0]) - 'a';
}

// 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++)
    {
        hashtable[i] = NULL;
    }

    // Open dictionary
    FILE *file = fopen(dictionary, "r");
    if (file == NULL)
    {
        unload();
        fprintf(stderr, "Cound not open %s.\n", dictionary);
        return false;
    }

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

    // Insert words into hash table
    while (fscanf(file, "%s", word) != EOF)
    {
        //create node and check malloc; copy word value
        node *new_node = malloc(sizeof(node));

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

        strcpy(new_node->word, word);

        //get index of the hash function
        int index = hash(word);

        //execute linking
        new_node->next = hashtable[index];
        hashtable[index] = new_node;

        dic_size++;
    }

    // Close dictionary
    fclose(file);

    // Indicate success
    loading_complete = true;
    return true;
}

// Returns number of words in dictionary if loaded else 0 if not yet loaded
unsigned int size(void)
{
    if (loading_complete == true)
    {
        return dic_size;
    }

    else
    {
        return 0;
    }
}

// Returns true if word is in dictionary else false
bool check(const char *word)
{
    //determine in which bucket is the word
    int index = hash(word);

    //init checker
    node *checker = hashtable[index];

    while (checker != NULL)
    {
        //compare use case insensitive function
        if (strcasecmp(checker->word,word) == 0)
        {
            return true;
        }
        checker = checker->next;
    }
    return false;
}

// Unloads dictionary from memory, returning true if successful else false
bool unload(void)
{
    for (int i = 0; i < N; i++)
    {
        //initialize for the first element of the linked list, for each one of the hashtable
        node *cursor = hashtable[i];
        while (cursor != NULL)
        {
            node *temp = cursor;
            cursor = cursor->next;
            free(temp);
        }
    }
    return true;
}

You must log in to answer this question.

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