0

I finished the code for load() and check(). It seems to me that load() works fine. But when I finished check() and ran the program, segmentation fault appeared. Then I used Valgrind and here is one of the errors that I believe is the key problem:

==6829== Invalid read of size 8
==6829==    at 0x401252: check (dictionary.c:62)
==6829==    by 0x400CE7: main (speller.c:117)
==6829==  Address 0x80 is not stack'd, malloc'd or (recently) free'd

Then I went back to my code, especially at dictionary.c:62:

crawler = crawler->children[index];

I think there should not be any problems as I had already allocated memories to it and equaled it to root, which was defined globally. It would be very appreciated if anyone can point out my problem or give me some hints.

The followings are my dictionary.c and dictionary.h:

/**
 * dictionary.c
 *
 * Computer Science 50
 * Problem Set 5
 *
 * Implements a dictionary's functionality.
 */

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


#include "dictionary.h"

/**
 * Returns true if word is in dictionary else false.
 */
bool check(const char* word)
{
    trie* crawler = malloc(sizeof(trie));
    if(crawler == NULL)
    {
        printf("Cannot create crawler!\n");
        return 1;
    }
    crawler = root;

    int len = strlen(word);
    char neword[len+1];

    // Change all capital letters to lowercase
    for(int i = 0; i < len; i++)
    {
        if(isupper(word[i]))
        {
            neword[i] = tolower(word[i]);
        }
        else
        {
            neword[i] = word[i];
        }
    }
    neword[len] = '\0';

    for(int level = 0; neword[level] != '\0'; level++)
    {
        int index;

        if(isalpha(neword[level]))
        {
            index = neword[level] - 'a';
        }
        else
        {
            index = 26;
        }

        crawler = crawler->children[index];

        if(crawler == NULL)
        {
            return false;
        }
    }

    if(crawler->is_word == true)
    {
        return true;
    }
    else
    {
        return false;
    }
}

/**
 * Loads dictionary into memory.  Returns true if successful else false.
 */
bool load(const char* dictionary)
{
    // open the dictionary
    FILE* dict = fopen(dictionary, "r");
    if (dict == NULL)
    {
        printf("Cannot open the dictionary!");
        return false;
    }

    // create the root for the trie
    trie* root = calloc(1,sizeof(trie));

    // get words from dictionary
    char word[LENGTH+1];

    for (char* c = fgets(word, LENGTH+1, dict); c != NULL; c = fgets(word, LENGTH+1, dict))
    {
        // get word from the dictionary one by one
        for (int i = 0; i < LENGTH+1; i++)
        {
            if(word[i] == '\n')
            {
                word[i] = '\0';
                break;
            }
        }

        int len = strlen(c);
        trie* crawler = malloc(sizeof(trie));
        crawler = root;


        for (int level = 0; level < len; level++)
        {
            if(word[level] - 39 == 0)
            {
                if(crawler->children[26] == NULL)
                {
                    crawler->children[26] = malloc(sizeof(trie));
                    crawler = crawler->children[26];
                }
            }
            else if(crawler->children[word[level] - 97] == NULL)
            {
                crawler->children[word[level] - 97] = malloc(sizeof(trie));
                crawler = crawler->children[word[level] - 97];
            }
        }

        crawler->is_word = true;
        libword++;

    }

    fclose(dict);
    return true;
}


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

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

dictionary.h:

/**
 * dictionary.h
 *
 * Computer Science 50
 * Problem Set 5
 *
 * Declares a dictionary's functionality.
 */

#ifndef DICTIONARY_H
#define DICTIONARY_H

#include <stdbool.h>

// maximum length for a word
// (e.g., pneumonoultramicroscopicsilicovolcanoconiosis)
#define LENGTH 45

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

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

/**
 * Returns number of words in dictionary if loaded else 0 if not yet loaded.
 */
unsigned int size(void);

/**
 * Unloads dictionary from memory.  Returns true if successful else false.
 */
bool unload(void);

/**
 * Create the structure of node for the trie.
 */
typedef struct trie
{
    bool is_word;
    struct trie* children[27];
}trie;

/**
 * Define the root for later use
 */
trie* root;

/**
 * Create a global variable for tracking the number of vocalbulary loaded
 */
int libword;

#endif // DICTIONARY_H
0

The problem is that line. Once you start working down the tree, it does get to a point where crawler is null, so when it tries to access crawler->children[], it seg faults.

Once this is fixed, there are other issues, but that's another question. ;-)

Also, there's an obvious memory leak here:

trie* crawler = malloc(sizeof(trie));
...
crawler = root;

It allocates and then abandons memory. There's no need to malloc the memory if you're going to immediately assign the pointer to something else. Just assign it to root to start with.

1
  • Thank you very much Cliff! I found out that my load() function also had many problems, which you may had already noticed. I re-wrote my code and now it's working! Jul 6 '16 at 2:45

You must log in to answer this question.

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