segmentation fault in speller, but gbd exits with status 0?

Question

I'm getting a segmentation fault. It came up when I added check() into dictionary.c (been writing mini programs to test my functions in isolation whenever possible), but decided to continue and fight my way thru size() and unload().

Segmentation fault happens after MISSPELLED WORDS, line 46 of speller. I stepped thru the code with gbd expecting to find where it occurs. I've learned my check function isn't working properly as it adds "caterpillar" to the list of misspelled words when checking ralph.txt using the small dictionary, but the real surprise was the code executed thru the end of speller.

My code is here for reference:

/**
 * Implements a dictionary's functionality.
 */

#include <stdbool.h>
#include <ctype.h>
#include <stdlib.h>
#include <stdio.h>

#include "dictionary.h"

/**
 * Returns true if word is in dictionary else false.
 */

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

// ptr to begining of trie
node *root = NULL;
node *trav = NULL;

int words_howmany = 0;

// stores alphabetic index of value returned from alpha
int ind_abc = 0;

/**
* 'alpha' calculates alphabetical index of ascii value
*/
int alpha(char *c)
{
    // for all chars which aren't an apostrophe
    if (*c != '\'')
    {
        tolower(*c);
        *c = (*c - 'a');
    }

    // set alphabetic index of apostrophe to 26
    else if (*c == '\'')
    {
        *c = 26;
    }

    return *c;
}

/**
 * Returns true if word is in dictionary else false.
 */   
bool check(const char *word)
{
    trav = root;

    // for each letter in input word
    for (int ind = 0; word[ind]!= '\0'; ind++)
    {
        // dereference word[ind] to get char
        char letter = word[ind];

        // get alphabetical index for *word[ind]
        ind_abc = alpha(&letter);

        // if NULL, word is misspelled
        if (trav->branch[ind_abc] == NULL)
        {
            return false;
        }

        // move to next letter in trie
        else
        {
            trav = trav->branch[ind_abc];
        }
    }

    return trav->is_word;
}

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

    // checks if ptr return is null, quits if is
    if (root == NULL)
    {
        return 1;
    }

    trav = root;

    // opens dictionary file for reading
    FILE *fp_dictionary = fopen(dictionary, "r");

    // checks if ptr returned is null, quits if is
    if (fp_dictionary == NULL)
    {
        printf("Can't open dictionary\n");
        return 1;
    }

    // loop to read char from file one at a time
    for (char c = fgetc(fp_dictionary); c != EOF; c = fgetc(fp_dictionary))
    {
        // for chars which are not a new line
        if (c != '\n')
        {
            // calls alpha() to convert decimal to alphabetic index
            ind_abc = alpha(&c);

            // checks if root node's branch ptr at alpha index is NULL
            // 'root' is dynamically declared on the heap and therefore, uses -> to dereference
            if (trav->branch[ind_abc] == NULL)
            {
                // creates new node if ptr at index c is NULL
                trav->branch[ind_abc] = new_node();

                // quits if ptr returned for new_node is NULL
                if (trav->branch[ind_abc] == NULL)
                {
                    unload();
                    return false;
                }

                // advance in trie to be ready for next char
                trav = trav->branch[ind_abc];
            }

            else if (trav->branch[ind_abc] != NULL)
            {
                // move to existing node and continue
                trav = trav->branch[ind_abc];
            }
        }

        // if char is new line escape sequence
        else if (c == '\n')
        {
            // word end reached, sets node's bool to true
            trav->is_word = true;

            // word is in dictionary, count it
            words_howmany++;
        }
    }

    return true;
}

/**
 * Creates new node and initializes its members
 */
struct node *new_node(void)
{
    // mallocs memory for new node
    node *new_node = malloc(sizeof(node));

    // sets bool checking if word is in dictionary to false
    new_node->is_word = false;

    // set all ptrs in 'branch' to NULL because don't point to anything yet
    for (int i = 0; i < 27; i++)
    {
        new_node->branch[i] = NULL;
    }

    return new_node;
}

/**
 * recursively frees node in trie
 */
bool prune(struct node *trie_ptr)
{
    trav = root;

    for(int i = 0; i < 27; i++)
    {
        while(trav->branch[i] != NULL)
        {
            prune(trav->branch[i]);
        }

        free(trav->branch[i]);
        return true;
    }

    return false;
 }

/**
 * Returns number of words in dictionary if loaded else 0 if not yet loaded.
 */
unsigned int size(void)
{
    // returns number of words loaded into dictionary
    return words_howmany;
}

/**
 * Unloads dictionary from memory. Returns true if successful else false.
 */
bool unload(void)
{
    return prune(root);
}

I ran valgrind to try and find the seg fault:

==1152== Stack overflow in thread 1: can't grow stack to 0xffe801ff8
==1152== 
==1152== Process terminating with default action of signal 11 (SIGSEGV)
==1152==  Access not within mapped region at address 0xFFE801FF8
==1152==    at 0x401451: prune (dictionary.c:188)
==1152==  If you believe this happened as a result of a stack
==1152==  overflow in your program's main thread (unlikely but
==1152==  possible), you can try to increase the size of the
==1152==  main thread stack using the --main-stacksize= flag.
==1152==  The main thread stack size used in this run was 8388608.
==1152== Stack overflow in thread 1: can't grow stack to 0xffe801ff0
==1152== 
==1152== Process terminating with default action of signal 11 (SIGSEGV)
==1152==  Access not within mapped region at address 0xFFE801FF0
==1152==    at 0x4A256B0: _vgnU_freeres (in /usr/lib/valgrind/vgpreload_core-amd64-linux.so)
==1152==  If you believe this happened as a result of a stack
==1152==  overflow in your program's main thread (unlikely but
==1152==  possible), you can try to increase the size of the
==1152==  main thread stack using the --main-stacksize= flag.
==1152==  The main thread stack size used in this run was 8388608.
==1152== 
==1152== HEAP SUMMARY:
==1152==     in use at exit: 290,335,480 bytes in 1,296,139 blocks
==1152==   total heap usage: 1,296,140 allocs, 1 frees, 290,336,048 bytes allocated
==1152== 
==1152== LEAK SUMMARY:
==1152==    definitely lost: 0 bytes in 0 blocks
==1152==    indirectly lost: 0 bytes in 0 blocks
==1152==      possibly lost: 0 bytes in 0 blocks
==1152==    still reachable: 290,335,480 bytes in 1,296,139 blocks
==1152==         suppressed: 0 bytes in 0 blocks
==1152== Reachable blocks (those to which a pointer was found) are not shown.
==1152== To see them, rerun with: --leak-check=full --show-leak-kinds=all
==1152== 
==1152== For counts of detected and suppressed errors, rerun with: -v
==1152== ERROR SUMMARY: 0 errors from 0 contexts (suppressed: 0 from 0)

I can continue to work on why words in the dictionary are coming back as misspelled, but don't know how to continue to troubleshoot the seg fault when the debugger's making it to the end of the file, the exit code is 0, valgrind's results aren't meaningful to me, and help50 can't help.

Maybe valgrind's results indicate an infinite loop? But seg fault came up before size() and unload(). Can someone please advise? Many thanks.

I've appended an updated version of alpha() here in response to Blauelf's answer:

#include <stdio.h>
#include <ctype.h>
#include <stdlib.h>

int alpha(char *pc);
int ind_abc = 0;

int main(void)
{
    char c = '\'';

    printf("char before alpha is %i\n", c);
    ind_abc = alpha(&c);
    printf("char after alpha is %i\n", ind_abc);

    return 0;
}

// 'alpha' calculates alphabetical index of ascii value
// made the argument a ptr because want it passed by reference so value itself is changed
int alpha(char *pc)
{
    // stores alpha index of pc
    int pc_abc = 0;

    // pc stores the address of c
    // if the value where pc points to isn't an apostophe...
    if (*pc != '\'')
    {
        // make the value the ptr pc points lowercase
        pc_abc = (tolower(*pc)) - 'a';
    }

    else if (*pc == '\'')
    {
        pc_abc = 26;
    }

    return pc_abc;
}

Answer 1

In check, tolower(*c) does nothing. You have to assign the result. Also, why do you use a char* instead of a char?

In load, the else if (c == '\n') path lacks a final trav = root;, which has to happen before a new word, otherwise you get a trie for a really long word containing all the letters.

I see a few problems in prune.

One logical:

    trav = root;

Use trie_ptr instead of trav, and remove that line. No trav in this function, as traversal is done by recursion.

One critical:

        while(trav->branch[i] != NULL)
        {
            prune(trav->branch[i]);
        }

So what happens after calling prune(trav->branch[i]) once? trav->branch[i] won't change value. But its children will no longer point to allocated memory, but recently freed memory. Calling the function a second time will generate a segfault.

Use if, not while.

Memory leak:

        free(trav->branch[i]);

You'd only free children (conveniently free(NULL) won't crash), but never free the root node that's no-one's child. Place a free(trie_ptr) after your loop instead.

Memory leak:

        return true;

return leaves the function, so your loop will always end within the first iteration. What's the meaning of that anyway? Is there a way to fail unloading that does not result in a segfault?