Speller - trie implementation - Segmentation Fault

Question

Having some trouble with a trie implementation of speller pset5 (2014). It seems to almost work, finding misspelled words, but then I get a segfault. It appears I have some memory problems, and I have pasted the relevant parts of my valgrind output below (running with --leak-check=full --show-leak-kinds=all --track-origins=yes).

Note that the lines identified by valgrind in dictionary.c are both in load:

73: root = calloc(1, sizeof(node));

105: cursor->children[letter] = calloc(1, sizeof(node));

Any advice?

[code snipped by mod]

void free_node(struct node* cursor) 
{
    cursor = root;
    if (cursor == NULL) return;

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

    free(cursor);
}

[code snipped by mod]

Valgrind:

==8102== Stack overflow in thread 1: can't grow stack to 0xbe510ffc
==8102== 
==8102== Process terminating with default action of signal 11 (SIGSEGV): dumping core
==8102==  Access not within mapped region at address 0xBE510FFC
==8102==    at 0x80492D8: free_node (dictionary.c:136)

==8102== Process terminating with default action of signal 11 (SIGSEGV)
==8102==  Access not within mapped region at address 0xBE510FF8
==8102==    at 0x4024510: _vgnU_freeres (in /usr/lib/valgrind/vgpreload_core-x86-linux.so)

==8102== 
==8102== HEAP SUMMARY:
==8102==     in use at exit: 41,113,184 bytes in 367,082 blocks
==8102==   total heap usage: 367,084 allocs, 2 frees, 41,113,888 bytes allocated
==8102== 

==8102== 112 bytes in 1 blocks are still reachable in loss record 1 of 2
==8102==    at 0x402C109: calloc (in /usr/lib/valgrind/vgpreload_memcheck-x86-linux.so)
==8102==    by 0x80490DD: load (dictionary.c:73)
==8102==    by 0x8048775: main (speller.c:45)

==8102== 41,113,072 bytes in 367,081 blocks are still reachable in loss record 2 of 2
==8102==    at 0x402C109: calloc (in /usr/lib/valgrind/vgpreload_memcheck-x86-linux.so)
==8102==    by 0x8049209: load (dictionary.c:105)
==8102==    by 0x8048775: main (speller.c:45)

==8102== LEAK SUMMARY:
==8102==    definitely lost: 0 bytes in 0 blocks
==8102==    indirectly lost: 0 bytes in 0 blocks
==8102==      possibly lost: 0 bytes in 0 blocks
==8102==    still reachable: 41,113,184 bytes in 367,082 blocks
==8102==         suppressed: 0 bytes in 0 blocks
==8102== Reachable blocks (those to which a pointer was found) are not shown.
==8102== To see them, rerun with: --leak-check=full --show-leak-kinds=all

==8102== ERROR SUMMARY: 0 errors from 0 contexts (suppressed: 0 from 0)
Segmentation fault (core dumped)

Thanks!

Answer 1

When you call you free_node function, you are passing it the root already, so cursor=root; is totally unnecessary.

In your loop over the children, you shouldn't set cursor to the children before freeing. That's what your recursion will do and by you doing it, you can end up hitting memory that you don't have access to, hence your segfault.