Cs50 Speller Uninitialised value was created by a heap allocation error

Question

I have some code that is supposed to take a dictionary file, read each word and add it to trie data structure setting a bool to true on the final node of the word.

It runs but when i check words against the dictionary later in the check() function it was always saying false.

Valgrind is throwing this error;

    ==20700== 
    ==20700== Conditional jump or move depends on uninitialised value(s)
    ==20700==    at 0x40116F: load (dictionary.c:114)
    ==20700==    by 0x400834: main (speller.c:40)
    ==20700==  Uninitialised value was created by a heap allocation
    ==20700==    at 0x4C2FB0F: malloc (in /usr/lib/valgrind/vgpreload_memcheck-amd64-linux.so)
    ==20700==    by 0x401180: load (dictionary.c:116)
    ==20700==    by 0x400834: main (speller.c:40)
    ==20700== 
    Killed

I had a look around and added the loops that itterate through children[] and initialise to NULL after creating a new node, but still seem to have the issue.

// Represents a node in a trie
typedef struct node
{
    bool is_word;
    struct node *children[N];
}
node;

// Represents a trie
node *root;

// Loads dictionary into memory, returning true if successful else false
bool load(const char *dictionary)
{
    // Initialize trie
    root = malloc(sizeof(node));
    if (root == NULL)
    {
        return false;
    }
    root->is_word = false;
    for (int i = 0; i < N; i++)
    {
        root->children[i] = NULL;
    }

    // Open dictionary
    FILE *file = fopen(dictionary, "r");
    if (file == NULL)
    {
        unload();
        return false;
    }

    //declare pointer to store adress of current node
    node *ptr = root;

    // Buffer for a word
    char word[LENGTH + 1];

    for (int i = 0; i < LENGTH + 1; i++)
        {
            word[i] = 0;
        }

    int size = 0;

    // Insert words into trie
    while (fscanf(file, "%s", word) != EOF)
    {

        // make pointer to current place in trie structure and intitialise to root
        ptr = root;

        // make variable to store chaacter as int representing position in alphabet
        int alphaindex;

        // iterate over letters in word
        for (int i =0; i < LENGTH; i++)
        {



            // if word i == to ' character check ptr children and make new node if necesary
            if ((int)&word[i] == '\'')
            {
                alphaindex = 26;
                if (ptr-> children[alphaindex] == NULL)
                {
                    node *n = malloc(sizeof(node));

                    if (n == NULL)
                    {
                        return 1;
                    }

                    root->is_word = false;

                    for (int j = 0; j < N; j++)
                    {
                        root->children[j] = NULL;
                    }


                    // set 27th element of children to new node
                    ptr -> children[alphaindex] = n;
                }

                // set ptr to ptr[26]

                ptr = ptr -> children[alphaindex];

            }

            else
            {

                // adjust alphainex
                alphaindex = islower((int) word[i]) ? (int) word[i] - 97 : (int) word[i] - 65;

                //check location for NULL and make new index if necessary
                if (ptr -> children[alphaindex] == NULL)
                {
                    node *n = malloc(sizeof(node));

                    if (n == NULL)
                    {
                        return 1;
                    }

                    root->is_word = false;

                    for (int k = 0; k < N; k++)
                    {
                        root->children[k] = NULL;
                    }

                    // set children[alphaindex] to new node
                    ptr -> children[alphaindex] = n;

                    //set ptr to new alphaindex element of array which its self points to the new node
                    ptr = ptr -> children[alphaindex];
                }

                else
                {

                //set ptr to new alphaindex element of array which its self points to the new node
                ptr = ptr -> children[alphaindex];

                }


            }



            // if the character is 0 word is over, set is_word and return to while loop
            if((char) word[i + 1] == 0)
            {
                ptr -> is_word = true;
                size ++;
                break;
            }



        }



    }

    printf("Size of dictionary = %i\n", size);

    // Close dictionary
    fclose(file);

    // Indicate success
    return true;
}

Im fairly sure that as the conditional with this error is where I evaluate weather or not to make a new node that this will be causing the errors when i try to test words against it later.

Thanks in advance for your help

Alex

That doesn't seem likely, as no variables are read there so there can't be access of an uninitialized value. Please post a minimal reproducible example. — interjay
im sorry that was 116 i gave you, 114 is the if statement above that checks for NULL — Rusty
That line numbering is not consistent with the valgrind output either, and I don't see a matching pattern anywhere in that code. That leaves me inclined to suspect that the source presented does not correspond to the binary that was tested. Perhaps you need to rebuild the binary against the current sources? — John Bollinger

DinoCoderSaurus DinoCoderSaurus · Accepted Answer · 2019-12-31T13:42:30

Several immediate problems:

If word contains an apostrophe, all pointers in root are set to NULL here:

for (int j = 0; j < N; j++)
                    {
                        root->children[j] = NULL;
                    }

Typo? That will make them "unfreeable" (not to mention, check will never find them).

Same problem in the else branch:

for (int k = 0; k < N; k++)
                    {
                        root->children[k] = NULL;
                    }

The apostrophe check needs to be discrete. It also looks like program doesn't "save" enough pointers, but you won't be able to work through that until these big structural problems are corrected.

Cs50 Speller Uninitialised value was created by a heap allocation error

1 Answers