I've tried implementing a recursive function to free every node in each linked list in the hash table but it turns out it doesn't seem to free any memory as Valgrind shows there is a leak when calling getNode
==7597== 8,013,040 bytes in 143,090 blocks are definitely lost in loss record 2 of 2
==7597== at 0x4C2FB0F: malloc (in /usr/lib/valgrind/vgpreload_memcheck-amd64-linux.so)
==7597== by 0x401065: getNode (dictionary.c:36)
==7597== by 0x4010E8: insertNode (dictionary.c:51)
==7597== by 0x4011D4: load (dictionary.c:91)
==7597== by 0x400964: main (speller.c:40)
I'm passing in the head of each linked list (if it exists) into the recursive function and it should be going along the chain until it finds a null next pointer and then freeing each node.
/* Hash Table Implementation */
// Implements a dictionary's functionality
#include <stdbool.h>
#include <stdio.h>
#include <string.h>
#include <ctype.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;
// Hash function prototype
unsigned int hash(const char *word);
// Number of buckets in hash table
const unsigned int N = 250000;
// Number of words in dictionary
unsigned int words = 0;
// Hash table
node *table[N];
// Gets a node for a singly linked list
node *getNode(const char *key)
{
node *pNode = malloc(sizeof(node));
if (pNode == NULL)
{
printf("Could not allocate memory for linked list node.\n");
return pNode;
}
strcpy(pNode->word, key);
// Set next to NULL pointer
pNode->next = NULL;
return pNode;
}
void insertNode(node *head, const char *key)
{
// Create node
node *pNode = getNode(key);
// Insert node into linked list
if (head != NULL)
{
// Link pNode to current head
pNode->next = head;
}
// Now set pNode to head
head = pNode;
}
// Loads dictionary into memory, returning true if successful else false
bool load(const char *dictionary)
{
FILE *dict = fopen(dictionary, "r");
if (dict == NULL)
{
return false;
}
// Set all next pointers to NULL in hash table
for (int i = 0; i < N; i++)
{
table[i] = NULL;
}
char word[LENGTH + 1];
while(fscanf(dict, "%s", word) != EOF)
{
// Get key from hash function
unsigned int key = hash(word);
// // Add value to Hash table with head of linked list
insertNode(table[key], word);
words++;
}
fclose(dict);
return true;
}
// Returns true if word is in dictionary else false
bool check(const char *word)
{
// Convert word to lowercase to get same key from hash function
char copy[strlen(word) + 1];
strcpy(copy, word);
char *p = copy;
for ( ; *p; ++p) *p = tolower(*p);
unsigned int key = hash(copy);
// Temp traversal pointer (points to head)
node *trav = table[key];
// Traverse through linked list (linear search)
while (trav != NULL)
{
if (strcmp(copy, trav->word) == 0)
{
return true;
}
trav = trav->next;
}
return false;
}
// Returns number of words in dictionary if loaded else 0 if not yet loaded
unsigned int size(void)
{
return words;
}
getNode
function and they should be cleared up in the unload functioninsertNode
function ascheck
is always returning false since the head is always null meaning the nodes aren't being inserted into the hash table correctly, this makes sense since the memory leak would be occurring as the nodes are being created and then lost. Not sure whyinsertNode
isn't working correctly though