PSET5: memory leak in check function

Question

bool check(const char *word)
{   
    unsigned int hash_index = hash(word);
    node *trav = table[hash_index];

    while (trav != NULL)
    {   
        int len = strlen(trav->word);
        char *dict_word = malloc(sizeof(char) * len); // valgrind says to check here
        strcpy(dict_word, trav->word);
        if (strcasecmp(word, dict_word) == 0) // strcasecmp does not work with character arrays
        {   
            return true;
        }
        trav = trav->next;
        free(dict_word);
    }
    return false;
}

running help50 on valgrind shows

==3164== 72,896 bytes in 16,801 blocks are definitely lost in loss record 1 of 1
==3164==    at 0x4C2FB0F: malloc (in /usr/lib/valgrind/vgpreload_memcheck-amd64-linux.so)
==3164==    by 0x4010F1: check (dictionary.c:45)
==3164==    by 0x400CD9: main (speller.c:112)

Looks like your program leaked 72,896 bytes of memory. Did you forget to free memory that you allocated via malloc? Take a closer look at line 45 of dictionary.c.

I did put free(dict_word) every iteration that I malloc'ed it. Why does it say that it didn't free the memory

here is the rest of the code if needed

// Implements a dictionary's functionality

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


#include "dictionary.h"

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

unsigned int word_count = 0;

// Number of buckets in hash table
const unsigned int N = 65536;

// Hash table
node *table[N];

// Returns true if word is in dictionary else false
/* 


BUG IS WITH STRCASECMP TAKING CHARACTER ARRAYS AND NOT CONST CHAR*


*/
bool check(const char *word)
{   
    unsigned int hash_index = hash(word);
    node *trav = table[hash_index];

    while (trav != NULL)
    {   
        int len = strlen(trav->word);
        char *dict_word = malloc(sizeof(char) * len);
        strcpy(dict_word, trav->word);
        if (strcasecmp(word, dict_word) == 0) // strcasecmp does not work with character arrays
        {   
            return true;
        }
        trav = trav->next;
        free(dict_word);
    }
    return false;
}

// Hashes word to a number // hash function is fine
unsigned int hash(const char *word)
{
    unsigned long hash = 5381;
    int c = *word;
    c = tolower(c);

    while (*word != 0)
    {
        hash = ((hash << 5) + hash) + c;
        c = *word++;
        c = tolower(c);
    }
    return hash % N;
    // hash taken from https://www.reddit.com/r/cs50/comments/eo4zro/good_hash_function_for_speller/
}
// Loads dictionary into memory, returning true if successful else false
bool load(const char *dictionary)
{
    // initialze all values of the table to NULL
    for (int i = 0; i < N; i++)
    {
        table[i] = NULL;
    }
    // define word buffer;
    char word[LENGTH + 1];

    // Open dictionary file
    FILE *dict = fopen(dictionary, "r");
    if (dict == NULL)
    {
        printf("Could not open dictionary file\n");
        fclose(dict);
        return false;
    }

    unsigned int hash_index;

    while (fscanf(dict, "%s", word)  != EOF)
    {
        // creates a node for the word and inserts word into node
        node *n = malloc(sizeof(node));
        if (n == NULL)
        {   
            fclose(dict);
            unload();
            return false;
        }
        else
        // inserts node into linked list in that location
        strcpy(n->word, word);
        // every word in dictionary is lowercase
        hash_index = hash(n->word);
        // since table is initialized to NULL, next will point to NULL if there is nothing
        // otherwse, next will point to the old head of the linked list
        n->next = table[hash_index];
        table[hash_index] = n;
        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;
}

// Unloads dictionary from memory, returning true if successful else false
bool unload(void)
{
    // instead of directly working with the table, created new pointers to the same memory to clear these stuff
    for (int i = 0; i < N; i++)
    {
        node *trav = table[i];
        while (trav != NULL)
        {
            node *tmp = trav;
            trav = trav->next;
            free(tmp);
        }
        free(trav);
    }
    return true;

}

Answer 1

Simple. Every time a word is found, the code returns true BEFORE it executes the free call.

You could fix this by adding another free call before the return statement, but why use an intermediate pointer and a malloc in the first place - a second one at that? It's a one-time throw away use. It makes more sense and less overhead to just use trav->word in the strcasecmp call. Why create an intermediate pointer to copy data from another intermediate pointer????

My recommendation is to first add the extra free call and test it just so you see that it works, then get rid of dict_word and the related code completely.

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