after scouring the internet for multiple solutions to my Valgrind issue I cannot seem to find any that is specific to my code. I've spent hours coding this and Check50 gave me the green light except for Valgrind.
Here's the snapshot of Valgrind:
==3246==
==3246== HEAP SUMMARY:
==3246== in use at exit: 8,013,096 bytes in 143,091 blocks
==3246== total heap usage: 143,096 allocs, 5 frees, 8,023,256 bytes allocated
==3246==
==3246== 8,013,096 bytes in 143,091 blocks are still reachable in loss record 1 of 1
==3246== at 0x483B7F3: malloc (in /usr/lib/x86_64-linux-gnu/valgrind/vgpreload_memcheck-amd64-linux.so)
==3246== by 0x401B18: insert (dictionary.c:112)
==3246== by 0x401AC8: load (dictionary.c:76)
==3246== by 0x4012BE: main (speller.c:40)
==3246==
==3246== LEAK SUMMARY:
==3246== definitely lost: 0 bytes in 0 blocks
==3246== indirectly lost: 0 bytes in 0 blocks
==3246== possibly lost: 0 bytes in 0 blocks
==3246== still reachable: 8,013,096 bytes in 143,091 blocks
==3246== suppressed: 0 bytes in 0 blocks
==3246==
==3246== For lists of detected and suppressed errors, rerun with: -s
==3246== ERROR SUMMARY: 0 errors from 0 contexts (suppressed: 0 from 0)
Okay, onto my code for dictionary, I'll explain in full:
// 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 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;
// Hash table
node *table[N];
// Self-Helper function prototypes or variables
void insert(int key, const char *buffer); // abstraction for inserting into hash table
int dic_size = 0; // dictionary size counter
// Returns true if word is in dictionary, else false
bool check(const char *word)
{
// figure the key
int key = hash(word);
// use the key and traverse
node *trav = table[key];
while (true)
{
// if the traversal ptr returns null, there is no word in the dictionary
if (trav == NULL)
{
return false;
}
// checks for the word by comparing
if (strcasecmp(trav->word, word) == 0)
{
return true;
}
// if not found, travel to the next
trav = trav->next;
}
}
// Hashes word to a number
unsigned int hash(const char *word)
{
// Hash is my own, taken inspiration from the Caesar Cipher
return toupper(word[0]) - 'A' % N;
}
// Loads dictionary into memory, returning true if successful, else false
bool load(const char *dictionary)
{
// declare and open
FILE *dic = fopen(dictionary, "r");
// if file is null, return an error
if (dic == NULL)
{
printf("File does not exist.\n");
return false;
}
// initialize the key and the buffer variable
char buffer[LENGTH + 1];
int key = 0;
// get each word and insert into the hash table
while (fscanf(dic, "%s", buffer) != EOF)
{
key = hash(buffer);
insert(key, buffer);
dic_size++;
}
fclose(dic);
return true;
}
// Returns number of words in dictionary if loaded, else 0 if not yet loaded
unsigned int size(void)
{
// return the counter from load
return dic_size;
}
// Unloads dictionary from memory, returning true if successful, else false
bool unload(void)
{
node *tmp = NULL;
for (int i = 0; i < N; i++)
{
while (table[i] != NULL)
{
// while the table is not null, set tmp to the next node and clear the base ie table[i]
// then set the new value of the base to tmp
tmp = table[i]->next;
free(table[i]);
table[i] = tmp;
}
}
return true;
}
//-------SELF-MADE HELPER FUNCTIONS-------//
void insert(int key, const char *buffer)
{
// create new node
node *new = malloc(sizeof(node));
// check if no more space
if (new == NULL)
{
return;
}
// populate new node
strcpy(new->word, buffer);
new->next = NULL;
// check if the head exists, if null, set new as the head
if (table[key] == NULL)
{
table[key] = new;
}
// if exists, insert new node at the beginning
else
{
new->next = table[key];
table[key] = new;
}
}
Let's start with my helper function and variable. I decided to abstract the act of pushing into the hash table by passing in the key and the buffer into a function. I thought it the load function might look cleaner this way. Though feel free to please tell me otherwise if that is more practical.
Next is the variable, I decided to introduce a global variable that counts the size of the dictionary so I can call it to all functions. Again if this is not practical or is not good practice feel free to tell me.
Onto my logic for the functions:
Check: declaring a key by hashing the word passed, I traverse through the linked list comparing the words vs the one entered. If found return true, if the pointer returns NULL then it can reasonably deduced that the word does not exist and the end of the list is reached.
hash: Nothing special here, since the walkthroughs heavily implied to use each alphabet as buckets, I revisited the logic used from Caesar Cipher to get the location of each letter in the alphabet. I return that as the key.
load: This is where I used my insert function. For load, I opened the dictionary and declared a buffer of size length + 1 and a key variable. Then as instructed, I used fscanf to get the words until EOF. I grab the key and the buffer and pass that onto insert. Counter iterates. Repeat until EOF.
Insert: My insert mallocs a new node of size node and then populates the word variable with the buffer; then set its pointer to NULL for the meantime. It would then get inserted. If the list is empty, I will populate the list with the new node as the new head. Though I did not declare head as table[key] itself will be the location for the new node. if it's already populated, I set the pointer for the new node to the first location and then set the new node as THE location or the head.
size: Nothing special here as well. I just returned the variable.
unload: I set a temporary pointer to null and declared a for loop that will iterate through the keys. Then inside the for loop, I declared a while loop. While the head is not equal to NULL, I continue to iterate. tmp gets assigned to the next node while the current node is free'd, then the current location of temp will be assigned as the new head.
I've been at this for hours on end and I just cannot seem to find out why my memory is leaking. Though from what I can see by the total heap usage report from Valgrind, it seems like my free is not performing well as I have over 100K allocs compared to 5 frees. Seems a bit weird to me and I might be onto something, yet I cannot discern how to fix this problem.
Any assistance would be appreciated!
