0

In pset5, I have made load (using a trie), check and size run successfully, even my whole codes passed check50. I believe so because when I do spell check a text using the big library, I get the same result as that of the staff code.

However, valgrind reports my code has memory leaks and lots of errors, I guess it is the unload function.

My code can exit normal, returning 0 and showing the "time usage", so gdb does not help me. I tried different coding but still can not fix it. I really need help here...Please point out what is wrong in my code. Thanks!

My psuedocode for unload is:

  1. if the node is the lowest, free it. (base case)

  2. unload all the children nodes,

  3. free the current node.

Here is my load and unload functions:

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

// global variables tracking the beginning of trie
node* root;
node* destroyer;

/**
* 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.
    root = malloc(sizeof(node));
    initialize(root);
    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;
                    new_node = NULL;
                }

                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))
        {
            free(destroyer);
            return true;
        }

        else
        {

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



/**
* 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;
}
0

The problem lies in this code block:

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

When destroyer->children[j] is not null, destroyer gets reassigned to the child and unload is called. On return from that call, destroyer is one level lower in the trie. The rest of the children at the previous level never get checked, leaving them behind. Perhaps destroyer needs to be restored to its previous value on return?

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

  • A minor question: I test my code with a small dictionary, which contains only 1 word "a". Valgrind reports there are 4 allocs. I drew the trie structure, it only takes 2 nodes, one is root the other is the node with is_word returning true. Why the code malloc 4? – user13479 Sep 15 '16 at 2:50
  • There are also two file pointers that you need to account for, the input file and the output file. I believe a file pointer is 568 bytes each. You can do the math. ;-) – Cliff B Sep 15 '16 at 3:03

You must log in to answer this question.

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