Problems in data structure

Viewed 70

I'm making a data structure that stores strings from a file in memory. The struture is:

typedef struct node
{
    bool end;
    struct node *letters[27];
} node;

Each char from the string goes through a hash function:

int
hash(int letter)
{
    int n;

    // converts upper case to a number from 1 to 26
    if (letter >= 65 && letter <= 90)
        n = letter - 64;

    // converts letter case to a number from 1 to 26
    else if (letter >= 97 && letter <= 122)
        n = letter - 96;

    // converts apostrophe to 27
    else if (letter == '\'')
        n = 0;

    return n;
}

Thus, the structure is similar to a tree where the position of each pointer in the array corresponds to a letter, as follows: tree

The function that loads the words into memory is as follows:

bool
load(const char *dict)
{
    // open the dictionary file
    FILE *infile = fopen(dict, "r");
    if (infile == NULL)
    {
        return false;
    }

    // pointer for the first tree     
    node *first = calloc(28, sizeof(node));
    if (first == NULL)
        return false;

    //pointer to the nodes
    node *nextptr = NULL;

    // word storage variables
    int index = 0;
    char word[LENGTH+1];

    // stores the words of the file in the struct   
    for (int c = fgetc(infile); c != EOF; c = fgetc(infile))
    {   
        // reads only letters and apostrophes
        if ((c >= 65 && c <= 90) || (c >= 97 && c <= 122) || (c == '\''))
        {
            word[index] = c;

            // creates a new tree from the first tree
            if (index == 0)
            {  
                // checks if there is a struct for the char
                if (first->letters[hash(word[0])] != NULL)
                {
                    nextptr = first->letters[hash(word[0])];
                    index++;
                }

                // creates a new struct for the char
                else
                {
                    first->letters[hash(word[0])] = calloc(28, sizeof(node));
                    if (first->letters[hash(word[0])] == NULL)
                        return false;

                    nextptr = first->letters[hash(word[0])];
                    index++;
                }
            }

            // create the following structures
            else
            {
                // checks if there is a struct for the char
                if (nextptr->letters[hash(word[index])] != NULL)
                {
                    nextptr = nextptr->letters[hash(word[index])];
                    index++;
                }

                // creates a new struct for the char
                else
                {
                    nextptr->letters[hash(word[index])] = calloc(28, sizeof(node));
                    if (nextptr->letters[hash(word[index])] == NULL)
                        return false;
                    
                    nextptr = nextptr->letters[hash(word[index])];
                    index++;
                }
            }
        }

        // creates the last struct for a word
        else if (c == '\n')
        {
            // ends the word
            word[index] = '\0';

            // the boolean end is set to true, defining the end of the word
            nextptr->end = true;
            nextptr = NULL;

            // prepares for a new word
            index = 0;
        }
    }

    return true;
}

The function that has an error is an function that check strings and verify if is in the structure:

bool
check(const char *word)
{
    node *checkptr = first;
    
    for (int i = 0; i < sizeof(word); i++)
    {
        if (word[i] == '\0' && checkptr->end == true)
            return true;
        else if (checkptr->letters[hash(word[i])] != NULL)
            checkptr = checkptr->letters[hash(word[i])];
        else
            return false; 
    }

    return false;
}

When the program is started, segmentation fault occurs on the line else if (checkptr->letters[hash(word[i])] != NULL) and valgrind shows Invalid read of size 8.

I will still create a function to give the necessary free but I guess that the problem is there, mainly because I tried to check if the checkptr pointer was really set to the same structure as the first, but I discover that first is set to NULL, why?

Sorry for my bad english, i'm a beginner programmer and it's my first time on Stack Overflow, but I really don't know how to solve this. If someone can help me in any way, i thank you in advance.

1 Answers

The problem was solved. The error really was in the pointer first. I had accidentally used calloc for a new pointer, instead of the original first, so check was accessing the original first pointer (which had remained NULL).

Related