0

working on pset4 speller via trie. I AM AWARE OF THE CLANG BUG. According to one of the answers in the original question i removed the -fsanitize flag and ran valgrind() on it while using a small dictionary of :

do
dog
foo
fox

so valgrind gives this message:

HEAP SUMMARY:
==603==     in use at exit: 0 bytes in 0 blocks
==603==   total heap usage: 13 allocs, 13 frees, 12,112 bytes allocated
==603== 
==603== All heap blocks were freed -- no leaks are possible
==603== 
==603== For counts of detected and suppressed errors, rerun with: -v
==603== ERROR SUMMARY: 1468 errors from 11 contexts (suppressed: 0 from 0)

Is the last line ok??? Is the unload working fine ??? It says that there is no memory leak...

BUT when i ran valgrind with the default large dictionary .Probably after printing misspelled names the IDE seems to lose connection to server and i am prompted to the dashboard. I think there is something wrong with my unload, which is probably not showing when i use small dictionary. This is the unload which is working fine(in a sense that i am not getting segfault)

bool func_unload(node *unloader)
{
    node *temp = unloader;
    for(int i = 0; i < N; i++)
    {
        temp = unloader;
        if(unloader -> children[i] != NULL)
        {
            func_unload(unloader -> children[i]);
        }
    }
    free(unloader);
    unloader = temp;
    return true;
}

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

    return true;
}

Most importantly why is the IDE shutting down

EDIT: here is the load

while (fscanf(file, "%s", word) != EOF)
    {
        node *trav = root;
        for(int i = 0, s = strlen(word); i < s; i++)
        {
            if (isalpha(word[i]))
            {
                index = tolower(word[i]) - 97;
            }
            else
            {
                index = 26;
            }

            if ((trav -> children[index]) == NULL)
            {
                (trav -> children[index]) = malloc(sizeof(node));


            }

            trav = trav -> children[index];

        }
        trav -> is_word = true;

    }

    // Close dictionary
    fclose(file);

EDIT: So plz take a look at my size function. Sorry but i have to clear this concept in my mind.

unsigned int size(void)
{    
    node *trav = root;
    int ctr = 0;
    for (int i = 0; i < N; i++)
    {       
            //Sizer is also a node pointer initialized to root previously
            if (sizer -> children[i] == NULL)
            {
                continue;

            }
            else
            {   
                //Store the current value of sizer 
                trav = sizer;

                //Change sizer to point to its child
                sizer = sizer -> children[i];

                if ((sizer -> is_word) == true)
                {
                    ctr ++;
                }
                // recursively call size again
                int x = size();
                ctr += x;

                /*After adding the number all the words IN THE CHILDREN of this particular child, I want to point to the original `sizer`, so that i can move on to the next child and repeat the same for its chidren. To do that i need something to point back to original position*/
                sizer = trav;

            }

    }

    return ctr;

I think definitely here i need trav pointer , because otherwise i am not getting the actual number of words. Here i am using trav to explicitly go to the previous location, it is not being remembered as you saying.

4
  • temp is totally unnecessary, you can remove it. Otherwise looks fine. If there are issues, they are probably in load (e.g. due to not initialising all of your allocated nodes, setting children pointers to NULL and is_word to false), or less likely in check (some people call free there, freeing nodes still in use). Does valgrind really not list those 11 contexts? No idea about the IDE. – Blauelf Jul 16 '19 at 20:24
  • i think these eleven contexts are only when i use the small dictionary , when i use the default one after printing the misspelled words , ( i think during execution of unload() ) , it just says there is no connection and prompts me to return to dashboard. BTW i gave my load function() – CeNiEi Jul 16 '19 at 21:05
  • I was right, you don't initialise your nodes. Try calloc instead of malloc, it's about the same but overwrites the allocated memory with zeroes, which is NULL for pointers and false for booleans, exactly what we need. – Blauelf Jul 16 '19 at 21:26
  • THANK YOU SO VERY MUCH!!!!!!FINALLY GOT THAT RIGHT!!! – CeNiEi Jul 16 '19 at 21:45
1

The result of the comment discussion as an answer.

I still have no idea why the IDE would time out, I am guessing valgrind had a hell of a job counting all the occasions where you read from uninitialised memory.

Turns out the nodes malloced in load were not initialised. That could be done by something like (adjust variable names as needed)

node *new_node = malloc(sizeof(node));
for (int i = 0; i < N; i++)
    new_node->children[i] = NULL;
new_node->is_word = false;

or equivalently

node *new_node = calloc(1, sizeof(node));

calloc does the same as malloc, but additionally overwrites everything with zero bytes, which happen to be interpreted as NULL and false, so exactly what we need.

13
  • BTW why temp is not necessary in the unload function ?? Isn't it actually pointing to to where unloader was pointing to before being pointed to its children. and after freeing that unloader i need to point unloader to point to where we left off before calling the function recursively (I think this is what i am doing) – CeNiEi Jul 16 '19 at 23:23
  • I tried deleting the temp node and the program is still running fine and is also freeing all the nodes. Shouldn't i get an error or something?? – CeNiEi Jul 16 '19 at 23:34
  • @CeNiEi You copy over the value of unloader into temp. But the value of unloader never changes, so you now have two variables of same value. I think you might have confused that with unloading a linked list in a loop, where you had a use-after-free if you did not store the pointer to the current and next node in separate variables before freeing the current one. – Blauelf Jul 17 '19 at 5:28
  • Ok but i think i am doing that. I make an alias to the unloader BEFORE it is changed. so temp is pointing to unoalder (for now) then i change unlaoder to point to its child. After freeing all children of this child i now want to get back and move to next child and so on. Dont you think i need a pointer to point to unloader before it started pointing to its child , to move on to the next child – CeNiEi Jul 17 '19 at 6:00
  • You don't assign to unloader, so it does not change. – Blauelf Jul 17 '19 at 6:07

You must log in to answer this question.

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