0

I seem to have the load/size functions on point. I'm trying to implement unload before I move on to check, but my valgrind keeps telling me I have a ton of memory left (~8,011,460 bytes) and points to my "new node" malloc call in my load function. Any ideas?

#include <ctype.h>
#include <stdbool.h>
#include <stdio.h>
#include <stdlib.h>
#include <string.h>

#include "dictionary.h"

// Represents number of buckets in a hash table
#define N 26

// Represents a node in a hash table
typedef struct node
{
    char word[LENGTH + 1];
    struct node *next;
}
node;

// Represents a hash table
node *hashtable[N];

// My code, declare reusable struct pointers & counter
int wordCount = 0;

// Hashes word to a number between 0 and 25, inclusive, based on its first letter
unsigned int hash(const char *word)
{
    return tolower(word[0]) - 'a';
}

// Loads dictionary into memory, returning true if successful else false
bool load(const char *dictionary)
{
    // Initialize hash table
    for (int i = 0; i < N; i++)
    {
        hashtable[i] = NULL;
    }

    // Open dictionary
    FILE *file = fopen(dictionary, "r");
    if (file == NULL)
    {
        unload();
        return false;
    }

    // Buffer for a word
    char word[LENGTH + 1];

    // Insert words into hash table
    while (fscanf(file, "%s", word) != EOF)
    {
        // TODO

        // malloc space for newWord(s)
        node *newWord = (struct node *) malloc(sizeof(struct node));
            if (newWord == NULL) {
                unload();
                return false;
            }
        strcpy(newWord->word, word);
        newWord->next = NULL;

        // create temp to link the list
        struct node *temp = newWord;

        // word counter for size function
        ++wordCount;

        // hash the word first
        unsigned int hashedWord = hash(word);

        // if bucket is empty, start a new list
        if (hashtable[hashedWord] == NULL) {

            hashtable[hashedWord] = newWord;

        // otherwise, append the last node to the new node
        } else {

            temp->next = newWord;
            temp = temp->next;
        }

    }

    // Close dictionary
    fclose(file);

    // Indicate success
    return true;
}

// Returns number of words in dictionary if loaded else 0 if not yet loaded
unsigned int size(void)
{
    if (wordCount > 0) {
        return wordCount;
    } else {
        return 0;
    }
}

// Returns true if word is in dictionary else false
bool check(const char *word)
{
    // TODO
    return false;
}

// Unloads dictionary from memory, returning true if successful else false
bool unload(void)
{
     for (int i = 0; i < N; i++) { // iterate over the hashtable

        printf("Int loop for freeing mem\n"); // testing

        struct node * cursor = hashtable[i]; // create a cursor to scan the first linked list

        while(cursor != NULL) { // while the cursor doesn't equal "NULL" or rather, the end of the list, repeat the following:

            struct node * tmp = cursor; // we need a temp var to store the value of the cursor in

            cursor = cursor->next; // move the cursor over to next position in list

            free(tmp); // free the memory at the last location in the list

            printf("word freed\n");
        }
    }

    return true;
}
2
  • I don't have an answer, only a hint. Thie struct node * cursor = hashtable[i]; looks sketchy (and this struct node * tmp = cursor) in the unload function. You are not creating a new struct, you are simply declaring new variables as nodes. I believe the use of struct is incorrect here. Mar 13 '19 at 19:05
  • psst, looking in the wrong place, Dino? ;-) Everyone: memory leaks happen as much in load as in unload, if not more. I'd say it's about 60/40 in favor of load, maybe more! But that's just my opinion, I could be wrong. ;-)
    – Cliff B
    Mar 13 '19 at 23:52
0

If you had gone on to write check, you would have discovered a serious issue with load. Also, valgrind will point to where the lost memory is created. This usually not where a problem may lie. It's just a pointer at where to start looking.

If the node being created is the first one with a given hash, it will be added to the hashtable array. BUT, for words that have the same hash as a prior word, temp = newword, so newword->next is constructively set to newword. In other words, the pointer in next points back at itself. Remember, newword and temp are both pointers and point to the same address. Also, whatever is stored in temp is lost when the loop ends and temp is recreated when the loop runs again.

There is no code that actually adds any nodes to the linked lists pointed to by the hashtable array. All of those nodes that were created after the first nodes with a given hash value are lost. That's the memory leak.

One very important piece of advice. It's almost always best to get all of the code working before checking for memory leaks. Many leaks will be fixed as a side effect of fixing the coding errors. (Checking for mem leaks can give clues to errors, but the focus should be on getting the code running without errors before focusing on memory leaks just for the sake of memory leaks.)

If this answers your question, please click on the check mark to accept. Let's keep up on forum maintenance. ;-)

You must log in to answer this question.

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