0

I'm posting a new question to a similiar one posted here: Valgrind error in PSET6

My question is almost exactly the same, except that unfortunately unlike the OP, I wasn't able to fix the remaining 194 errors Valgrind gives at the end (I get no leaks, however). I have tried using the --track-origins=yes flag with Valgrind, but to no avail. I'm going to post all my code here just for reference (please edit it as you see fit when you zoom in on the source of my problem) as well as the exact Valgrind output.

Here's my code:

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

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



// declare root pointer of the trie dictionary data structure
node* root = NULL;

//Variable to store number of words in dictionary
int num_words = 0;


/**
 * Returns true if word is in dictionary else false.
 */
bool check(const char* word)
{
    // make traversing pointer to go through the whole dictionary
    node* crawler = root;

    // iterate over every letter of the word
    for(int i = 0, word_length = strlen(word); i < word_length; i += 1)
    { 
        // convert any uppercase letter to lowercase (to match the dictionary)
        char c = tolower(word[i]);

        // check to see if the letter is an apostrophe
        if (c == '\'')
        {
            if (crawler->children[26] == NULL)
            {
                return false;
            }
            crawler = crawler->children[26];
        }

        //Otherwise, it would just be a normal letter, so check to see if it's there or not
        else if (crawler->children[c % 97] == NULL)
        {
            return false;
        }   

        // If it is there, update the pointer
        else
        {
            crawler = crawler->children[c % 97];
        }
    }

    //check to see if the end of the word signifies a whole word in the dictionary
    if (crawler->is_word)
    {
        return true;
    }
    else
    {
        return false;
    }
}


/**
 * Loads dictionary into memory.  Returns true if successful else false.
 */
bool load(const char* dictionary)
{
    // Malloc the root node pointer as well as initialize the pointer to be used and updated in for loop
    root = malloc(sizeof(node));
    for (int i = 0; i < 27; i += 1)
    {
        root->children[i] = NULL;
    }
    node* current_node = root;

    // open dictionary file and test if it opens properly
    FILE* file = fopen(dictionary, "r");
    if (file == NULL)
    {
        return false;
    }

    //iterate over all words in the dictionary and store each one in a trie
    for (char c = fgetc(file); c != EOF; c = fgetc(file))
    {
        //test to see if c is an alphabetic letter
        if (isalpha(c))
        {
            c = tolower(c);
            if (current_node->children[c % 97] == NULL)
            {   
                current_node->children[c % 97] = malloc(sizeof(node));
                if (current_node->children[c % 97] == NULL)
                {
                    return false;
                }
                current_node = current_node->children[c % 97];
                for (int i = 0; i < 27; i += 1)
                {
                    current_node->children[i] = NULL;
                }
            }
            else
            {
                current_node = current_node->children[c % 97];
            }
        }

        //check if it is end of a word
        else if (c == '\n')
        {
            current_node->is_word = true;
            num_words += 1;
            current_node = root; 
        }

        // check if c is an apostrophe
        else if (c == '\'')
        {
            if (current_node->children[26] == NULL)
            {
                current_node->children[26] = malloc(sizeof(node));
                if (current_node->children[26] == NULL)
                {
                    return false;
                }
                current_node = current_node->children[26];
                for (int i = 0; i < 27; i += 1)
                {
                    current_node->children[i] = NULL;
                }
            }   
            else
            {
                current_node = current_node->children[26];
            }
        } 
    }

    //close the file
    fclose(file);

    // return true if everything loads as expected
    return true;
}


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


/**
 * FreeNode function to be used recursively in the unload function
 */
void FreeNode(node* current_node)
{
    if (current_node == NULL)
    {
        return;
    }
    else
    {
        for (int i = 0; i < 27; i += 1)
        {
            if (current_node->children[i] != NULL)
            {
                FreeNode(current_node->children[i]);
            }
            else
            {
                free(current_node->children[i]);
            }
        }
        free(current_node);
    }
}


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

And here's the output from Valgrind:

jharvard@appliance (~/Dropbox/pset5): valgrind --track-origins=yes ./speller ~cs50/pset5/texts/austinpowers.txt
==6637== Memcheck, a memory error detector
==6637== Copyright (C) 2002-2013, and GNU GPL'd, by Julian Seward et al.
==6637== Using Valgrind-3.10.0.SVN and LibVEX; rerun with -h for copyright info
==6637== Command: ./speller /home/cs50/pset5/texts/austinpowers.txt
==6637== 

MISSPELLED WORDS

FOTTAGE
==6637== Conditional jump or move depends on uninitialised value(s)
==6637==    at 0x804901F: check (dictionary.c:64)
==6637==    by 0x8048ABD: main (speller.c:117)
==6637==  Uninitialised value was created by a heap allocation
==6637==    at 0x402A17C: malloc (in /usr/lib/valgrind/vgpreload_memcheck-x86-linux.so)
==6637==    by 0x8049157: load (dictionary.c:104)
==6637==    by 0x8048725: main (speller.c:45)
==6637== 
INT
EVIL'S
s
EVIL'S
Farbissina
FARBISSINA
CARNABY

...........

VO
VO
AUSITN
VO

WORDS MISSPELLED:     644
WORDS IN DICTIONARY:  143091
WORDS IN TEXT:        19190
TIME IN load:         2.82
TIME IN check:        0.10
TIME IN size:         0.00
TIME IN unload:       5.00
TIME IN TOTAL:        7.93

==6637== 
==6637== HEAP SUMMARY:
==6637==     in use at exit: 0 bytes in 0 blocks
==6637==   total heap usage: 367,084 allocs, 367,084 frees, 41,113,888 bytes allocated
==6637== 
==6637== All heap blocks were freed -- no leaks are possible
==6637== 
==6637== For counts of detected and suppressed errors, rerun with: -v
==6637== ERROR SUMMARY: 194 errors from 1 contexts (suppressed: 0 from 0)

Again, apologies if I posted anything extra. I really appreciate all your help, guys!


UPDATE

Ok, so after hours of editing out I was able to find what the source of the problem was. The problem was that after mallocing for each node, I indeed was setting each of the children to NULL, but I wasn't initializing the is_word value to false. Does anyone know why on earth that would cause a memory error? I mean as far as I can see it, any boolean expression is either true or false, so there isn't much room for "garbage value" as there is with pointers. I'm glad I was able to solve the problem, but I'd like explanation from someone on the technical reasons behind this. Thank you all so very much!

1 Answer 1

0

Ok, I actually figured it out, it's pretty simple. It's true that the garbage value contained within is_word could only be true or false (since it's initialized in the struct as a bool). However, it could be set to true in places where there is actually no trie path that signifies the end of the word there. The fact that I only got an error in Valgrind but my output wasn't affected was only a matter of luck. However, this COULD have affected my output had been there a word tested for where the is_word value wasn't initialized to false, and it had a garbage value of true. It would be detected as a true word, and thus not turn up in the misspelled words.

You must log in to answer this question.

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