Pset 5 Speller recursive unload

Question

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;
}

Answer 1

insertnode isn't working correctly because of the way functions are called. When a function is called, any parameters are passed by copy. That means that a copy of the data is created in the function that can be modified, while the original parameter in the calling code will remain unchanged.

In this case, that means that the address stored in table[key] and not the var table[key] is passed to insertnode(). So, storing the address of the new node in head does not actually store anything in table[key]. The result is that nothing is ever added to the dictionary and all those nodes are lost.

This is also a good demonstration that all bugs in code should be resolved before trying to resolve memory leaks. Many times, memory leaks are fixed when bugs are fixed. In this case, the problem that the number of misspelled words is incorrect would have led to finding this and should be resolved first.