Program runs fine with small dictionary, seg faults with the large dictionary

Question

I have decided to use trie to implement load in speller and it works fine with the small dictionary (~14 words), however it seg faults with the large dictionary. Using valgrind, it says:

Invalid read of size 8

at 0x4012A0: load (dictionary.c:77)

by 0x400874: main (speller.c:40)

Address 0x51fdef8 is not stack'd, malloc'd or (recently) free'd

I have a hard time understanding the problem or even how to fix it. Any help would be great Here's my implementation for load:

bool load(const char *dictionary)
{
// TODO
root = calloc(1, sizeof(trie));
if (root == NULL)
{
    printf("ERROR.\n");
    return false;
}

trie *trav = root;

FILE *dict = fopen(dictionary, "r");
if (dict == NULL)
    return false;

for(int c = fgetc(dict); c != EOF; c = fgetc(dict))
{
    if(c != '\'' && c != '\n' && trav->letters[c%97] == NULL)
    {
        trav->letters[c % 97] = calloc(1, sizeof(trie));
        trav = trav->letters[c % 97];
    }

    if(trav->letters[c % 97] != NULL)
        trav = trav->letters[c % 97];

    if (c == '\'')
    {
        trav->letters[26] = calloc(1, sizeof(trie));
        trav = trav->letters[26];
    }

    if(c == '\n')
    {
        trav->isWord = true;
        words++;
        trav = root;
    }
}

fclose(dict);
return true;

}

Answer 1

Interesting issue. The problem is tied to the processing of apostrophes and memory allocation. It seems that, in the for loop, the second if statement is tripping on an apostrophe, but not the first one. It's more like several hundred apostrophes are processed before it seg faults. I haven't worked out precisely why, so if anyone tracks down the exact reason, feel free to chime in.

Having said that, I can identify the exact problem. The second if statement,

if(trav->letters[c % 97] != NULL)

is trying to test apostrophes (and line feeds, I'm sure). The problem is closely tied to trying to find trav->letters[c % 97], which works out to trav->letters[39]. Clearly, this is a problem. It can be easily fixed by using the same conditions used in the first if statement, as follows:

if(c != '\'' && c != '\n' && trav->letters[c%97] != NULL)

This cures this issue. You could also instead use isalpha() as a more reliable and comprehensive test, combined with the null checks.

The part that I haven't figured out is why it takes (in my testing) about 674 apostrophes successfully processed before it fails with a segfault. I would expect it to fail sooner, but apparently, it's not going outside of memory bounds until then. (Sometimes, bad addresses are actually valid in the allocated memory.)

Given that I've tracked down the error, I'll leave it to you to figure out the exact mechanism of failure, if you wish. You can enjoy spending more time on it. ;-)

If this answers your question, please click on the check mark to accept. Let's keep up on forum maintenance. ;-)