0

I am working on Pset5 and have successfully load dictionary into a trie. ( I tested it by printing out the size of dictionary, it says 143091, exactly the same as in the guide.)

struction of trie contains

{ bool is_word;

struct node* children[27]; }

However, my code hit segmentation fault on first try of check function. I looked into it via Valgrind, it turned out there is a invalid read of size 8 in "if (checker->children[position] == NULL)"

I used the same way as loading dictionary, couldn't see why it kept getting seg fault.

Please give a hint.

Many thanks

Here is the part of my code:

// creat a pointer to track the beginning of trie
node* root;

// dictionary size counter
int dictionary_size = 0;

// to initialize new nodes
void initialize(node* pointer)
{
    pointer->is_word = false;
    for(int i = 0; i < 27; i++)
    {
        pointer->children[i] = NULL;
    }
}


// the Load function

bool load(const char* dictionary)
{
    // open the dictionary file.
    FILE* dt = fopen(dictionary, "r");
    if (dt == NULL)
    {
        printf("Could not open %s.\n", dictionary);
        return 1;
    }

    // creat a pointer at the start of tries to track loading.
    node* root = malloc(sizeof(node));
    initialize(root);
    node* builder = root;

    while (builder != NULL)
    {
        for (int ch = fgetc(dt); ch != EOF; ch = fgetc(dt))
        {
            if (isalpha(ch))
            {
                if (builder->children[ch - 'a'] == NULL)
                {
                    node* new_node = malloc(sizeof(node));
                    initialize(new_node);
                    builder->children[ch - 'a'] = new_node;
                }

                builder = builder->children[ch - 'a'];
            }

            else if ( ch == '\'' )
            {
                if(builder->children[26] == NULL)
                {
                    node* new_node = malloc(sizeof(node));
                    initialize(new_node);
                    builder->children[26] = new_node;
                }

                builder = builder->children[26];
            }

            // when hit \0
            else
            {
                builder->is_word = true;
                dictionary_size = dictionary_size + 1;

                // reset the pointer to the root, preparing for a new word
                builder = root;
            }
        }

        // hit EOF, close dictionary
        fclose(dt);
        return true;
    }

    return false;
}


// the check function

bool check(const char* word)
{
    node* checker = root;
    // check spelling char by char
    for (int j = 0; j < LENGTH + 1; j++)
    {
        if (isalpha(word[j]))
        {
            int position = (tolower(word[j]) - 'a');
            printf("position:%i\n", position); //for test only.
            if (checker->children[position] == NULL) //HERE COMES the INVALID READ
            {
                return false;
            }

            else 
            {
                checker = checker->children[position];
            }
        }

        else if (word[j] == '\'')
        {
            if (checker->children[26] == NULL)
            {
                return false;
            }

            else
            {
                checker = checker->children[26];
            }
        }

        // when hit \0
        else if (word[j] == '\0')
        {
            if (checker->is_word == true)
            {
                return true;
            }

            else
            {
                return false;
            }
        }
    }
    return false;
}
1

If the seg fault you described is occurring on the line if (checker->children[position] == NULL) it's almost certain that checker itself is NULL or contains garbage data (was it properly initialized?), and the struct components don't exist. Without seeing the code that initialized and declared root, or the load function, it's impossible to know more.

You could temporarily put an if statement in the code to test this.

[EDIT: following updated code]

I was right, checker is null. In fact, every pointer in root is null. The problem is that you created a shadow of root by re-declaring root inside of load(). When root was redeclared as a local variable, it takes precedence locally and supersedes the global variable root, effectively hiding it. As long as the shadow variable is in scope, the original root remains untouched. All of the actions on root inside of load() are on the local variable. When load() exits, the local shadow variable root is destroyed, losing all pointers to the trie. The global root comes back into focus and is then used by check, but since it has not been initialized, it contains garbage pointers, not null and not valid pointers. This leads to a seg fault as soon as the code tries to access any pointers in root.

Don't re-declare root in load()!

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

1
  • Before the check function, I have loaded the dictionary and have the node* root pointing to the beginning of the trie and never move root. The pointer checker just starts from where the root, how can it be NULL? I edited my question to include more parts of my code, please give me some direction. thanks – user13479 Sep 9 '16 at 1:57

You must log in to answer this question.

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