0

I have been trying to solve this problem for about 3 weeks now...after multiple iterations I just cannot seem to find what I am doing wrong in the load or unload functions to trigger this error. Below is my code, and I will follow this with a brief explanation of what I think is happening.

Global variables & Other info

// Maximum length for a word
// (e.g., pneumonoultramicroscopicsilicovolcanoconiosis)
#define LENGTH 45

// Number of node pointers in children
#define SIZE 28

// declare trie node
typedef struct node
{
    bool is_word;
    struct node *children[SIZE];
}
node;

// declare root and trav pointers
node *root;
node *trav;

// declare int used for size function
unsigned int wordcount = 0;

// number of nodes
int nodes = 0;

Load function:

// Loads dictionary into memory, returning true if successful else false
bool load(const char *dictionary)
{
    // declare word char
    char word1[LENGTH + 1];

    // assign root node
    root = (node*)calloc (1, sizeof(node));
    nodes++;

    // check if there is space for new node
    if(!root)
    {
        unload();
        return false;
    }

    // receive word from dictionary
    FILE *file = fopen(dictionary, "r");

    if (!file)
    {
        printf("File does not exist!\n");
        return false;
    }

    // loop through each word in the dictionary
    while (fscanf(file, "%s", word1) != EOF)
    {
        // set trav node to root node
        trav = root;
        int j;
        // loop through word1
        for (int i = 0; i < strlen(word1); i++)
        {
            // convert word character to integer
            if (word1[i] == '\'')
            {
                j = (word1[i] - 13);
            }
            else
            {
                j = (word1[i] - 'a');
            }

            // check if trav->children is null
            if (!trav->children[j])
            {
                // if it is create a new node and point trav at it
                node* new_node = (node*)calloc (1, sizeof(node));
                nodes++;

                // check if there is space for new node
                if(!new_node)
                {
                    unload();
                    return false;
                }
                trav->children[j] = new_node;
                trav = trav->children[j];
            }

            // else move trav to next node
            else
                trav = trav->children[j];
        }

        // at end of loop set is_word to true at last node
        trav->is_word = true;
    }

    fclose(file);
    return true;
}

Unload function

// Unloads dictionary from memory, returning true if successful else false
bool unload(void)
{

for (int i = 0; i < nodes; i++)
{
    found(root);
}
    return true;
}

// finds node at end of trie and frees it
void found(node *ptr)
{
    // recursive case
    for (int i = 0; i < SIZE; i++)
    {
        if (ptr->children[i]) // line 167
        {
            return found(ptr->children[i]);
        }
    }

    // base case
    free(ptr);
    return;
}

When I debug the program with a small dictionary containing the word "abc", I can see that *ptr travels to the same place twice, namely the address of root->children[0]->children[1]->children[2] and tries to free the node contained in that address each time (which I assume is causing the double free error). But why is it doing this the second time? Shouldn't freeing it the first time cause my found function to point *ptr at the next node up the second time?

When I run Help50 Valgrind I receive the following: "Looks like you're trying to access 8 bytes of memory that isn't yours? Did you try to index into an array beyond its bounds? Take a closer look at line 167 of dictionary.c." I have indicated line 167 in the unload() code above.

If I am misunderstanding pointers, recursion, or there are any glaring errors in my code, I would so appreciate your help. Thanks!

5
  • I'm not posting an answer because this is from the gut, not from empirical evidence. I think the problem is nodes. With your test file, nodes will be 3 (ish). So the nodes loop in unload will try to free root 3 times. No? Nov 24 '18 at 14:23
  • And another thing on a quick scan: calling unload in load usually has a bad result. Let speller manage the unload. Nov 24 '18 at 14:30
  • Dino, I disagree. The usage is a common error cleanup. While not necessary in this particular pset problem, it is a good implementation of freeing memory when an error is encountered to clean things up, in preparation for the program trying to prep for a recovery. OTOH, if the program is going to abort, it isn't needed.
    – Cliff B
    Nov 24 '18 at 20:02
  • @CliffB But (generally speaking, not just this code) if unload is called in load and it frees root, then when speller calls unload it will try to free root again and crash, won't it? Maybe it's a faulty memory on my part. Nov 24 '18 at 21:24
  • Well, that would be a valid argument if speller actually did then call unload in that scenario. However, if load returns false, then speller will throw an error and return 1 to the OS immediately. In either scenario, it's critical to know what happens when an error happens and what all of the involved code will do. Good lesson for everyone!
    – Cliff B
    Nov 24 '18 at 21:39
0

For that to work properly, you would have to null the pointer after free, so the next call won't go the same direction and find a pointer to some node no longer existing. Either the calling part would have to null, or you would have to pass a pointer to the pointer, so that the called function can null it itself.

But it can be done in an easier, and more efficient way, with minor modifications.

In unload, you should not have a loop, but only a single call to your recursive function.

In found, remove the return from the loop. That way, after the for loop, you know that none of the subtries exists and you are free to free that node.

3
  • The easier method worked! but I am not sure why, specifically in terms of what ptr is doing. When I free ptr after it has found a node at the bottom of the trie, it automatically points at the next node above it, and continues to go through the for loop from the point after it had dropped down. Eg. if it dropped down at children[2], freed that node, and then travelled back up, it re enters the loop at children[3]. Why this behavior? If this isn't clear, I am happy to lay out this question in answer format with code appended. Thank you! Nov 26 '18 at 17:47
  • Each time you call found, it gets another ptr variable that exists until that particular function has returned. Each call will only see its own.
    – Blauelf
    Nov 26 '18 at 18:05
  • Gotcha. I had completely forgotten about this aspect of recursion. This is not starting to make sense. Thank you! Nov 27 '18 at 11:18
0

Both an answer and more questions - and then a solution.

I look at the code and see that for children[i], i should have a range of 0 to 27 inclusive. What is the value of SIZE? If it is anything other than 28, that will cause problems. Since the error is occurring on the first usage of ptr->children[i] in the function, this makes me even more suspicious. I'm inclined to think this is a corruption fail and not a double free fail.

If this is not the issue, please edit the question and add the struct definition, the SIZE definition, and any other related code that's missing.

[EDIT: addendum]

It took a little time after not seeing the forest for the trees, but I found the issue. ;-)

The problem lies in the unload function itself. It appears that the intent was to process each pointer stored in the root structure, demonstrated by the presence of the for loop. However, the call to found() passes root itself, not the pointers in the struct (root->children[i]).

Think about the impact that has. found() will ultimately free the pointer that is passed to it. What happens when the loop runs the second pass? root has already been freed! So, guess what happens? Keep in mind that root still contains the same address, but it is no longer valid. In short, the results are both unpredictable and bad.

That's the main problem here. There are other issues lurking in wait, but those are for another question.

Here's one freebie though. Take a close look at how you're handling \'. What's the actual decimal ASCII code for an apostrophe? ;-)

Happy coding!

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

2
  • Thank you Cliff, I updated size to 28 (the program outputs the same error), and added my global variables declarations and other info at the top of the original question. Any further help appreciated as I am super lost on this one! Nov 25 '18 at 11:21
  • Thank you Cliff, I wound up solving the problem with Blauelf's help (see above). I really appreciate your taking the time to answer my questions. Nov 27 '18 at 11:19

You must log in to answer this question.

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