1

I'm trying to implement a trie for pset5. The program compiles, and appears to spit out the right output, except Valgrind seems to have a LOT of issues with it! First, there's the memory leak, which seems to be a product of something wrong in my load() code. Then, there's the ERROR SUMMARY which seems to be related to the issue in load(). Running Valgrind again with -v shows that the errors all seem to be stemming from the same place.

==11941== HEAP SUMMARY:
==11941==     in use at exit: 3,865,120 bytes in 17,255 blocks
==11941==   total heap usage: 367,084 allocs, 349,829 frees, 82,227,504 bytes allocated
==11941== 
==11941== 3,865,120 (1,916,768 direct, 1,948,352 indirect) bytes in 8,557 blocks are definitely lost in loss record 2 of 2
==11941==    at 0x4C2CC70: calloc (in /usr/lib/valgrind/vgpreload_memcheck-amd64-linux.so)
==11941==    by 0x40114B: load (dictionary.c:48)
==11941==    by 0x4008CD: main (speller.c:45)
==11941== 
==11941== LEAK SUMMARY:
==11941==    definitely lost: 1,916,768 bytes in 8,557 blocks
==11941==    indirectly lost: 1,948,352 bytes in 8,698 blocks
==11941==      possibly lost: 0 bytes in 0 blocks
==11941==    still reachable: 0 bytes in 0 blocks
==11941==         suppressed: 0 bytes in 0 blocks
==11941== 
==11941== For counts of detected and suppressed errors, rerun with: -v
==11941== ERROR SUMMARY: 27101 errors from 6 contexts (suppressed: 0 from 0)

These are the initializations I have in dictionary.h, if it matters:

typedef struct node
{
    bool is_word;
    struct node* children[27];
} node;

node* root;
node* cursor;
int words_in_trie;

Here is my load() function, which Valgrind claims is causing an issue when I calloc memory for a new_node. I have tried to free(new_node) in several locations in my load() body, but there would always be some problem or another. I did manage to get all the memory leaks out when I added free(new_node) in the place where I've commented it in below, but when compiling and executing this, I always get a segmentation fault. Also, the number of errrors skyrockets. Please tell me what's wrong! I've been searching the forums for ages, and I really can't figure it out...

bool load(const char* dictionary)
{
    // open dictionary
    FILE* dict = fopen(dictionary, "r");
    if (dict == NULL)
        return false;

    // start up the trie
    root = calloc(1, sizeof(node));
    cursor = root;
    node* new_node = NULL;

    //take one char from dictionary at a time
    //put into trie
    // when encounter \n, is_word becomes true
    for (int c = fgetc(dict), position; c != EOF; c = fgetc(dict))
    {
        if (isalpha(c) || c == '\'')
        {
            if (isalpha(c))
                position = c - 'a';
            else
                position = 27;

            // if there's no open nodes, make new node for c
            if (cursor->children[position] == NULL)
            {
                new_node = calloc(1, sizeof(node));
                if (new_node == NULL)
                {
                    printf("Out of space for new nodes.\n");
                    return false;
                }

                cursor->children[position] = new_node;
                //free(new_node);
            }

            // update cursor
            cursor = cursor->children[position];
        }

        else
        {
            cursor->is_word = true;
            words_in_trie++;
            cursor = root;
        }
    }

    //check for file errors
    if (ferror(dict))
    {
        fclose(dict);
        printf("Error reading dictionary file");
        unload();
        return false;
    }

    //close file and return
    fclose(dict);
    return true;
}

I just know Valgrind is upset with my callocing, but I thought I had gotten rid of all that with my unload() -- which, if you were curious, looksl like this:

/**
 * helper function for unload
 */
void free_trie(node* cursor)
{
    for (int i = 0; i < 27; i++)
    {
        if (cursor->children[i] != NULL)
            free_trie(cursor->children[i]);
    }

    free(cursor);
}

/**
 * Unloads dictionary from memory.  Returns true if successful else false.
 */
bool unload(void)
{
    free_trie(root);
    return true;
}

Please let me know if you know what's wrong with the code I spat out -- and thanks in advance!

1

You can't free nodes in load() because you need them to persist for the life of the program.

The recursive calls to free_trie() are running out of stack memory. From this post answer 1:

Each time you call a function, a certain amount of stack is eaten (usually dependent on the function). The eaten amount is the stack frame, and it is recovered when the function returns.

Here's another interesting post on the topic.

The small dictionary will do 11 calls to free_trie() before it does it's first free. That can stack up pretty quick in the large dictionary.


Does valgrind mention any invalid read/write? Another leak-waiting-to happen is here: position = 27;. According to your node definition (struct node* children[27];) children[27] is not allocated. Depending on dictionary, that's a segfault-waiting-to-happen too.

6
  • I just reviewed my unload code, and I don't see how I'm only freeing 27 nodes -- could you elaborate? Since it's a recursive call, it should be able to keep going down the trie until the bottom, and make its way up/down until all nodes are freed. Good catch on the position value though, I should have set it to 26 for the apostrophe, forgot about the 0-indexing!
    – Connie
    Apr 6 '16 at 3:22
  • DOH! Yes, I read that wrong. It is still the root of your problem, answer has been amended. Apr 6 '16 at 16:14
  • I see, I did not know that was a thing, but it makes sense! How would I go about solving such a problem? If I make the stack size larger (assuming I'm allowed to do so), would it be fixed? Is there some other way to approach it?
    – Connie
    Apr 7 '16 at 0:50
  • I added return; after free(cursor); -- it seems to have cleared up the issue. Who knew it was so simple? But now I get what's going on. Thanks!
    – Connie
    Apr 7 '16 at 0:57
  • @DinoCoderSaurus I seem to have similar problem but I have written "return;" for the recursive delete code. If you could have a look at my code and suggest changes. Program works perfectly in terms of logic but memory leaks are an issue. Jun 28 '16 at 1:43

You must log in to answer this question.

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