Unable to free up the malloc space, don't know what's going wrong in speller?

Question

    // Implements a dictionary's functionality

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

#include "dictionary.h"

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

//Choose number of buckets in hash table
const unsigned int N = 26 * 26;

// Hash table
node *table[N];

// count loaded word in dict
unsigned int count = 0 ;

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

}

// Hashes word to a number
unsigned int hash(const char *word)
{
    // Improve this hash function
    unsigned int hash_val = ((toupper(word[0]) - 'A') * 26) + (toupper(word[1]) - 'A');
    if(hash_val > N)
    {
        hash_val = hash_val % N;
    }
    return hash_val;
}

// Loads dictionary into memory, returning true if successful, else false
bool load(const char *dictionary)
{
    // Opening Dictonary file
    FILE* source = fopen(dictionary, "r");
    if (source == NULL)
    {
        return false;
    }
    // Lopping for read each word from a file
    char wrd[LENGTH + 1];
    while (fscanf(source, "%s", wrd) == 1)
    {
        int index = hash(wrd);
        node *n = malloc(sizeof(node));
        if(n == NULL)
        {
            return false;
        }
        strcpy(n->word, wrd);
        n -> next = table[index];
        table[index] = n ;
        count++;
    }
    fclose(source);
    return true;
}

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

// Unloads dictionary from memory, returning true if successful, else false
bool unload(void)
{
    for(int i=0 ;i < N; i++)
    {
        node * trav = table[i];
        node * temp = table[i];
        while(trav->next != NULL)
        {
            trav = trav->next;
            free(temp);
            temp = trav;
        }
        free(trav);
        free(temp);
    }
    return true;
}

Valgrind Report

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

MISSPELLED WORDS

==109053== Invalid free() / delete / delete[] / realloc()
==109053==    at 0x484988F: free (in /usr/libexec/valgrind/vgpreload_memcheck-amd64-linux.so)
==109053==    by 0x109BC1: unload (dictionary.c:122)
==109053==    by 0x10970F: main (speller.c:153)
==109053==  Address 0x4b5e320 is 0 bytes inside a block of size 56 free'd
==109053==    at 0x484988F: free (in /usr/libexec/valgrind/vgpreload_memcheck-amd64-linux.so)
==109053==    by 0x109BB8: unload (dictionary.c:121)
==109053==    by 0x10970F: main (speller.c:153)
==109053==  Block was alloc'd at
==109053==    at 0x4846828: malloc (in /usr/libexec/valgrind/vgpreload_memcheck-amd64-linux.so)
==109053==    by 0x109A7D: load (dictionary.c:82)
==109053==    by 0x1092CB: main (speller.c:40)
==109053== 
Could not unload dictionaries/large.
==109053== 
==109053== HEAP SUMMARY:
==109053==     in use at exit: 7,340,536 bytes in 131,081 blocks
==109053==   total heap usage: 143,096 allocs, 12,046 frees, 8,023,256 bytes allocated
==109053== 
==109053== 7,340,536 bytes in 131,081 blocks are still reachable in loss record 1 of 1
==109053==    at 0x4846828: malloc (in /usr/libexec/valgrind/vgpreload_memcheck-amd64-linux.so)
==109053==    by 0x109A7D: load (dictionary.c:82)
==109053==    by 0x1092CB: main (speller.c:40)
==109053== 
==109053== LEAK SUMMARY:
==109053==    definitely lost: 0 bytes in 0 blocks
==109053==    indirectly lost: 0 bytes in 0 blocks
==109053==      possibly lost: 0 bytes in 0 blocks
==109053==    still reachable: 7,340,536 bytes in 131,081 blocks
==109053==         suppressed: 0 bytes in 0 blocks
==109053== 
==109053== For lists of detected and suppressed errors, rerun with: -s
==109053== ERROR SUMMARY: 31 errors from 1 contexts (suppressed: 0 from 0)

Answer 1

Problems

Problem Issues with Check

1. In check you don't check that that the very first word you obtained from the table is non-null, you checked that it's trav->next is non-null, before doing a comparison of trav to wrd... you need to check that trav is non-null before using trav.

YOUR BIGGEST BUG

1. You should NOT be free-ing memory from the dictionary during check. This is causing a large amount of your memory errors. Why are you trying to free memory from your dictionary during a check of whether a word wrd is in the dictionary?? If you delete a word from the dictionary every time you check if it's in the dictionary your dictionary will eventually be empty. You aren't even adjusting the dictionary properly when you do that free either you are going to double-free at best or if you actually NULLED it, you'd leaking the rest of the list. Since you aren't NULLING it out you are getting lucky that memory isn't being reused (or you might not be getting lucky) and you will encounter undefined behavior (This is a supremely very a bad thing). You can make no conclusions about what happens at this point because the compiler can recognize this undefined behavior chain and is basically free to do whatever it wants. FIX THIS FIRST... Remove the free call from this function before making any other changes, and then evaluate again; you'll still have issues, but this is your first problem.

2. Your check logic is broken and overly redundant. Don't repeat yourself see if you can figure out a shorter way to right the 'check' code that you wrote in 15 lines or less with no duplication. I'll 'hide' a version for you here. But try to do this yourself first

your check properly written should just be:

 // NOTE to coder not to keep in your code:
 // DO NOT FREE anything in this function since you don't allocate memory
 // in it and you don't 'own' the memory in this function. You aren't finished with anything

 // Returns true if word is in dictionary, else false
 // note this assumes the word has already been case converted to all upper or lower case
 bool check(const char wrd)
 {
     bool found = false; // we haven't found it yet to start with false
     int hash_num = hash(wrd); //just as you had it
     node trav = table[hash_num]; // just as you had it

     while (trav != NULL) // NOTE how I check that trav exists before using it
     {
         if (strcasecmp(trav->word, wrd) == 0) // just as you had it
         {
             found = true; // this will be used at return
             break; // exit the loop
         }
         //implied else because break would have been taken
         trav = trav->next; // move's trav to next word we can check later if its NULL
     }
     return found; // will only be true if we found it
 }
 

Problems with Unload

You are checking trav->next instead of trav first again. You are also double freeing and doing things in an unusual order. Suggest make this simpler you have the basic idea though just too many extra free's. I'm going to make this a spoiler though; see if you can come up with the right unload first. You are correct unload is the function in which you should be doing free. Right now, it's the only function that should be free'ing from. Understand why: Your load does allocation (takes memory from the system), the unload has to free/deallocate memory (return it to the system) because unload means you are 'done' with that memory you borrowed.

 // Unloads dictionary from memory, returning true if successful, decreases count
 bool unload(void)
 {
     for (int i=0; i < N; i++)
     {
         node *trav = table[i];
         node *temp = NULL; // start NULL
         while (trav != NULL) // NOTE I ONLY CHECK TRAV
         {
             temp = trav; // point temp at non-null trav
             trav = trav->next; // move trav to next item for loop
             free(temp); // free the item trav had pointed to that was NONNULL
             // next line is OPTIONAL but probably a good idea when you are debugging
             // table[i] = trav;
             // NOTE THIS OPENS UP ANOTHER POSSIBILE PATTERN
             --count; //decrement count since the dictionary lost a word
         }
         // We've now deleted everything in this bucket we should make sure to set back to NULL
         table[i] = NULL;
     }  // End For Loop
     return count == 0; // returns true if we freed everything we created or false if we didn't free something
 } // End unload
 

Optimizations

• For your hash function, there's a problem with the modulo check, namely that you won't be greater than N, and you will be less than 0 in some cases. In either event I would consider removing the if statement and just always perform the modulo always or make it so that you never need it. The result will be the same AND it will likely be faster to always execute the same thing. You will waste more CPU time checking then you will possibly save compared to just performing the unneeded modulo here. I had written a whole big thing up then realized I misread part of your code and it rendered the whole convo moot for the moment, but I'm saving it in case it becomes relevant again. The problem right now is apostrophe as that is the only allowed non alphabetic character and it ends up being 'negative'.

• Take it one step further, convert the whole word to upper case before passing it to hash or check... otherwise you are going to keep wasting time capitalizing the word over and over again, right?