0

Everything is working bar this issue - program compiles, passes check50 and gives the correct output. However, when I run valgrind while checking a large text, e.g. tolstoy.txt, towards the end I get this error:

==2228== Invalid read of size 8
==2228==    at 0x40115B: check (dictionary.c:66)
==2228==    by 0x400CE7: main (speller.c:117)
==2228==  Address 0x89fbf80 is 32 bytes before an unallocated block of size 64 in arena "client"
==2228== 
==2228== Invalid read of size 8
==2228==    at 0x40117B: check (dictionary.c:74)
==2228==    by 0x400CE7: main (speller.c:117)
==2228==  Address 0x89fbf80 is 32 bytes before an unallocated block of size 64 in arena "client"
==2228== 

Note this is between lines 12693 and 12694 of the tolstoy key document.

The lines it points to are within my check function:

bool check(const char* word)
{
    // create a 'cursor' pointer
    node* current_node = root;
    int word_length = strlen(word);

    for(int i = 0; i <= word_length; i++)
        {
            // calculate index of letter or apostrophe in 'children' array
            int letter_index;

            if (word[i] == '\'')
            {
                letter_index = 26;
            }
            else
            {
                letter_index = tolower(word[i]) - 97;
            }

            if (i == word_length && current_node->is_word == true)
            {
                // word in dictionary
                return true;
            }

            else if (current_node->children[letter_index] == NULL)
            {
                // word not in dictionary
                return false;
            }
            else
            {
                // move to next node
               current_node = current_node->children[letter_index];
            }
        }
    // if previous checks fail must not be dictionary
    return false;
}

Specifically the following two lines:

else if (current_node->children[letter_index] == NULL)

current_node = current_node->children[letter_index];

I'm at a loss of what to do at this point. After a quick google it seems the problem is coming from reading an invalid pointer, as it is of size 8, and so this leads me to think something is wrong with the pointer in 'children[letter_index]'. I therefore checked my load function, but don't see any issues there.

Any advice would be greatly appreciated, as I'm so close now! If you need to see any other code, please ask and I'll gladly provide it. Thanks in advance :)

2
  • Ok I see a couple errors here but if they are the same in your load function that would explain it working. Remember arrays in C are zero indexed, meaning if a string is of size x as per x = strlen(string), the last element in the array is string[x -1] and not string[x]. In fact string[x] would point you to the NULL ( '\0' ) character which terminates the array. Like I said if you make the same mistake in the load function then it adds up, with the exception of words that are longer than the maximum allowed (45 I think), since you dont have space for the NULL char. I hope this helps you.
    – dLopez
    Aug 6 '16 at 15:41
  • @dLopez thanks for the advice. I have fixed the problem now (yay!) and although the issue wasn't exactly what you have described, you definitely pointed me (ha!) in the right direction. It turns out my logic and 'if' statements needed to be slightly adjusted. If you want to know more, go here: reddit.com/r/cs50/comments/4wfjzc/… Aug 6 '16 at 17:44
0

Turns out my logic was flawed, and my 'if' statements needed to be edited slightly. I had forgotten about one case specific case / path through my 'if' statements and that threw off valgrind.

Where I said this specifically:

if (i == word_length && current_node->is_word == true)
        {
            // word in dictionary
            return true;
        }

else if (current_node->children[letter_index] == NULL)
        {
            // word not in dictionary
            return false;

The logic behind the first 'if' statement meant that if i equalled word_length (meaning you are at the node that marks the end of the word), but is_word was false, the second if statement would be checked. The issue here is that letter_index can have values outside of the 0 - 26 range (if the current character is the string terminator for example) - meaning children[letter_index] can contain a junk pointer and hence the invalid read.

You must log in to answer this question.

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