0

I'm trying to implement a trie as my load function in pset5, but I have two questions:

  1. How did I fix the segfault I encounter? (identified specifically below)
  2. More broadly, where are the errors in my implementation of the trie?

I've tried to wrap my head around the setup of tries/pointers, but (obviously) I'm missing something logically and/or syntactically.

Here is what I declared in dictionary.h:

/**
* Declare struct and global variables for loading words into dictionary and counting total words
*/

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

node* root;

int words;

Here is what I have as my load function in dictionary.c:

/**
 * Loads dictionary into memory.  Returns true if successful else false.
 */
bool load(const char* dictionary)
{
    // declare root node
    root = calloc(1, sizeof(node));
    root->is_word = false;

    // declare traversal pointer
    struct node* pTrav = NULL;

    // open dictionary for reading
    FILE* dict = fopen(dictionary, "r");
    if (dict == NULL)
    {
        printf("Error loading dictionary");
        return false;
    }

    // begin reading dictionary
    while (true)
    {
        // set traversal point equal to root to begin a new word
        pTrav = root;

        // declare variable for moving through dictionary
        int c;

        while (true)
        {
            // get character from dictionary
            c = fgetc(dict);

            // if c is a new line, break loop
            if (c == '\n')
            {
                break;
            }

            // convert c to numeric value based on ascii value (or 26 for apostrophes)
            if (isalpha(c))
            {
                c = c - 'a';
            }
            else
            {
                c = 26;
            }

            // check the value at children[c]

            // if NULL, malloc a new node and have children[c] point to it
            if (pTrav->children[c] == NULL)
            {
                pTrav = calloc(1, sizeof(node));
                pTrav = pTrav->children[c];

            // if not NULL, move to new node and continue
            }
            else
            {
                pTrav = pTrav->children[c];
            }
        }

        // once loop has broken (and thus a word has been completed), set is_word to true and increase counter
        pTrav->is_word = true;
        words++;

        if (c == EOF)
        {
            break;
        }
    }

    // check whether there was an error
    if (ferror(dict))
    {
        fclose(dict);
        return false;
    }
    else
    {
        fclose(dict);
        return true;
    }

}

When I tried to debug it just now, I got a segfault at this line:

pTrav->is_word = true;
2
  • Perhaps you could walk your edit back and add the solution as an answer so that the question is removed from the unanswered question pool? Answering your own questions is highly valued, but the system usually requires 2 days after the question is posted to accept your own answer. – Cliff B Feb 4 '16 at 0:31
  • Done! Thanks for the tip. – Peter Feb 4 '16 at 0:36
1

ANSWERED MY OWN QUESTION! SUCCESS!

After clearing up a couple workflow issues and doing some drastic re-writing of my code, I fixed the errors!

The biggest issue came at this line:

pTrav = calloc(1, sizeof(node));

It really should have been:

pTrav->children[i] = calloc(1, sizeof(node));

I was getting ahead of myself with my assignment to pTrav, and in so doing destroyed the trie and prevented it from progressing.

I can't remember being as joyful figuring out a problem than when I saw this:

load and size complete!

You must log in to answer this question.

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