PSET5 - Issues with initialization of pointers in LOAD function

Question

I'm still trying to debug my load function, I rewrite my code again and again but with no result... I know we need to have specific question, but now I just have so many questions. So, I'll go with what I think is the source of my error. I think I don't initialize my two pointers correctly, by initialized, I mean allocate the memory.

There, how I define and initialize the structure of my nodes and pointers :

#include "dictionary.h"
#define NB_NODES 27

// define global structure and pointers
typedef struct node
{
    bool is_word;
    struct node* children[NB_NODES];
} node;

// initialize pointers and variables
node* root = NULL;
node* current = NULL;
int word_counter = 0;

Now, there is my implementation of LOAD :

bool load(const char* dictionary)
{
// open dictionary file
FILE* inptr = fopen(dictionary, "r");

if (inptr == NULL)
{
    printf("fail to open dictionary\n");
    return false;
}

// initialize tools
root = malloc(sizeof(node));
word_counter = 0;
int index = 0;
current = root;

// looks for word until end reached
for (int c = fgetc(inptr); c != EOF; c = fgetc(inptr))
{
    // looking words one by one
    if (c != '\n')
    {
        if (c == '\'')
        {
            index = 26;

            if (current->children[index] == NULL)
            {
                current->children[index] = calloc(1, sizeof(node));

                // test
                if (current->children[index] == NULL)
                {
                    printf("error with apostrophe");
                    return 1;
                }

            }
        }

        else
        {
            index = c - 'a';

            if (current->children[index] == NULL)
            {
                current->children[index] = calloc(1, sizeof(node));

                // test
                if (current->children[index] == NULL)
                {
                    printf("error with characters");
                    return 1;
                }
            }
        }

        // update current pointer to the next node
        current = current->children[index];
    }

    else if (c == '\n')
    {
        // new word found
        if (current->is_word == false)
        {
            current->is_word = true;
            word_counter++;
            current = root;
        }

        // duplicate word
        else
        {
            current = root;
        }
    }

    // character not found
    else 
    {
        printf("character not found");
        return 2;
    }
}

fclose(inptr);
return true;
}

So in my headers statements, I declare my pointers equal to NULL, and let them accessible by all sub functions (global variable). After, in the top of LOAD, I allocate memory size of a node, to my pointer root. I have tried many ways to code this but the one shared appear me to be the most logical.

I also have doubt about the way I reinitialize the root pointers after a complete word is found. May be in doing that, the way I do, I "lost" the track of the word just found?

Help would really be appreciated on this case to continue my debugging of speller.

Here the main error I get when I tried to run speller :

jharvard@appliance (~/Dropbox/pset5): ./speller                  ~cs50/pset5/dictionaries/small/austinpowers.txt
Could not open /home/cs50/pset5/dictionaries/small/austinpowers.txt.
*** Error in `./speller': double free or corruption (!prev): 0x094302d8 ***
Aborted (core dumped)
jharvard@appliance (~/Dropbox/pset5): 

I also launched speller in gdb and got this error :

jharvard@appliance (~/Dropbox/pset5): gdb ./speller
Reading symbols from ./speller...done.
(gdb) run ~cs50/pset5/dictionaries/small/austinpowers.txt
Starting program: /home/jharvard/Dropbox/pset5/speller     ~cs50/pset5/dictionaries/small/austinpowers.txt
Could not open /home/cs50/pset5/dictionaries/small/austinpowers.txt.
*** Error in `/home/jharvard/Dropbox/pset5/speller': double free or     corruption (!prev): 0x0804c2d8 ***

Program received signal SIGABRT, Aborted.
0xb7fdd428 in __kernel_vsyscall ()
(gdb) 

Curiously when I go forward step by step in gdb, I can go through my load loop without receiving failures...

There is my code of UNLOAD (REVISED) :

bool unload(void)
{
// recursive_free prototype
void recursive_free (node* node_to_free);

recursive_free(root);

    if (root == NULL)
    {
        return true;
    }

    else return false;
    }


void recursive_free (node* node_to_free)
{
    for (int i = 0; i < NB_NODES; i++)
    {
        // node created to assign memory to free if children found
        node* temp;

        // if children found
        if (node_to_free->children[i])
        {
            temp = node_to_free;
            node_to_free = node_to_free->children[i];
            free(temp);
            recursive_free(node_to_free);
        }

        else free(node_to_free);
    }
}

Answer 1

Look at the following code:

current = root;

for (int i = 0; i < NB_NODES; i++)
{
    recursive_free(current);
    recursive_free(root);
}

You free all of the children under current and then try to free all of the children under root. Since root and current both point to the same memory location, you're trying to free all of the same memory a second time - that's the double free.

In this code, there's no need to create a new pointer called current. Instead, you could just call recursive_free(root) and be done with it.

However, you still have more issues. You never actually free the memory allocated to root. Even if you do, you have assumed that something will cause root to be set to NULL. That doesn't happen. Even though the memory is freed, the pointer remains pointed at that address, which is now an invalid memory call. Your unload() function would return false even if successful.

Also, your logic has a flaw. If a node has no children, it will be freed, but if it does, the children may be freed, but the current node will be skipped over. The result is that only nodes with no children will be freed. All others will remain and will be a memory leak.

Since you say that you are still debugging your load function, I would suggest that you remove your code from the unload() and any other functions until you get load and check working. Restore everything except load and check to what was given in the downloaded file before you started. Even though the code won't pass valgrind, the code stubs will compile and execute while you debug load and check. You can work on the rest later.

There may be other issues, but this will give you a lot to think about. At least it answers why you have the double free error.

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