0

FINAL EDIT

My function that frees the memory works properly; the problem lies in node creation. I now have a separate problem where the program segfaults when run normally, but it cannot be reproduced in gdb or valgrind. However, that is a separate question altogether.

I have since found out that this segfault happened because I did not check for the EOF character properly. As per Cliff B's answer in this question, the check for EOF happens only after the last character in the file. As a result, in my load function, I had assigned the last character of the file to some i (which in this case was -1 according to a printf call), and tried to create and access a child node that was not between 0 and 27 (each node in my trie structure has 27 node*s). This caused a segmentation fault, and also caused problems with my unload function, which would not unload the very last node I created.

UPDATE

While stepping through my load function, I notice an unexpected behaviour. I believe the problem lies somewhere in these lines of code, which are embedded within a for loop. The casting to (node*) is just to be safe, though it does not affect the running of the code to my knowledge.

// if node doesnt exist, calloc one, go to node
if (current_node->children[i] == NULL)
{
    current_node->children[i] = (node*) calloc(1, sizeof(node));
    nodes++;
}
current_node = current_node->children[i];

While stepping through the load function, I see that my current_node->children[i] seem to be calloc'ed properly (all children set to NULL), but the moment I step into current_node->children[i] and examine its children, I see that the addresses get screwed up. Specifically, the i'th child in the children node gets set to 0x0 for some reason. Can anyone shed light on how this might happen?

enter image description here

ORIGINAL QUESTION

So I somehow borked my code after it worked properly previously (though, it only ran well in gdb and valgrind but segfaulted when run directly). The problem seems to be in the function that frees my trie, which unload calls using free_all(root). It will run into a segmentation fault, but not immediately.

Here is my function, with some temporary printf calls for debugging purposes:

void free_all(node* curs)
{
    int i;

    // recursive case (go to end of trie)
    for (i = 0; i < 27; i++)
    {
        if (curs->children[i])
        {
            printf("from %p\t accessing children[%i] at\t %p\n", curs, i, curs->children[i]);
            free_all(curs->children[i]);
        }
    }

    // base case
    free(curs);
    printf("%p freed\t", curs);
    nodes--;
    printf("left %i nodes\n", nodes);
}

Here's the terminal output (the last few lines, anyway)

from 0x598f720   accessing children[24] at       0x59928d0
from 0x59928d0   accessing children[11] at       0x59929c0
0x59929c0 freed left 2005 nodes
0x59928d0 freed left 2004 nodes
0x598f720 freed left 2003 nodes
from 0x598f630   accessing children[18] at       0x5992ab0
from 0x5992ab0   accessing children[19] at       0x5992ba0
from 0x5992ba0   accessing children[4] at        0x5992c90
from 0x5992c90   accessing children[17] at       0x5992d80
0x5992d80 freed left 2002 nodes
0x5992c90 freed left 2001 nodes
0x5992ba0 freed left 2000 nodes
0x5992ab0 freed left 1999 nodes
0x598f630 freed left 1998 nodes
0x597fcd0 freed left 1997 nodes
from 0x603250    accessing children[24] at       0x5992e70
from 0x5992e70   accessing children[0] at        0x603000
from 0x603000    accessing children[0] at        0x241

Program received signal SIGSEGV, Segmentation fault.
0x0000000000401398 in free_all (curs=0x241) at dictionary.c:128
128             if (curs->children[i])

Here is the valgrind summary:

==12406== 
==12406== HEAP SUMMARY:
==12406==     in use at exit: 0 bytes in 0 blocks
==12406==   total heap usage: 367,084 allocs, 367,085 frees, 82,227,504 bytes allocated
==12406== 
==12406== All heap blocks were freed -- no leaks are possible
==12406== 
==12406== For counts of detected and suppressed errors, rerun with: -v
==12406== ERROR SUMMARY: 1006 errors from 6 contexts (suppressed: 0 from 0)

I seem to have more calls to free than allocs, but printing the number of nodes tells me otherwise. However, I think this is causing the problem, but I cannot figure out how it happens.

My nodes variable is an unsigned int, which is initialised to 1, and then incremented by 1 every time I call calloc. Here is an excerpt of my load function where I increment nodes:

for (int c = fgetc(file); c != EOF; c = fgetc(file))
{
    // if end of line, set is_word to true, go back to root and increase count

    // assign letters to node index


    // if node doesnt exist, calloc one, go to node
    if (current_node->children[i] == NULL)
    {
        current_node->children[i] = calloc(1, sizeof(node));
        nodes++;
    }
    current_node = current_node->children[i];
}
0

Good news / bad news kind of answer. I plugged your free_all() function into my code and tested it with a small dictionary and input file, along with the default large dictionary and holmes.txt. The result is that it worked flawlessly. It freed every node and valgrind reported no leaks.

In light of this, I would say that you have a problem in load. Somehow, something is probably going wrong in your trie as nodes are being added. Without seeing the load code, it's difficult to see where the problem lies.

If this answers your question, please click on the check mark to accept. Let's keep up on forum maintenance. ;-)

1
  • Am I allowed to post my entire load function here? I thought that was against the rules or something – jiewpeng Jan 9 '16 at 10:13

You must log in to answer this question.

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