pset 05 trie large dictionary unload issue

Question

I am working through pset5 (Mispellings) using a trie and I am stumped. This is the error exactly from gdb (sample is a text file I made and works just fine with the small dictionary):

Starting program: /home/jharvard/Dropbox/CS_50x/pset5/speller sample.txt

MISSPELLED WORDS


Program received signal SIGSEGV, Segmentation fault.
_int_free (av=0xb7fc9420 <main_arena>, p=0x8af5d68, have_lock=0)
at malloc.c:3814
3814    malloc.c: No such file or directory.`

I have all the functionality working when the small library is loaded. I added in some code to tell me how many words I had unloaded before the error and was consistently getting between 20,000 and 30,000. Going up with gdb I get:

up
#1  0x08049579 in unload_all (root=0x804c008, c_node=0x8af5cf0, clear=11)
at trie_lib.c:235
235         free(c_node->children[clear]);
(gdb) p c_node->children
$1 = {0x0 <repeats 11 times>, 0x8af5d70, 0x0, 0x8af5f70, 0x0, 0x0,0x0, 
0x8af6c70, 0x0, 0x0, 0x0, 0x0, 0x0, 0x0, 0x0, 0x0, 0x0}
(gdb) p c_node->children[clear]
$2 = (struct node *) 0x8af5d70
(gdb) p c_node->children[clear]->children
$3 = {0x0 <repeats 27 times>}

I noticed that the malloc fault gives an address: p=0x8af5d68 is 0x8af5d70 - 2, but that could just be a result of how malloc works not that it's receiving the wrong address.

When I run Valgrind, I get:

==3246== Command: ./speller /home/cs50/pset5/dictionaries/large sample.txt
==3246== 

MISSPELLED WORDS

==3246== Stack overflow in thread 1: can't grow stack to 0xbe72bffc
==3246== 
==3246== Process terminating with default action of signal 11 (SIGSEGV): dumping core
==3246==  Access not within mapped region at address 0xBE72BFFC
==3246==    at 0x8049574: unload_all (trie_lib.c:235)

Here are important snippets of code (trying to be reasonable with the honesty policy):

// define the trie node struct
typedef struct node 
{
    bool is_word;
    int key; 
    struct node* previous;
    struct node* children[ALPHALEN];
}
    node;

// to show where key is set
int add_word(node* level, char* word, int* count, int* size)
{
// checks on word

// select letter based on count

// if letter does not exist in trie
if (level->children[letter] == NULL)
{
    // make new node
    node* next_level = add_node();
    next_level->key = letter;

    // set location to point at the next node 
    level->children[letter] = next_level;

    // set previous location 
    next_level->previous = level;
    (*count)++;

    // pass in the next node as the new location to look at 
    return add_word(next_level, word, count,size);
}

bool unload_all(node* root, node* c_node, int clear)
{
// if root was never populated

// clear if previous call found the bottom
if (clear != -1)
{
    //free up the current node
    free(c_node->children[clear]);
5. c_node->children[clear] = NULL;
}

// loop over the alphabet  (ALPHALEN = 27)
   {
    // if a letter is found
        // go down one level
        unload_all(root, c_node->children[i], -1);
   }

// if nothing was found at current level
{
    // free root and return if all is clear and at root
}
// go up one level and set clear
else
{
    unload_all(root,c_node->previous, c_node->key); 
}

return false;
}

The line marked with 5. doesn't make much sense to me since I don't see how I have access to that memory location as I just freed it. If I don't include it though, I get a double free error.

Any thoughts as to where I am going wrong would be appreciated. Is it possible that my whole problem stems from how I am loading the dictionary in the first place? Really appreciate any help!

Answer 1

@SFri: I agree that it's hard to tell without seeing some code, but I'll tell you what i think can happen from the errors and the pseudocode. The reason to set a recently freed pointer to null is to clean up and be tidy, but it should not affect how your function works. If you get a double free error by commenting out the line that sets the freed pointer to null, it's because the check for null is the only thing stopping your program from freeing memory twice. That suggest something wrong with the design of your recursion. You must be revisiting pointers twice at some point. I would focus on what happens each time the recursive call is performed. How do you check for "bottom"? Going too deep into recursion can cause the stack overflow error message, so I would first look into the function in detail. It's not likely than errors in the way you loaded the memory would cause a crash if the unload function is OK. I guess it could happen, but look into your recursion again and post it here if you have doubts.