i am new to stack-overflow so bare with me
I am taking CS50 and im on Pset5(speller) My code works as intended, however when I run the check50 function my program fails Valgrind, Valgrind doesn't find the leak without adding -s. I am sure it has something to do with freeing malloc on line 94 but still uncertain as to where i have gone wrong.
if you can assist me in resolving this issue i would much appreciate it.
link to CS50 Pset5: https://cs50.harvard.edu/x/2023/psets/5/speller/
See below to see code:
// 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;
// 26 buckets as there are only 26 letters in the alphabet(regardless of starting from 1 there will still only be 26 buckets needed)
const unsigned int N = 1e6 + 9;
// Hash table
node *table[N];
//Unsigned int will encode only nonnegative integers to my delcared variables
unsigned int hash_value;
unsigned int word_count;
// Returns true if word is in dictionary, else false
bool check(const char *word)
{
// take the inputted hash and output a numerical value that refers to the bucket value
hash_value = hash(word);
node *cursor = table[hash_value];
while(cursor != 0)
{
if (strcasecmp(word, cursor-> word) == 0)
{
return true;
}
else
{
cursor = cursor ->next;
}
}
return false;
}
// Hashes word to a number
unsigned int hash(const char *word)
{
//information pulled on hash function from:
//https://cp-algorithms.com/string/string-hashing.html
//map char array into an integer and compare those instead of the strings
const int p = 29;
const int m = 1e6 + 9;
//initialise variable
long long hash = 0;
//start from 1 as a starting from 0 could result in a collision after calculation(if a is 0 aaa will also be 0)
long long p_pow = 1;
//loops through the char array
for (int i = 0; i < strlen(word); i++)
{
//iterates each char as a upper case
char c = toupper(word[i]);
//calculates the hash_value by subtracting the ascii value and adding back the 1 from p_pow
hash = (hash + (c - 'A' + 1) * p_pow) % m;
//modulo keeps integer overflow to a minimum
p_pow = (p_pow * p) % m;
}
return hash;
}
// Loads dictionary into memory, returning true if successful, else false
bool load(const char *dictionary)
{
//opens file dictionary to read the contents
FILE *file = fopen(dictionary, "r");
//returns null if file couldn't be opened
if (file == NULL)
{
return false;
}
//declare variable called word;
char word[LENGTH + 1];
//While only reading strings reading through the file with fscan allocate memory for a new node
while(fscanf(file, "%s", word) == 1)
{
//allocate the memory for a node and store the address of that node inside of n
node *n = malloc(sizeof(node));
//return False if memory allocation fails, do this by checking if n is equal to NULL(this tells if this is the first in the list)
if (n == NULL)
{
return false;
}
else
{
//pointer to the destination array where the string is to be copied
strcpy(n->word, word);
//increment word count based on number of words being pulled from the dictionary
word_count++;
//after hashing the word store the number value in a variable
hash_value = hash(word);
//set the pointer of the new node to the front of the table
n->next = table[hash_value];
//
table[hash_value] = n;
}
}
//free up system resources that are using the file once finished
fclose(file);
return true;
}
// Returns number of words in dictionary if loaded, else 0 if not yet loaded
unsigned int size(void)
{
// return the size of dictionary
if(word_count > 0)
{
return word_count;
}
return 0;
}
// Unloads dictionary from memory, returning true if successful, else false
bool unload(void)
{
// to free memory used by malloc
for(int i = 0; i < N; i++)
{
node *cursor = table[i];
while (cursor != NULL)
{
node *tmp = cursor;
cursor = cursor->next;
free(tmp);
if (cursor == NULL)
{
return true;
}
}
}
return false;
}
//////////
//Load which responsible for loading the data into a hash table
//Hash take a word run a hash function returning a number that corrisponds to that word
//Size which returns how many words are in the dictionary
//Check which answers whether the word is in the dictionary or not
//Unload free the memory that you allocated
running Check50 results below
:( program is free of memory errors
valgrind tests failed; see log for more information.:
running valgrind --show-leak-kinds=all --xml=yes --xml-file=/tmp/tmpgldh6b_g -- ./speller substring/dict substring/text...
checking for output "MISSPELLED WORDS\n\nca\ncats\ncaterpill\ncaterpillars\n\nWORDS MISSPELLED: 4\nWORDS IN DICTIONARY: 2\nWORDS IN TEXT: 6\n"...
checking that program exited with status 0...
checking for valgrind errors...
56 bytes in 1 blocks are still reachable in loss record 1 of 1: (file: dictionary.c, line: 94)
if you would like more information feel free to ask.
i have tried searching multiple other forums for ways to free malloc and looking to ensure i have closed all files opened.
The implementation of unload() should be
void unload(void) {
for(int i = 0; i < N; i++) {
node *cursor = table[i];
while (cursor != NULL) {
node *tmp = cursor;
cursor = cursor->next;
free(tmp);
}
}
}