0

I have got this Valgrind error for my code. I know that I have not freed the malloc of new_node but I still could not solve this problem after trying many different ways. Can anyone help:(

// Implements a dictionary's functionality

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

// Set initial global variable of the number of words in dictionary
int word_count = 0;

// Hash table
node *table[N];

// Returns true if word is in dictionary else false
bool check(const char *word)
{
    node *cursor = table[hash(word)];
    while (cursor != NULL)
    {
        if (strcasecmp(cursor->word, word) == 0)
        {
            return true;
        }
        else
        {
            cursor = cursor->next;
        }
    }
    return false;
}

// Hashes word to a number
// reference: https://stackoverflow.com/questions/7666509/hash-function-for-string
unsigned int hash(const char *word)
{
    unsigned long hash = 5381;
    int c = 0;

    while (c == *word++)
    {
        hash = ((hash << 5) + hash) + c; /* hash * 33 + c */
    }
    return hash;
}

// Loads dictionary into memory, returning true if successful else false
bool load(const char *dictionary)
{
    // open the dictionary file
    FILE *file = fopen(dictionary, "r");
    if (!file)
    {
        return false;
    }

    // read every string from the file
    char word[LENGTH+1];

    while (fscanf (file, "%s", word)!= EOF)
    {
        // allocate memory for words
        node *new_node = malloc(sizeof(node));

        // check if memory is successfully allocated
        if (new_node == NULL)
        {
            unload();
            return false;
        }
        else
        {
            strcpy(new_node->word, word);

            word_count++;

            // insert dictionary words into hash table at that location
            int h = hash(new_node->word);

            if (table[h] == NULL)
            {
                table[h] = new_node;
                new_node->next = NULL;
            }
            else
            {
                new_node->next = table[h];
                table[h] = new_node;
            }
        }
    }
    fclose(file);
    return true;
}

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

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

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

Interesting one. The bug is well hidden. The number of blocks leaked is the same as the number of words in the dictionary. There's one clue.

Did you notice that the hash value of every word is N? That should tell you where the problem lies.

If you can't figure it out, leave a comment and I'll fill in the details.

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

5
  • I solved the problem by replacing return hash with return hash % N in the below hash function. You have no idea how much I want to thank you for this. I really spent a very long time on this problem. However, frankly speaking, I solved it but I don't quite understand why does it work. Do you mind helping me further? At first, I thought the problem was I did not free the malloc in the load function, so I tried to add free(new_node) to the end of the load function, but it was wrong. Why don't I need to free this malloc? – Marcus Chan May 24 '20 at 17:02
  • Secondly, I simply copied the hash function from the internet but don't quite understand how it works, why was the hash function gives N all the time? Am I making the best out of that hash function by adding % N? Is there another better way to correct my bug? – Marcus Chan May 24 '20 at 17:04
  • If you look very carefully at the code, you had "==" where it should have been "=" in the hash's while statement. THe code was doing a test instead of an assignment and broke the hash function. Adding the %N just made everything hash to 0. While your change made everything technically work, the hash was still broke. A great example of how an error can hide in code for years if not thoroughly tested. – Cliff B May 24 '20 at 20:43
  • Do you mean while (c == *word++) ? I think we do mean c equals *word++ instead of assignment here while it should be a condition in this while loop? – Marcus Chan May 25 '20 at 14:50
  • That is what I mean. The original author ot the code is using the while loop in a more complex way. He's actually doing an assignment that updates the value of c. – Cliff B May 25 '20 at 17:20

You must log in to answer this question.

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