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

node* root;
bool freenode(node* crawler);
bool is_word;
int words;

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

    int pos = 0;

    for (int i = 0; i < strlen(word); i++)
    {
        int c = word[i];

        if (c == '\'')
        {
            pos = 26;
        }
        else
        {
            c = tolower(c);
            pos = (c - 97);
        }

        crawler = crawler -> children[pos];

        if (crawler -> children[pos] == NULL)
        {
            return false;
        }

        if (i == strlen(word) - 1)
        {
            return crawler -> is_word;
        }
    }
    free (crawler);
    return false;
}

/**
 * Loads dictionary into memory.  Returns true if successful else false.
 */
bool load(const char* dictionary)
{
    FILE* infile = fopen(dictionary, "r");
    if (infile == NULL)
    {
        return false;
        fclose(infile);
    }

    root = calloc(1, sizeof(node));
    node* new_node = root;

    if(root == NULL)
    {
         return 1;
    }

    for(int i = 0; i < 27; i++)
    {
        root -> children[i] = NULL;
        root -> is_word = false;
    }

    {
        int count = 0;
        words = 0;

        for (int c = fgetc(infile); c != EOF; c = fgetc(infile))
        {
            if (c == '\n')
            {
                count++;
            }
            if (isalpha(c))
            {
                c = (c - 97);

                if (new_node -> children[c] == NULL)
                {
                    new_node -> children[c] = calloc(1, sizeof(node));
                    new_node = new_node -> children[c];
                }
                else
                {
                    new_node = new_node -> children[c];
                }
            } 
            else if (c == '\'')
            {
                c = 26;

                if (new_node -> children[c] == NULL)
                {
                    new_node -> children[c] = calloc(1, sizeof(node));
                    new_node = new_node -> children[c];
                }
                else
                {
                    new_node = new_node -> children[c];
                }
            }

            if (count > 0)
            {
                new_node -> is_word = true;
                new_node = root;
                words++;
                count = 0;
            }
        }
    }
    free(new_node);
    fclose(infile);
    return true;
}

I keep rewriting my check function. At some point, my code passed Check50 except for possessives. Now, it will compile, but not pass any of the Check50 tests. I have been working on Pset5 on and off since October and it is driving me nuts! When I run it using a long text, I get a Seg Fault as it is listing the misspelled words. When I run it using texts/ralph.txt I get:

MISSPELLED WORDS

When
grow
want
a
principal
a
caterpillar
love
you
Principal
Skinner
Ralph
Wiggum

WORDS MISSPELLED:     13
WORDS IN DICTIONARY:  143091
WORDS IN TEXT:        20
TIME IN load:         0.10
TIME IN check:        0.00
TIME IN size:         0.00
TIME IN unload:       0.00
TIME IN TOTAL:        0.10

I know that there should be only 1 misspelled word. Can someone please point me in the right direction?

1 Answer 1

0

Multiple places for possible segfaults.

In check:

You dereference crawler without knowing whether it's valid, or maybe NULL:

        crawler = crawler -> children[pos];

and again

        if (crawler -> children[pos] == NULL)

and again

            return crawler -> is_word;

You free a node, while check should not change the dictionary:

free (crawler);

(leaves invalid pointers, which lead to segfaults)

In load:

Similar thing, you free a node that's meant to stay

    free(new_node);
3
  • Not really sure what you mean by making sure a pointer is valid or NULL before dereferencing. How would you do this, by placing an a conditional statement before each dereferencing line such as: while (crawler != NULL) or similar? Jan 21, 2017 at 2:32
  • Thanks for the info on freeing the nodes prematurely. I suspected as much when I ran valgrind. Jan 21, 2017 at 2:50
  • I finally figured out my problem. Jan 22, 2017 at 21:17

You must log in to answer this question.

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