0

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;
}
3
  • Not convinced that the problem lies in any of the posted code. I'd have to see all the code to test it and see if there's not another issue, like malloc'ing nodes and then abandoning them somewhere else. – Cliff B Jan 25 '20 at 3:31
  • @CliffB I've edited my post to include the other functions, the only place I'm malloc'ing nodes is in the getNode function and they should be cleared up in the unload function – docnocturnal Jan 25 '20 at 16:27
  • I think I've narrowed down the issue to the insertNode function as check 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 why insertNode isn't working correctly though – docnocturnal Jan 25 '20 at 18:01
2

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.

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .