0

I've been doing this pset for 3 weeks. This is the hardest pset ever. The segfault seems relevant to the free_node() function. But the valgrind report is full of confusing jargon. I'm completely lost. Great many thanks for your patience and help!

==3473== Conditional jump or move depends on uninitialised value(s)
==3473==    at 0x4013B1: free_node (dictionary.c:160)
==3473==    by 0x4013D0: free_node (dictionary.c:164)
==3473==    by 0x4013D0: free_node (dictionary.c:164)
==3473==    by 0x4013D0: free_node (dictionary.c:164)
==3473==    by 0x4013D0: free_node (dictionary.c:164)
==3473==    by 0x4013D0: free_node (dictionary.c:164)
==3473==    by 0x4013D0: free_node (dictionary.c:164)
==3473==    by 0x401352: unload (dictionary.c:145)
==3473==    by 0x400DDC: main (speller.c:166)
==3473== 
==3473== Stack overflow in thread 1: can't grow stack to 0xffe801ff8
==3473== 
==3473== Process terminating with default action of signal 11 (SIGSEGV)
==3473==  Access not within mapped region at address 0xFFE801FF8
==3473==    at 0x4013CC: free_node (dictionary.c:164)
==3473==  If you believe this happened as a result of a stack
==3473==  overflow in your program's main thread (unlikely but
==3473==  possible), you can try to increase the size of the
==3473==  main thread stack using the --main-stacksize= flag.
==3473==  The main thread stack size used in this run was 8388608.
==3473== Stack overflow in thread 1: can't grow stack to 0xffe801ff0
==3473== 
==3473== Process terminating with default action of signal 11 (SIGSEGV)
==3473==  Access not within mapped region at address 0xFFE801FF0
==3473==    at 0x4A256B0: _vgnU_freeres (in /usr/lib/valgrind/vgpreload_core-amd64-linux.so)
==3473==  If you believe this happened as a result of a stack
==3473==  overflow in your program's main thread (unlikely but
==3473==  possible), you can try to increase the size of the
==3473==  main thread stack using the --main-stacksize= flag.
==3473==  The main thread stack size used in this run was 8388608.
==3473== 
==3473== HEAP SUMMARY:
==3473==     in use at exit: 290,334,688 bytes in 1,296,137 blocks
==3473==   total heap usage: 1,296,139 allocs, 2 frees, 290,335,824 bytes allocated
==3473== 
==3473== LEAK SUMMARY:
==3473==    definitely lost: 0 bytes in 0 blocks
==3473==    indirectly lost: 0 bytes in 0 blocks
==3473==      possibly lost: 0 bytes in 0 blocks
==3473==    still reachable: 290,334,688 bytes in 1,296,137 blocks
==3473==         suppressed: 0 bytes in 0 blocks
==3473== Reachable blocks (those to which a pointer was found) are not shown.
==3473== To see them, rerun with: --leak-check=full --show-leak-kinds=all
==3473== 
==3473== For counts of detected and suppressed errors, rerun with: -v
==3473== Use --track-origins=yes to see where uninitialised values come from
==3473== ERROR SUMMARY: 3910033 errors from 3 contexts (suppressed: 0 from 0)
Segmentation fault

Here is my code:

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


#include "dictionary.h"

// Define a struct node to store words
typedef struct node
{
    bool is_word;
    struct node* children[27];
}
node;

// Set the root of tries
node root = {false, {NULL}};


/**
 * Returns true if word is in dictionary else false.
 */

bool check(const char* word)
{
    // TODO
    node* current_node = &root;
    for (int i = 0; word[i] != '\0'; i++)
    {
        // Calculate the index of the pointer of the corresponding trie. 
        int index = (isalpha(word[i])) ? (tolower(word[i]) - 'a'): 26; 
        // If the letter is in the loaded dictionary
        if (current_node -> children[index] != NULL)
        {
            // If the letter is the end of a word.
            if (current_node -> is_word == true)
            {
                return true;
            }
            else
            {
                current_node = current_node -> children[index];
            }
        }
        // If the letter is not in the loaded dictionary
        else
        {
            return false;
        }
    }

    return false;
}

/**
 * Loads dictionary into memory.  Returns true if successful else false.
 */

int word_counter = 0;
bool load(const char* dictionary)
{
    // Read words from dictionary and store them in the tries
        // Read the first letter
        // Store it in the relevant children array (node -> children[x])
        // Read the next letter
        // Store it in the relevant children array (node -> children[x] -> children[x])
        // If a space is read, set is_word true. And contine the loop.  

    // Open the dictionary
    FILE* infile = fopen(dictionary, "r");
    if (infile == NULL)
    {
        printf("Could not open %s.\n", dictionary);
        return false;
    }

    node* current_node = &root;
    for (int c = fgetc(infile); c != EOF; c = fgetc(infile))
    {
        if (c != '\n') 
        {
            // Calculate the index of the children array if c is a letter or an apostrophe.
            int index = (isalpha(c)) ? (c - 'a'): 26;  
            // If children[index] is NULL, add another node to it to suggest that the word hasn't ended yet.
            if (current_node -> children[index] == NULL)
            {
                current_node -> children[index] = malloc(sizeof(node));
                if (current_node -> children[index] == NULL)
                {
                    printf("Memory allocation failed!");
                    return false;// Or return 1???
                }
                current_node = current_node -> children[index];    
            }
            else
            {
                current_node = current_node -> children[index];
                word_counter ++;
            }

        }
        // If c is a '\n', mark the node as the end of the word.
        else
        {
            current_node -> is_word = true;
        }
    }

    fclose(infile);
    return true;
}

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

/**
 * Unloads dictionary from memory.  Returns true if successful else false.
 */
void free_node(node* cursor);
bool unload(void)
{
    // TODO
    //node* current_node = root;
    for (int i = 0; i < 27; i++)
    {
        if (root.children[i] != NULL)
        {
            free_node(root.children[i]);
        }

    }

    return true;
}

void free_node(node* cursor)
{
    for (int i = 0; i < 27; i++)
    {
        // If the child pointer do not point to Null, 
        // it suggests that the pointer points to another node.
        // So dive into the child node.
        if (cursor -> children[i] != NULL)
        {
            cursor = cursor -> children[i];
            // and return the for loop
            return free_node(cursor);
        }
    }
    // Continue the for loop
    // If reach the end of the loop, it suggests the pointer array all point to null.
    // Now you can free the current node.    
    free(cursor);
}

1 Answer 1

0

It looks like the recursive calls to free_node() are generating a stack overflow - at least that's my best guess.

While I'm not exactly sure of the result, I'm absolutely sure of the cause. The load() function has some serious flaws. The most significant issue is that the dictionary is being loaded into one continuous linear string of nodes, not into a trie with many branches. This is happening because current_node is not being reset to root after each word is processed. Each word is being added to the end of the previous word. This will make it impossible to find any words other than the first word in the dictionary, and is also causing the recursion overflow. free_node() is being recursively called once for every letter in the dictionary. Each recursion requires all of the state data (every variable and all the necessary state data) for that recursion to be added to the stack. That's a lot of memory usage!

This is the cause of your seg fault. There are a number of other issues to be fixed, but those would be different questions and you need to have a chance to work on them. ;-)

If this answers your question, please click on the check mark to accept. Let's keep up on forum maintenance. ;-)

3
  • Thank you, Cliff! I've decided to fix those functions first. The load() function now works well. But I found the misspelled word number incorrect. I've reviewed the part many times, But still can't figure out what is wrong. Could you give me some hints?
    – Kevin King
    Commented Sep 22, 2016 at 2:34
  • Like I said, the other problems would be for a new question, where, hopefully, you will post your updated code and comments about what is happening and what you think is going on. ;-)
    – Cliff B
    Commented Sep 22, 2016 at 2:36
  • Thank you, Cliff! I've opened a new question about the issue.
    – Kevin King
    Commented Sep 22, 2016 at 2:55

You must log in to answer this question.

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