PSET5: problems with load?

Question

So I'm not getting load to work properly in PSET5. Any tips on what I'm doing wrong?

My method now:

1. Scan char by char in file until EOF; increment index (global)
2. Insert each item into the trie from the root (global) -> this also updates the pointer so the next character in the loop starts from that pointer
3. Continuing will insert at the previous node recursively (I think).
4. When you reach end of word, return the trie pointer to head and set index to 0;

Here's what that looks like FYI what most people call 'nodes' I've labled as 'trie' (struct with bool isWord and trie* children[27] (edit - mistyped here. it should be 27 because of the '\'' character slot):

    trie* wordPtr = head;
for (int c = fgetc(fp); c != EOF; c = fgetc(fp))
    {
        if (isalpha(c) || (c == '\'' && index > 0))
        {
            wordPtr = insert(c, wordPtr);
            index++;
        }

        else if (index > 0)
        {
           // update counter
            num_words++;
            endword(wordPtr);
            wordPtr = head;
            index = 0;
        }
    }

I've searched the forums and this 'insert' method seems to be pretty standard, but here's the code for it:

trie* insert(char c, trie* ptr)
{
    if (c == '\'' && ptr->children[26] == 0)
    {
        ptr->children[26] = calloc(1, sizeof(trie));
        return ptr->children[26];
    }
    else if (c == '\'' && ptr->children[26] != 0)
    {
        return ptr->children[26];
    }
    if (ptr->children[c -'a'] == 0)
    {
        ptr->children[c - 'a'] = calloc(1, sizeof(trie));
        return ptr->children[c - 'a'];
    }
    else
    {
        return ptr->children[c - 'a'];
    }
}

endword indeed just sets the ptr->isWord to true.

Any idea what I'm doing wrong? Can I update wordPtr in the way that I've done it (passing it to the a function and updating it on when that function returns)?

Thanks!

Answer 1

You can skip until the QUICK ANSWER at the end.

I was running your program with gdb. Before I tell you what I found I would like to ask you, what is endword()?

I assumed it is something like this:

void endword(trie* ptr){
     ptr->isWord = true;    
}

I found two things that could be causing problems:

1.- I think you mean 25 everywhere you have 26 in the insert function. Since you can only access up to the 25th index (starting with the 0th index) of an array of 26 elements.

2.- I tracked a Segmentation fault running your program like this:

./speller texts/austinpowers.txt

If I run it with gdb I see it failing at line:

if (ptr->children[c -'a'] == 0)

This is because the first word in the large dictionary is "a". Before any words are loaded the head pointer is NULL.

wordPtr becomes a copy of head here:

trie* wordPtr = head;

and ptr becomes a copy of wordPtr when you pass it as an argument:

wordPtr = insert(c, wordPtr);

and then it gets stored in ptr in the first line of the function:

trie* insert(char c, trie* ptr)

So the value of ptr on the first word on the first letter to be loaded is NULL. And then we have this line (since the first letter is not a single quote):

if (ptr->children[c -'a'] == 0)

The problem with this line is that you are trying to access the array children contained in the struct that ptr is pointing to. But at the first letter of the first word ptr is not pointing to anything yet.

QUICK ANSWER

I suggest these changes to you:

Change 26 by 25 everywhere in your insert function.

Add this line:

head = calloc(1, sizeof(trie)); 

before this one:

trie* wordPtr = head;

So you have a trie to start messing with.

UPDATE AFTER LOOKING AT WHOLE CODE

I noticed that your load function always returns false at the end.

SECOND UPDATE

There is this piece of code on speller.c:

bool loaded = load(dictionary);

// some lines in between.

// abort if dictionary not loaded
if (!loaded)
{
    printf("Could not load %s.\n", dictionary);
    return 1;
}

So, I think load() needs to return true in case of success.