CharlesD89 CharlesD89 - 3 months ago 21
C Question

Issues to load a dictionary in a tree structure and unload it - C programming

I'm still trying to debug my load function which one is supposed to load a dictionary file. 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 and define them a specific type of value.

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 debugging because this is not my only issue!

Here the main error I get when I tried to run speller, main function calling load :

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);
}
}


If some more stuffs is needed to help me, just ask, and I will add. Thanks for your times guys.

Answer

Your load function looks OK. In your unload function you must first descend all nodes, then free the bottom node, then go one level up etcetera:

void recursive_free (node* node_to_free)
{
    for (int i = 0; i < NB_NODES; i++)
    {
        // if children found
        if (node_to_free->children[i])
        {
            recursive_free(node_to_free->children[i]);
        }
    }
    free(node_to_free);
}
Comments