0

My code passed the check50. But valgrind reported still reachable leaks. Some posts I'v read suggests that it is OK to have still reachable leaks. Is it really so? If not, how can I fix it? What does "still reachable" mean?

==2280== HEAP SUMMARY:
==2280==     in use at exit: 82,220,320 bytes in 367,055 blocks
==2280==   total heap usage: 367,083 allocs, 28 frees, 82,227,280 bytes allocated
==2280== 
==2280== LEAK SUMMARY:
==2280==    definitely lost: 0 bytes in 0 blocks
==2280==    indirectly lost: 0 bytes in 0 blocks
==2280==      possibly lost: 0 bytes in 0 blocks
==2280==    still reachable: 82,220,320 bytes in 367,055 blocks
==2280==         suppressed: 0 bytes in 0 blocks
==2280== Reachable blocks (those to which a pointer was found) are not shown.
==2280== To see them, rerun with: --leak-check=full --show-leak-kinds=all
==2280== 
==2280== For counts of detected and suppressed errors, rerun with: -v
==2280== ERROR SUMMARY: 0 errors from 0 contexts (suppressed: 0 from 0)

Here is my code:

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


#include "dictionary.h"

// Define a struct node to store words
typedef struct node
{
    bool is_word;
    struct node* children[27];
}
node;

// Set the root of tries
node root = {false, {NULL}};


/**
 * Returns true if word is in dictionary else false.
 */

bool check(const char* word)
{
    node* current_node = &root;
    for (int i = 0, k = LENGTH + 1; i < k; i++)
    {   
        // Check if the letter is in the right order.
        if (word[i] != '\0')
        {
            // Calculate the index of the pointer of the corresponding trie. 
            int index = (isalpha(word[i])) ? (tolower(word[i]) - 'a'): 26; 
            // If the letter is in the loaded dictionary
            if (current_node -> children[index] != NULL)
            {
                current_node = current_node -> children[index];
            }
            // If the letter is not in the loaded dictionary
            else
            {
                return false;
            }            
        }
        // If reach the end of the word, check if it is indeed a word.
        else
        {
            if (current_node -> is_word == true)
            {
                return true;
            }
            else
            {
                return false;
            }
        }
    }
    return false;
}

/**
 * Loads dictionary into memory.  Returns true if successful else false.
 */

int word_counter = 0;
bool load(const char* dictionary)
{
    // Read words from dictionary and store them in the tries
        // Read the first letter
        // Store it in the relevant children array (node -> children[x])
        // Read the next letter
        // Store it in the relevant children array (node -> children[x] -> children[x])
        // If a space is read, set is_word true. And contine the loop.  

    // Open the dictionary
    FILE* infile = fopen(dictionary, "r");
    if (infile == NULL)
    {
        printf("Could not open %s.\n", dictionary);
        return false;
    }

    node* current_node = &root;
    for (int c = fgetc(infile); c != EOF; c = fgetc(infile))
    {
        if (c != '\n') 
        {
            // Calculate the index of the children array if c is a letter or an apostrophe.
            int index = (isalpha(c)) ? (c - 'a'): 26;  
            // If children[index] is NULL, add another node to it to suggest that the word hasn't ended yet.
            if (current_node -> children[index] == NULL)
            {
                current_node -> children[index] = calloc(1, sizeof(node));
                if (current_node -> children[index] == NULL)
                {
                    printf("Memory allocation failed!");
                    return false;// Or return 1???
                }

                current_node = current_node -> children[index];    
            }
            else
            {
                current_node = current_node -> children[index];
            }

        }
        // If c is a '\n', mark the node as the end of the word. And reset the current_node to the root.
        else
        {
            current_node -> is_word = true;
            word_counter ++;
            current_node = &root;
        }
    }

    fclose(infile);
    return true;
}

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

/**
 * Unloads dictionary from memory.  Returns true if successful else false.
 */
void free_node(node* cursor);
bool unload(void)
{
    //node* current_node = root;
    for (int i = 0; i < 27; i++)
    {
        if (root.children[i] != NULL)
        {
            free_node(root.children[i]);
        }

    }

    return true;
}

void free_node(node* cursor)
{
    for (int i = 0; i < 27; i++)
    {
        // If the child pointer do not point to Null, 
        // it suggests that the pointer points to another node.
        // So dive into the child node.
        if (cursor -> children[i] != NULL)
        {
            cursor = cursor -> children[i];
            // and return the for loop
            return free_node(cursor);
        }
    }
    // Continue the for loop
    // If reach the end of the loop, it suggests the pointer array all point to null.
    // Now you can free the current node.    
    free(cursor);
}
1

Take a close look at the code for free_node()

for (int i = 0; i < 27; i++)
{
    if (cursor -> children[i] != NULL)
    {
        cursor = cursor -> children[i];
        return free_node(cursor);
    }

It reassigns cursor before recursively calling free_node(). But what happens when it returns to this level? cursor is no longer pointing at the same node as when it started. Instead, it is one node lower. The remaining nodes will be skipped. Worse, it has a return statement attached, so it will immediately terminate the current loop and return control to the code that called free_node(), whether it was a higher level call or unload(). In short, a lot of memory is not being freed, but is being lost becasue parents are being freed.

This would be easily fixed with

{
    free_node(cursor->children[i]);
}

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 .