0

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!

2
  • reasonable sure that valgrind is saying that the seg fault is coming from at 0x80492D8: free_node (dictionary.c:136)
    – ebobtron
    Aug 2 '15 at 5:31
  • also your call free_node(root) from unload and then assign cursor = root when cursor already equals root.
    – ebobtron
    Aug 2 '15 at 5:36
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.

2
  • Thanks! Any suggestions on optimizing code - I've add my slightly modified load and check functions above.
    – L.B.
    Aug 2 '15 at 16:17
  • @L.B. Please accept curiouskiwi's answer if it helped.
    – i_am_david
    Aug 2 '15 at 19:08

You must log in to answer this question.

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