1

My speller program functions fine, but when I run it in valgrind, I get a lot of messages saying Conditional jump or move depends on uninitialised value(s). Looking into this a little, I think this is because I am using a trie structure to store the words from the dictionary, and when I am navigating the trie (for example, to populate it), I use an if loop like this (my children array is called letters):

if(current_node->letters[letter]==NULL)
    current_node->letters[letter] = malloc(sizeof(node));

So I think what's happening is that the computer reaches the if loop, and is asked about the value of the as-yet uninitialized letter. I didn't think this should be a problem (and indeed, it runs just fine), but the fact that valgrind prints out a warning makes me think perhaps it's not good. If so, how else would I go about asking the computer whether a certain child node is populated yet. Is there a way to initialize them automatically with NULL (isn't that what happens anyway)?


Note: here's my trie type definition, if that's useful:

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

And, additionally, I am still tracking down two node's worth of memory (224 bytes: 112 direct, 112 indirect) that is leaked in malloc'ing a node at some point, if that might have something to do with it.

1
  • @Kareem: I have the same issue, but with strlen and strcasecmp. I am using a Hashtable to make my speller, so I can't initialize my array to NULL. Do I need to run a loop to initialize my char word [46] array? I have no leaks and my speller gives the correct output, but check50 gives errors on every check. – Erin Magner Dec 28 '14 at 16:19
4

You're totally correct. You have to initialize variables before asking for their values.

Since a trie is an array of arrays, the root array can be initialized when declared like that

node *root[26] = {NULL};

This way of initializing an array basically tells the compiler to initialize the first element in root (i.e., root[0]) to NULL and all the other elements to 0 which is also NULL since NULL is the zeroth memory location (i.e., address 0x0).

Unfortunately, initializing an array with an initialization list isn't allowed unless you're initializing the array in the same statement as you're declaring it. Therefore, when creating a new node, an easy way to initialize the elements of the member named letters is probably using a simple for loop as follows

root[0] = malloc(sizeof(node));
for (int i = 0; i < 27; i++)
    root[0]->letters[i] = NULL;

About the leaking part, valgrind gives exact information about the line number by which the leaking is caused. Just make sure you're compiling with the -ggdb3 option and passing the option --leak-check=full when running valgrind on your program.

6
  • I am doing it slightly differently, using a node structure as the root (for consistency), instead of an array, so I can't quite do the first part. But setting the letters array to be full of NULLs every time I make a new node has solved the uninitialized value problem. Thank you. – postylem Sep 21 '14 at 10:01
  • However, I still have an issue with the 2 nodes that are allocated but not freed. I am using --leak-check=full, but knowing the line number isn't much help because it is happening in the loop, and I don't know when (the loop runs for every letter of every word). – postylem Sep 21 '14 at 10:04
  • The leak only happens when I have a long dictionary file (like more than 70000 words), which is perplexing to me, as I can't see how that would make a difference. – postylem Sep 21 '14 at 10:11
  • 2
    @postylem it's quite difficult to guess what causes this problem without seeing how you're allocating/freeing memory. You may update your question or send me the source code at kareem.mes@gmail.com! – Kareem Sep 21 '14 at 11:06
  • 1
    I found where my leak was. It had to do with incorrectly dealing with apostrophes (I subtracted 97 from tolower'd char which led to negative values, and therefore writing outside of the letters array—apparently this only became a problem with large dictionaries, but that was just chance). – postylem Sep 21 '14 at 11:59

You must log in to answer this question.

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