0

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!

2
  • Lots of info, but we really need to see the code. Please edit your question and post the typedef struct for your nodes, related declarations, unload() and any other functions that it calls. – Cliff B Jul 8 '15 at 0:04
  • I tried not to add too much straight code but I can add more if need be. If something doesn't make sense, I can just copy unload_all() completely. – SFri Jul 8 '15 at 3:32
2

@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.

5
  • See added code. Thanks for your help! – SFri Jul 8 '15 at 3:33
  • 1
    @SFri: Not sure what you're trying to do in your recursive function. What are the calls with c_node->previous as argument? Also, in your other call you're actually assigning a value of -1 to "clear" and then you're trying to free c_node->children[clear]. Nothing good will ever come from trying to free an item at a negative array index. With respect to the add_word function, i don't think using recursion is a good idea. Also, i don't really know why you're moving backwards as well as forward from pointer to pointer. – Irene Jul 8 '15 at 6:35
  • Hopefully to clarify: c_node->previous sets the next current node to the node one level (one letter) above the current node. Clear is assigned a valid (ie 0-26) int at a leaf so that on the next time through unload_all, the node c_node->children[clear] can be freed. I used clear and previous so that I could free a node from a level above that node (ie word is cat, I free the node associated with the t while the current node is that associated with a). A better way (I didn't think it would work) would be to free the current node and then pass the previous node as the current node in unload_all. – SFri Jul 8 '15 at 20:33
  • @SFri: This line: return unload_all(root, c_node->children[i], -1); Clearly passes -1 to clear (no pun intended). I don't know why you say that you're only passing valid values when your function prototype is bool unload_all(node* root, node* c_node, int clear) Also, my question with respect to node->previous is why are you calling your recursive function with it as an argument. If you understand recursion, you should understand that you need to go deep till you reach the bottom ('t' in this case) and recursion will take care of going upwards. – Irene Jul 8 '15 at 23:04
  • I realized that you are completely right and that I needed to do some review on recursion. It is a learning process. I pretty much rewrote unload() and it's all working now. Thanks for you help! – SFri Jul 10 '15 at 6:55

You must log in to answer this question.

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