CS50 PSET5 Trie Segmentation Fault

Question

When I try to use speller.c with the large dictionary and the text 'hi', it says it could not load/open. When I use a large dictionary, it occasionally gives me a segmentation fault. Valgrind says:

==2378== 
==2378== HEAP SUMMARY:

==2378==     in use at exit: 1,240 bytes in 4 blocks
==2378==   total heap usage: 5 allocs, 1 frees, 1,808 bytes allocated

==2378== 
==2378== 224 bytes in 1 blocks are definitely lost in loss record 1 of 4
==2378==    at 0x4C2AB80: malloc (in 

/usr/lib/valgrind/vgpreload_memcheck-amd64-linux.so)

==2378==    by 0x401250: load (dictionary.c:105)
==2378==    by 0x40095D: main (speller.c:45)
==2378== 
==2378== 224 bytes in 1 blocks are definitely lost in loss record 2 of 4
==2378==    at 0x4C2AB80: malloc (in 
/usr/lib/valgrind/vgpreload_memcheck-amd64-linux.so)

==2378==    by 0x401295: load (dictionary.c:114)

==2378==    by 0x40095D: main (speller.c:45)
==2378== 

==2378== 224 bytes in 1 blocks are definitely lost in loss record 3 of 4
==2378==    at 0x4C2CC70: calloc (in /usr/lib/valgrind/vgpreload_memcheck-amd64-linux.so)

==2378==    by 0x40134A: load (dictionary.c:135)
==2378==    by 0x40095D: main (speller.c:45)
==2378== 
==2378== LEAK SUMMARY:

==2378==    definitely lost: 672 bytes in 3 blocks

==2378==    indirectly lost: 0 bytes in 0 blocks

==2378==      possibly lost: 0 bytes in 0 blocks

==2378==    still reachable: 568 bytes in 1 blocks

==2378==         suppressed: 0 bytes in 0 blocks

==2378== Reachable blocks (those to which a pointer was found) are not shown.

==2378== To see them, rerun with: --leak-check=full --show-leak-kinds=all

==2378== 
==2378== For counts of detected and suppressed errors, rerun with: -v

==2378== ERROR SUMMARY: 3 errors from 3 contexts (suppressed: 0 from 0)

My code lists every word as misspelled. When I try to free the memory, none of the loss bytes are retrieved. Here is my code:

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

    node;

    /**

    * Returns true if word is in dictionary else false.

    */

bool check(const char* word)
{
// declare trav and root nodes and assign all pointers in root/trav to NULL
node* root = calloc(1, sizeof(node));
node* trav = root;

// declare string length
int wordLength = strlen(word);

   for (int letter = 0; letter < wordLength; letter++)

   {

    int ind;

    // set into ASCI if apostrophe

    if (word[letter] == '\'')
    {
        // set index for easy math
        ind = 26;
    }
    else
    {
        // set into ASCI into index variable for easy math/keeping
        ind = tolower(word[letter]);
        ind = ind - 'a';
    }

    // check if letter is NULL i.e. word is mispelled
    if (trav->children[ind] == NULL)
    {
        // if so, return false
        return false;
    }
    // if not at last letter, move to next node
    else if (letter != wordLength - 1)
    {
        trav = trav->children[ind];
    }
    // if at end of word, return is_word
    else if (letter == wordLength - 1)
    {
        return trav->is_word;
    }

}

return false;
}

/**
 * Loads dictionary into memory.  Returns true if successful else      false.
 */
bool load(const char* dictionary)
{
//set wordCount
int wordCount = 0;

// open dictionary
FILE* dic = fopen(dictionary, "r");

// check to make sure all is good
if (dic == NULL)
{
    printf("Could not open dictionary.\n");
    return false;
}

// alert user that all is good
// printf("Successfully opened dictionary!!!\n");

// declare root node
node* root = malloc(sizeof(node));

// assign NULL to all root -> children pointers
for (int num = 0; num < 27; num++)
{
    root->children[num] = NULL;
}

// declare trav node
node* trav = malloc(sizeof(node));
trav = root;

// assign NULL to all trav -> children pointers
for (int ind = 0; ind < 27; ind++)
{
    trav->children[ind] = NULL;
}

// iterate over every letter in trie
for (char c = fgetc(dic); c != EOF; c = fgetc(dic))
{
    int l = tolower(c);

    // check for all letters
    if (l != '\'' && l != '\n')
    {
        // check if letter is NULL, like Z.C. recommended in walkthrough
        if (trav->children[l - 'a'] == NULL)
        {
            // malloc new node and make it into ASCI
            trav->children[l - 'a'] = calloc(1, sizeof(node));
            trav->children[l - 'a'] = NULL;
        }

            // move to next node
            trav = trav->children[l - 'a'];

    }

    // check for end of word
    if (l == '\n')
    {
        // increase wordCount size for size function
        wordCount++;
        // return true for true (pretty straight-forward)
        return true;
    }
}

// close dictionary
fclose(dic);

return false;
}

Thank you in advance!

UPDATE Here is my updated code:

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

// declare root & trav
node* root;
node* trav;

// initialize wordCount
int wordCount;

/**
 * Returns true if word is in dictionary else false.
 */
bool check(const char* word)
{
// declare trav and root nodes and assign all pointers in root/trav to NULL
// root = calloc(1, sizeof(node));
trav = root;

// declare string length
int wordLength = strlen(word);

for (int letter = 0; letter < wordLength; letter++)
{
    int ind;
    // set into ASCI if apostrophe
    if (word[letter] == '\'')
    {
        // set index for easy math
        ind = 26;
    }
    else
    {
        // set into ASCI into index variable for easy math/keeping
        ind = tolower(word[letter]);
        ind = ind - 'a';
    }

    // check if letter is NULL i.e. word is mispelled
    if (trav->children[ind] == NULL)
    {
        // if so, return false
        return false;
    }
    // if not at last letter, move to next node
    else if (letter != wordLength - 1)
    {
        trav = trav->children[ind];
    }
    // if at end of word, return is_word
    else if (letter == wordLength - 1)
    {
        return trav->is_word;
    }

}

return false;
}

/**
 * Loads dictionary into memory.  Returns true if successful else false.
 */
bool load(const char* dictionary)
{
//set wordCount
wordCount = 0;

// open dictionary
FILE* dic = fopen(dictionary, "r");

// check to make sure all is good
if (dic == NULL)
{
    printf("Could not open dictionary.\n");
    return false;
}

// alert user that all is good
// printf("Successfully opened dictionary!!!\n");

// declare root node
root = calloc(1, sizeof(node));

// assign NULL to all root -> children pointers
for (int num = 0; num < 27; num++)
{
    root->children[num] = NULL;
}

// declare trav node
trav = calloc(1, sizeof(node));
trav = root;

// assign NULL to all trav -> children pointers
for (int ind = 0; ind < 27; ind++)
{
    trav->children[ind] = NULL;
}

// iterate over every letter in trie
for (char c = fgetc(dic); c != EOF; c = fgetc(dic))
{
    int l = tolower(c);

    // check for all letters
    if (l != '\'' && l != '\n')
    {
        // check if letter is NULL, like Z.C. recommended in walkthrough
        if (trav->children[l - 'a'] == NULL)
        {
            // calloc new node and make it into ASCI
            trav->children[l - 'a'] = calloc(1, sizeof(node));
            trav->children[l - 'a'] = NULL;
        }

            // move to next node
            trav = trav->children[l - 'a'];

    }

    // check for end of word
    if (l == '\n')
    {
        // increase wordCount size for size function
        wordCount++;
        // return true for true (pretty straight-forward)
        return true;
    }
}

// close dictionary
fclose(dic);

return false;
}

Answer 1

As noted in the comments, root is not declared globally. It is declared as a local var in both load and check. By declaring it locally in load, the local var root is destroyed when load ends. That means that the trie is lost when load is finished. The memory that was calloc'd still exists, but there is no pointer to it. This needs to be fixed before any further diagnosis.

To be a global var, the var must be declared outside of main and outside of any other function. If declared inside of a function, or main, it is local to that function or main and will be deleted when that function finishes executing. Also, if declared in main, it is only available to main, not to any functions. Also, if you have separate declarations of the same variable name in two different functions, like root in both load and check, they are actually two different variables, with no relation to each other. Each is local to it's own function.

Also, remember that while it must be declared outside of all functions, only simple assignments to initialize it can be done outside of a function. The assignment has to be something that can be done at compile time, not at execution time, such as setting it to NULL, or setting an int to a number. It cannot be a calculation or a calloc in a global declaration. These kinds of assignments have to wait and be done inside main or a function.

You would probably benefit from a review of the class material on this pset, as well as a google search of "global variables in c"

[EDIT - following updated code posting]

Oh boy, there's a lot to be done with load().

Early on, trav is set with a call to calloc. On the next line, trav is set to point at root. Because of that, the memory just allocated is lost. That is called a memory leak.

Soon after, the code runs a for loop to initialize the pointers to NULL. This is dead code (called dead code because it is code that serves no purpose). It's dead because it repeats exactly what was just done in the previous loop. Remember, by assigning trav = root;, both var pointers now point at the same physical memory.

Now, study these two lines:

        trav->children[l - 'a'] = calloc(1, sizeof(node));
        trav->children[l - 'a'] = NULL;            

The first line allocates memory (correctly), but then the code immediately resets that pointer to NULL, abandoning that memory. Another memory leak. Worse, the node that needed to be created doesn't exist, creating a nasty problem. There's no node for that letter and nowhere to go in the trie to the next letter.

Later, when the code gets to the end of a word, it will return true; Unfortunately, this return terminates the load function, so load will never load more than one word into the trie.

Also, is_word is never set in load, so even if it didn't terminate after one word, there would never be an indicator of a word in the trie.

Finally, the last line is return false;. If the dictionary were to ever complete successfully, this tells main() that it failed and will generate an error.

As for check(), it appears OK at a cursory glance, but until load() is fixed, I'm not inclined to do a deep dive. I'm sure you'll find out when you test. If there are problems there, it'll make for a good new question.

There may be other issues with your code, or you may introduce new problems when you revise it. Either way, there's a lot of work to be done. Again, if you get stuck, a new question would be in order, given the number of issues already covered here. Happy coding! ;-)

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