0

Before starting explaining my issue, I know there are threads talking about Conditional jump or move depends on uninitialised value(s) errors prompted after executing Valgrind but unfortunately, none of them helped me fixing my problems.

Also, I've already asked a question about this pset a few months ago, feel free to check it here as it fully described how I designed my code (I'll sum up the main parts of it below).

Long story short, I've done this pset a while ago, it works but I don't know why, I've totally skipped the Valgrind part... I'm currently revising all my psets before submitting them and well, when I came to verify pset5 and executed Valgrind, I had 9911860 errors reported... Not bad! :)

Last thing, I've read again and again these two threads:

Valgrind error in PSET6

valgrind messages about “unititialised value(s)” - are they an issue?

Both are treating Conditional jump or move depends on uninitialised value(s) issues and I'm sure I'm missing something very important over there, I've even posted a comment in the last one a few days ago but no answer came unfortunately.

OK so I've declared my node as it follows

//dictionary.h

typedef struct node
{
    bool is_word;
    struct node* children[27];
}
node;

At the top of my dictionary.c sheet, I've declared as global variables

node* root;
node* newptr;

Later in the load function, I call root like this:

root = (struct node*) malloc(sizeof(node));
for (int i = 0; i < 27; i++)
{
    root->children[i] = NULL;
}

I've taken the idea of the for loop from Kareem's answer in Valgrind error in PSET6 topic except I didn't write root**[i]**->children[i] = NULL; as I can't compile my code then, I need to replace -> by a dot... and my errors count sees a rise of 25 errors (9911860)! Removing the index to root helped me to reduce the number of errors to 9911833, a 27 errors drop that totally makes sense to me.

Later in the load function, I declare newptr to be the next nodes in my trie:

node* newptr = (struct node*) malloc(sizeof(node));

This declaration comes in the loop that iterates through each character in the dictionary, inside the if statement checking if the end of the word in the dictionary has been reached.

If I apply the same method of initialization used for root, something like this for instance

node* newptr = (struct node*) malloc(sizeof(node));
for (int i = 0; i < 27; i++)
{
    newptr->children[i] = NULL;
}

The errors count doesn't drop.

Talking about newptr, I use this node as it follows:

if (isalpha(letter))
{
    if (newptr->children[letter - 'a'] == NULL)
    {
        newptr->children[letter - 'a'] = (struct node*) malloc(sizeof(node));
    }
    newptr = newptr->children[letter - 'a'];
}

Valgrind points out every lines like if (newptr->children[word[i] - 'a' == NULL) and newptr->children[letter - 'a'] = (struct node*) malloc(sizeof(node)); to be the source of the errors. Even the declaration of the node newptr itself is identified as an error.

If I pull this loop

for (int i = 0; i < 27; i++)
{
    newptr->children[i] = NULL;
}

or this

newptr->children[word[i] - 'a'];

before

newptr = newptr->children[letter - 'a'];

my errors count collapses to 2 or 3 errors but my code can't compile anymore due to a Segmentation Fault (core dumped).

Can someone please help me or at least explain me why the "NULL initialization loop" works for the root node but never works for the newptr node.

If more pseudo or chunks of my code are needed to understand my problem, please tell me and I'll edit my question.

4
  • What's the relationship (if any) between newptr and root? It would seem to me, from what you say, that you declare and initialize root, and tnen you declare a new node pointer (newptr), which is local to load, and which has no relation to root? So where and how do you load stuff into your trie, the one that you declared as global with "root"?
    – Irene
    Nov 11 '15 at 20:27
  • root is the root node of my trie and newptr is the node used for all the other nodes coming after the root node in my trie. Both root and newptr use the same struct node and both are now declared as global, at the top of my dictionary.c sheet code. In my first attempts, it is true that only root was declared as global but declaring newptr as global too hasn't improved anything. I edit right now my question as I forgot to mention that both root and newptr are now global.
    – DFATPUNK
    Nov 12 '15 at 8:31
  • Yes, but root and newptr are two different pointers that point at two different addresses. Why? How are you using them exactly? What are you freeing? Which one are you using in check? And, of course, what happens when you run gdb? Where is the segfault?
    – Irene
    Nov 14 '15 at 2:18
  • @Irene I've finally figured it out, please see my answer for more details. Thanks for your help!
    – DFATPUNK
    Nov 25 '15 at 14:18
0

First of all, I highly recommend you to read this thread: https://www.reddit.com/r/cs50/comments/3r0zb0/memorysegmentation_problems_with_dictionaryc_and/

I have done two major errors, I'll divide my answer in two parts for more clarity (well, I hope so!).

1. Setting nodes to NULL or false using memset()

In this thread, they talk about using memset() to set memory to false and NULL depending which line of the node (0 in memset() can mean both NULL and false).

In my load function, I've malloc'ed root = malloc(sizeof(node)); and that's it. If you use memset like this:

root = malloc(sizeof(node));
memset(root, 0, sizeof(node));

It will set your root node into something like this:

root->is_word = false;
root->children[27] = {NULL};

And that's exactly what we need to stop leaking memory! memset() must be used everytime you use malloc() to make sure everything is set to NULL or false. That means, you have to use it also in your loop, everytime you malloc a newptr...

This loop I was using

for (int i = 0; i < 27; i++)
{
    newptr->children[i] = NULL;
}

is ineffective and must be replaced by a memset().

2. Declaring newptr correctly

In her first comment, Irene (thank you for your help) underlined the undefined roles that root and newptr were playing in my code. Both are global variables but their use were unclear and indeed, newptr wasn't used properly.

In my load function, I first call root to malloc() and memset() it. Once the root of my trie correctly set, I open a first loop to get each character in the dictionary before loading the first word into my trie thanks to a second loop. In between, I was declaring newptr exactly how I declared root before the first loop iterating through the dictionary:

newptr = malloc(sizeof(node));
memset(newptr, 0, sizeof(node));

After adding all the memset() after all the malloc() in my load function, Valgrind was only pointing two errors, both coming from my newptr declaration.

When I loop through the first word read from the dictionary to store it in my trie, I first stores the first letter in my root node, then the second letter in a newptr node, the third in another newptr node and so on. At the end of the day, there are multiple newptr nodes, all descending from the root node of my trie.

If in every possible cases, that is to say:

 if (root->children[i] == NULL) // letter never stored in the root node
 if (newptr->children[i] == NULL) // letter never stored in the given newptr node
 if (newptr->children[26] == NULL) // apostrophe case

you correctly malloc() and memset() the next node of your trie, you don't need to do it before iterating through each word read from the dictionary! So getting a rid of

newptr = malloc(sizeof(node));
memset(newptr, 0, sizeof(node));

will help you to fix the last one or two errors remaining and stop leaking memory once for all.

I really hope this thread and my answer (I've tried to explain what I've understood) will help somebody, pset5 is in my opinion the second most difficult pset in CS50, right after resize from hacker4!

Good luck :)

3
  • Actually, setting the memory to NULL has nothing to do with memory leaks. The reddit post you mentioned is not about memory leaks, but about uninitialized variables. Also, i'm not too sure about the efficiency of malloc+memset. It seems to be slower than calloc, for example: stackoverflow.com/questions/2688466/… With respect to newptr: The problem is that there's no reason to malloc a pointer you will only use to traverse the trie. If you malloc it, you assign a separate block of memory, when what you need is for it to point to root :)
    – Irene
    Nov 25 '15 at 20:39
  • @Irene According to many posts I've read here and to the few I've linked in my question, not setting the nodes to NULL is the reason of the massive leak. The reddit post I've linked is also about Conditional jump or move depends on uninitialised value(s), just as my problem was. Replacing malloc() + memset() by calloc() works too but it's less efficient (0.22 seconds vs 0.37 with calloc() method). Anyway, I'm sure there's still a ton to say about my answer as it's incomplete but at the end of the day, it fixes everything and makes the program runs super fast! Thanks for your help Irene.
    – DFATPUNK
    Nov 27 '15 at 8:53
  • The Reddit post is not "also" about "conditional jump or move...", it's exclusively about it. That has nothing to do with memory leaks. Not initializing your pointers is just as bad as not initializing any variables, and Valgrind will tell you that it's an error, because it is. But that's not a memory leak. The memory leak (if there was one reported, you don't really say) would be because of mallocing to newptr initially). Actually, you never mentioned a "massive leak" but a massive amount of errors. Two very different things :)
    – Irene
    Nov 28 '15 at 0:29

You must log in to answer this question.

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