0

I think I have load, check and size function running successfully. However, my code meets seg fault again. Valgrind reports:

==5654== Stack overflow in thread 1: can't grow stack to 0xffe801ff8

==5654== Process terminating with default action of signal 11 (SIGSEGV)

==5654== Access not within mapped region at address 0xFFE801FF8

---other things---

==5654== at 0x4014A6: unload (dictionary.c:204)

==5654== HEAP SUMMARY:

==5654== in use at exit: 1,792 bytes in 8 blocks

==5654== total heap usage: 10 allocs, 2 frees, 2,928 bytes allocated

---other things----

==5654== ERROR SUMMARY: 0 errors from 0 contexts (suppressed: 0 from 0) Segmentation fault

It seems there is something wrong in unload, I sue a recursion in the function. Here is the part of my code

// define a tries to load dictionary
typedef struct node
{
    bool is_word;
    struct node* children[27];
}
node;


// creat a pointer to track the beginning of trie
node* root;
node* destroyer;

// dictionary size counter
int dictionary_size = 0;



/**
* Initialize new nodes.
*/
void initialize(node* pointer)
{
    pointer->is_word = false;
    for(int i = 0; i < 27; i++)
    {
        pointer->children[i] = NULL;
    }
}


/**
 * Loads dictionary into memory.  Returns true if successful else false.
 */
bool load(const char* dictionary)
{
    root = NULL;
    destroyer = NULL;
    // open the dictionary file.
    FILE* dt = fopen(dictionary, "r");
    if (dt == NULL)
    {
        printf("Could not open %s.\n", dictionary);
        return 1;
    }

    // creat a pointer at the start of tries to track loading.
    node* new_node = malloc(sizeof(node));
    initialize(new_node);
    root = new_node;
    node* builder = root;
    destroyer = root;

    if (builder != NULL)
    {
        for (int ch = fgetc(dt); ch != EOF; ch = fgetc(dt))
        {
            if (isalpha(ch))
            {
                if (builder->children[ch - 'a'] == NULL)
                {
                    node* new_node = malloc(sizeof(node));
                    initialize(new_node);
                    builder->children[ch - 'a'] = new_node;
                }

                builder = builder->children[ch - 'a'];
            }

            else if ( ch == '\'' )
            {
                if(builder->children[26] == NULL)
                {
                    node* new_node = malloc(sizeof(node));
                    initialize(new_node);
                    builder->children[26] = new_node;
                }

                builder = builder->children[26];
            }

            // when hit \0
            else
            {
                builder->is_word = true;
                dictionary_size = dictionary_size + 1;

                // reset the pointer to the root, preparing for a new word
                builder = root;
            }
        }

        // hit EOF, close dictionary
        fclose(dt);
        return true;
    }

    return false;
}


/**
 * Unloads dictionary from memory.  Returns true if successful else false.
 */
bool unload(void)
{

    // set the lowest node as base case, then recursion.
    if (destroyer != NULL)
    {
        if (lowest(destroyer))
        {
            if (destroyer == root)
            {
                free(destroyer);
                return true;
            }
            else
            {
                free (destroyer);
            }
        }

        else
        {
            for(int j = 0; j < 27; j++)
            {
                if (destroyer->children[j] != NULL)
                {
                    destroyer = destroyer->children[j];
                    unload();
                }
            }
        }
    }
    return true;
}



/**
* Checks if the node is the lowest layer of trie.
*/ 
bool lowest(node* layer)
{
    if (layer != NULL)
    {
        for (int i = 0; i < 27; i++)
        {
            if (layer->children[i] != NULL)
            {
                return false;
            }
        }
        return true;
    }
    return false;
}

My questions are:

  1. in my small dictionary, I put 3 words : a, and, once. I tried to draw the trie with pen and paper, it only took 8 node allocs. Why valgrind reports 10 allocs?

  2. Why my code has seg fault? and why valgrind reports no error?

  3. Does the seg fault have something to do with the valgrind warning "Stack overflow in thread 1: can't grow stack to 0xffe801ff8" ? what does it mean?

David was right about saying pset5 is the hill top (for cs50)...

Thank you!

0

You are running out of stack memory in your recursive calls to unload. I suspect, based on this post, that you need a return after free (destroyer);

| improve this answer | |
  • I added return true after free(destroyer), but still, seg fault... – user13479 Sep 12 '16 at 21:49
  • Sorry, you need a return somewhere in that else loop. It goes there a lot and keeps calling unload(), but never returns. Use gdb, how many times is going to that loop? But really, read up on why a recursive function will cause a stack overflow (!) and apply what you learn to your program. There's several posts on this forum, and of course the internet-at-large. – DinoCoderSaurus Sep 12 '16 at 22:29
  • I fixed the seg fault. It's not the recursion. It's how I set the pointer destroyer. Anyway, although I got rid of the seg fault, I still have the problem: Valgrind reports total heap usage: 14 allocs, 3 frees, 3,824 bytes allocated after running with a small dictionary with only 5 words. Could you give me some hint on what's wrong with my unload function? I really want to figure out how to successfully unload all the nodes. Thanks – user13479 Sep 13 '16 at 2:40
  • Use these valgrind arguments valgrind -v --leak-check=full --show-leak-kinds=all --track-origins=yes to get more specific messages. Make an even smaller dictionary. 2 2-letter words and use gdb. What happens after you get to the first "is_word = true"? – DinoCoderSaurus Sep 13 '16 at 12:19
  • I used 1 word dictionary, valgrind reports 4 alloc and 3 free. ( I can't see why it takes 4 alloc to build a only 1 word dictionary.) And after I modified the codes, gdb does not reports any fault, the main funtion exits successfully, returning 0 and shows the "time report". Just the valgrind reports the first invalid read of size 8 at " if (destroyer->children[j] != NULL) " by unload. I edited the code and hope some hints so that I can make the code better :) – user13479 Sep 13 '16 at 20:59

You must log in to answer this question.

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