0

There are 56 bytes that are not being freed.

==600== 56 bytes in 1 blocks are definitely lost in loss record 1 of 2

==600== at 0x4C2FB0F: malloc (in /usr/lib/valgrind/vgpreload_memcheck-amd64-linux.so)

==600== by 0x40116C: load (dictionary.c:65)

==600== by 0x400964: main (speller.c:40)

It says its from line 65 that is where I allocate space with malloc

// Loads dictionary into memory, returning true if successful else false
bool load(const char *dictionary)
{
// Initialize hash table
for (int i = 0; i < 25; 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];

// Create head of linked list
node *head = malloc(sizeof(node));

// Insert words into hash table
while (fscanf(file, "%s", word) != EOF)
{
    //change pointer of the new node to the already existing beginning of link list node
    head->next = hashtable[hash(word)];

    //then change the hashtable's first pointer to the new_node
    hashtable[hash(word)] = head;

    // Allocate space for node
    node *new_node = malloc(sizeof(node));

    // Check for space
    if (new_node == NULL)
    {
        unload();
        return false;
    }

    else
    {
        // Copy node
        strcpy(new_node->word, word);

        // Hash word and insert into hashtable
        int hash_key = hash(new_node->word);
        head = hashtable[hash_key];

        // Insert node into linked list
        new_node->next = head;
        head = new_node;
    }
}

// Close dictionary
fclose(file);

// Indicate success
return true;
}

and my unload code is

// Unloads dictionary from memory, returning true if successful else false
bool unload(void)
{
for (int x = 0; x < 25; x++)
{
    // Create new cursor
    node *cursor = hashtable[0];

    while (cursor != NULL)
    {
        node *temp = cursor;
        free(temp);
        cursor = cursor->next;
    }
return false;
}

How can I find where the memory leak is coming from?

1

There are problems in load and unload.

load

The last word of any alpha-index is never stored in the hashtable, therefore 1) will never get freed and 2) will ultimately give incorrect result.

Let's use a one-word dictionary "at" and (crude) code crawl to see what is allocated and where it is (or isn't!) stored in hashtable:

  1. node *head = malloc(sizeof(node));: head is allocated at address 0x1
  2. head->next = hashtable[hash(word)];: head->next is set to NULL
  3. hashtable[hash(word)] = head;: hashtable[0] is set to 0x1
  4. node *new_node = malloc(sizeof(node));: new_node is allocated at address 0x2
  5. head = hashtable[hash_key];: head is set to 0x1 (from line 3)
  6. new_node->next = head;: new_node->next is set to 0x1
  7. head = new_node;: head is set to 0x2

But remember, the dictionary contains one word, therefore address of new_node is never stored in the hash table.

Now the easy fix to get rid of the 56 lost bytes (which is, not coincidentally, sizeof(node)) is to add a free(head) before exiting load. But that is not going to solve the problem of that last word not being added to the dictionary.

Remembering that hashtable[N] is the head of the list, think about how to manage the pointers between hashtable[index] and new_node without creating the head node. Hopefully the code crawl highlights some of the redundancies.

unload

  1. There is no return true;, so speller is never going to give results report.
  2. The for loop does not process the hashtable[25]. If you want to see the difference that makes, use a dictionary/text file with 2 or more z words. You will see that the 56 bytes lost will be multiplied by the number of (z) words. (assuming no other changes). You'll want to make a similar change in the initialize loop.
  3. This node *cursor = hashtable[0]; should be node *cursor = hashtable[x];, otherwise it will only free the first index of the list.

Finally, once the memory LEAKs are fixed, be sure to investigate the ERROR SUMMARY that valgrind reports with valgrind -v ./speller .....

[I realize now that I gave a wrong information in this answer. Truly sorry about that. That would apply to trie, not hashtable. I will correct it after I check my work]

4
  • changing 25 to 26 or N does not change the outcome. also this is something I don't understand node *cursor = hashtable[0]; works the same as node *cursor = hashtable[x];
    – Chris
    Dec 19 '19 at 13:09
  • Research so far indicates that head as created in load is not being freed. I am still investigating. I don't understand the also in your comment. Where do they work the same? Dec 19 '19 at 13:17
  • I get the same message about the 56 unfreed bytes
    – Chris
    Dec 19 '19 at 13:45
  • answer has been updated Dec 19 '19 at 17:57

You must log in to answer this question.

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