0

I am doing the trie version of speller in pset4 and keep getting a segmentation fault.

I have run my code on short dictionaries and short text files and it seems to work just fine but when I try something a bit longer (like lalaland.txt) I get a segmentation fault in the 'unload' function.

When I ran check50 I got a few errors but they all return the same error message: "double free or corruption (top)"

I keep going through my code but cant figure out where I am freeing up space that I haven't malloc-ed or am freeing the same node twice.

My code is below:

        // Implements a dictionary's functionality

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

    #include "dictionary.h"

    // Represents number of children for each node in a trie
    #define N 27

    // Represents a node in a trie
    typedef struct node
    {
        bool is_word;
        struct node *children[N];
    }
    node;

    // Prototypes - used in the following functions
    int char_to_int(char c);
    bool free_trie(node *point);
    int dict_count = 0;

    // Represents a trie
    node *root;

    // Loads dictionary into memory, returning true if successful else false
    bool load(const char *dictionary)
    {
        // Initialize trie
        root = malloc(sizeof(node));
        if (root == NULL)
        {
            return false;
        }
        root->is_word = false;
        for (int i = 0; i < N; i++) 
        {
            root->children[i] = NULL;
        }

        // Open dictionary
        FILE *file = fopen(dictionary, "r");
        if (file == NULL)
        {
            unload();
            return false;
        }

        // Buffer for a word
        char word[LENGTH + 1];

        // Insert words into trie 
        while (fscanf(file, "%s", word) != EOF)
        {
            //temporary pointer starting at root
            node *point = root;

            // Iterate through each char in word
            for (int i = 0, l = strlen(word); i < l; i++)
            {
                int index = char_to_int(word[i]);

                // If node for char does not exist, create a new node and link to the trie
                if (point->children[index] == NULL)
                {
                    // Create a new node
                    node *add_node = malloc(sizeof(node));
                    if (add_node == NULL)
                    {
                        return false;
                    }

                    // Set children to null and is_word to false
                    add_node->is_word = false;
                    for (int j = 0; j < N; j++)
                    {
                        add_node->children[j] = NULL;
                    }

                    // Link the new node to the char in question
                    point->children[index] = add_node;

                    // Go to the new node
                    point = add_node;
                }

                // If path exists then follow to the next node
                else
                {
                    point = point->children[index];
                }

                // If this is the last character in the word then change is_word to true
                if (i == (l-1))
                {
                    point->is_word = true;
                    dict_count++;
                }
            }
        }

        // Close dictionary
        fclose(file); //

        // Indicate success
        return true;
    }

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

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

        // Temporary node to iterate through trie
        node *point = root;

        // Check if char in word is in trie
        for (int i = 0, l = strlen(word); i < l; i++)
        {
            int index = char_to_int(word[i]);

            if (point->children[index] != NULL)
            {
                point = point->children[index];
            }

            else
            {
                return false;
            }

            // If last char in word then check if is_word is true or false
            if (i == (l - 1) && point->is_word == false)
            {
                return false;
            }

            else if (i == (l - 1) && point->is_word == true)
            {
                return true;
            }
        }

        return false;
    }

    // Unloads dictionary from memory, returning true if successful else false
    void unload_node(node *point)
    {
        for (int i = 0; i < N; i++)
        {
            if (point->children[i] != NULL)
            {
                point = point->children[i];

                unload_node(point);
            }
        }

        free(point);
    }

    bool unload(void)
    {
        if (root == NULL)
        {
            return false;
        }
        else
        {
            unload_node(root);
            return true;
        }

    }

    //convert char into lowercase and store as an int, if apostrophe then return 26
    int char_to_int(char c)
    {
        if (c == '\'')
        {
            return 26;
        }

        char new_char = tolower(c);

        int number = (int) new_char;

        number -= 97;

        return number;
    }
1

In unload_node, change

                point = point->children[i];

                unload_node(point);

to just

                unload_node(point->children[i]);

You should not change point in that function. Its initial value is still needed.

1
  • Fantastic! - I completely missed that and it make so much sense, program works perfectly now, thank you! – Egill Dec 13 '19 at 12:03

You must log in to answer this question.

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