0

I have search around alot of places and even looked at others code but I dont find my code is that much different.

I keep getting program is free of memory errors if I check with cs50. I can run my program fine with normal ./speller etc.. and I get all memory freed from valgrind. I dont understand what is my problem...

// Implements a dictionary's functionality

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

#include "dictionary.h"

//Create node
typedef struct node
{
    bool is_word;
    struct node *children[27];
}
node;

//The root node
node *root;

//Declare bool function for later use
void FreeNode(node* ptr);

//Total number of nodes
int totalNodes;

bool check(const char *word)
{
    node* cursor = root;

    //Find the index for the charactar by using ASCII value
    int id = 0;

    for(int i = 0; word[i] != '\0'; i++)
    {
        if(word[i] == '\'')
        {
            id = 26;
        }
        else
        {
            id = toupper(word[i]) % 'A';
        }

        //Check if the children its NULL or not
        if(cursor->children[id] == NULL)
        {
            //if NULL then node is not created, this also means dictionary doesnt have the word
            //Meaning its misspelled.
            return false;
        }

        //if node exit then go deeper into the trie
        cursor = cursor->children[id];
    }

    //Once we hit the last would we would need to check and return the bool of is_word
    return cursor->is_word; //if true then word exist, else is misspelled/doesnt exist.

}

// Loads dictionary into memory, returning true if successful else false
bool load(const char *dictionary)
{
    // Malloc memory for root
    root = (node*)malloc(sizeof(node));

    //Set all pointer to null
    for (int i = 0; i < 27; i++)
    {
        root -> children[i] = NULL;
    }

    //Keep track of number of nodes
    totalNodes = 0;

    //Read dictionary and check if the dictionary is null or not
    FILE* fp = fopen(dictionary, "r");
    if (fp == NULL)
    {
        //Unload dictionary if it cant be open
        fprintf(stderr, "%s could not be open.\n", dictionary);
        unload();
        return false;
    }

    //Make another node as the cursor with same location as root
    node* cursor = root;

    //Read each character in the dictionary
    for (int c = fgetc(fp); c != EOF; c = fgetc(fp)) //Check if the c is EOF (-1)
    {
        if (c == '\n')
        {
            //Mark as word when we hit the \n aka new line
            cursor->is_word = true;

            //Increment node counter by 1
            totalNodes++;

            //Reset the cursor pointer back to the root pointer of the trie
            cursor = root;
        }
        else
        {
            //Find the index for the charactar by using ASCII value
            int id;

            if(c == '\'')
            {
                id = 26;
            }
            else
            {
                id = toupper(c) % 'A';
            }

            //Check if node is already made
            if (cursor->children[id] == NULL)
            {
                //Make a new node and malloc the memory
                cursor->children[id] = malloc(sizeof(node));
            }

            //if exist then we will keep go deeper into the trie
            cursor = cursor->children[id];
        }
    }

    fclose(fp);

    return true;
}

unsigned int size(void)
{
    return totalNodes;
}

void FreeNode(node* ptr)
{
    //Check if children node is free, if not then free it
    for (int i = 0; i < 27; i++)
    {
        if(ptr->children[i] != NULL)
        {
            FreeNode(ptr->children[i]);
        }
    }
    free(ptr);

    return;
}

bool unload(void)
{
    node* currentnode = root;
    FreeNode(currentnode);
    return true;
}

My error from check50 valgrind tests failed; rerun with --log for more information.

Log 
running valgrind ./speller substring/dict substring/text... 
checking for output "MISSPELLED WORDS ca cats caterpill caterpillars WORDS MISSPELLED: 4 WORDS IN DICTIONARY: 2 WORDS IN TEXT: 6 "... 
checking that program exited with status 0... 
checking for valgrind errors... 
Conditional jump or move depends on uninitialised value(s): (file: dictionary.c, line: 127) 
Conditional jump or move depends on uninitialised value(s): (file: dictionary.c, line: 66) 
Conditional jump or move depends on uninitialised value(s): (file: speller.c, line: 100) 
Conditional jump or move depends on uninitialised value(s): (file: dictionary.c, line: 54) 
Conditional jump or move depends on uninitialised value(s): (file: dictionary.c, line: 156) 

My Valgrind error

    ==8043== Memcheck, a memory error detector
==8043== Copyright (C) 2002-2013, and GNU GPL'd, by Julian Seward et al.
==8043== Using Valgrind-3.10.1 and LibVEX; rerun with -h for copyright info
==8043== Command: ./speller texts/lalaland.txt
==8043== 
==8043== Conditional jump or move depends on uninitialised value(s)
==8043==    at 0x422C43: load (dictionary.c:127)
==8043==    by 0x4208E2: main (speller.c:40)
==8043==  Uninitialised value was created by a heap allocation
==8043==    at 0x4C2AB80: malloc (in /usr/lib/valgrind/vgpreload_memcheck-amd64-linux.so)
==8043==    by 0x422C54: load (dictionary.c:130)
==8043==    by 0x4208E2: main (speller.c:40)
==8043== 

MISSPELLED WORDS

==8043== Conditional jump or move depends on uninitialised value(s)
==8043==    at 0x422518: check (dictionary.c:54)
==8043==    by 0x4212B3: main (speller.c:112)
==8043==  Uninitialised value was created by a heap allocation
==8043==    at 0x4C2AB80: malloc (in /usr/lib/valgrind/vgpreload_memcheck-amd64-linux.so)
==8043==    by 0x422C54: load (dictionary.c:130)
==8043==    by 0x4208E2: main (speller.c:40)
==8043== 
Chazelle
==8043== Conditional jump or move depends on uninitialised value(s)
==8043==    at 0x42273B: check (dictionary.c:66)
==8043==    by 0x4212B3: main (speller.c:112)
==8043==  Uninitialised value was created by a heap allocation
==8043==    at 0x4C2AB80: malloc (in /usr/lib/valgrind/vgpreload_memcheck-amd64-linux.so)
==8043==    by 0x422C54: load (dictionary.c:130)
==8043==    by 0x4208E2: main (speller.c:40)
==8043== 
==8043== Conditional jump or move depends on uninitialised value(s)
==8043==    at 0x421310: main (speller.c:119)
==8043==  Uninitialised value was created by a heap allocation
==8043==    at 0x4C2AB80: malloc (in /usr/lib/valgrind/vgpreload_memcheck-amd64-linux.so)
==8043==    by 0x422C54: load (dictionary.c:130)
==8043==    by 0x4208E2: main (speller.c:40)
==8043== 
==8043== Conditional jump or move depends on uninitialised value(s)
==8043==    at 0x421337: main (speller.c:119)
==8043==  Uninitialised value was created by a heap allocation
==8043==    at 0x4C2AB80: malloc (in /usr/lib/valgrind/vgpreload_memcheck-amd64-linux.so)
==8043==    by 0x422C54: load (dictionary.c:130)
==8043==    by 0x4208E2: main (speller.c:40)
==8043== 

==8043== Conditional jump or move depends on uninitialised value(s)
==8043==    at 0x423024: FreeNode (dictionary.c:156)
==8043==    by 0x423124: FreeNode (dictionary.c:158)
==8043==    by 0x423124: FreeNode (dictionary.c:158)
==8043==    by 0x423124: FreeNode (dictionary.c:158)
==8043==    by 0x422EEC: unload (dictionary.c:176)
==8043==    by 0x4214B4: main (speller.c:152)
==8043==  Uninitialised value was created by a heap allocation
==8043==    at 0x4C2AB80: malloc (in /usr/lib/valgrind/vgpreload_memcheck-amd64-linux.so)
==8043==    by 0x422C54: load (dictionary.c:130)
==8043==    by 0x4208E2: main (speller.c:40)
==8043== 
==8043== Conditional jump or move depends on uninitialised value(s)
==8043==    at 0x423024: FreeNode (dictionary.c:156)
==8043==    by 0x423124: FreeNode (dictionary.c:158)
==8043==    by 0x423124: FreeNode (dictionary.c:158)
==8043==    by 0x422EEC: unload (dictionary.c:176)
==8043==    by 0x4214B4: main (speller.c:152)
==8043==  Uninitialised value was created by a heap allocation==8043==    at 0x4C2AB80: malloc (in /usr/lib/valgrind/vgpreload_memcheck-amd64-linux.so)
==8043==    by 0x422C54: load (dictionary.c:130)
==8043==    by 0x4208E2: main (speller.c:40)
==8043== 
==8043== Conditional jump or move depends on uninitialised value(s)
==8043==    at 0x423024: FreeNode (dictionary.c:156)
==8043==    by 0x423124: FreeNode (dictionary.c:158)
==8043==    by 0x422EEC: unload (dictionary.c:176)
==8043==    by 0x4214B4: main (speller.c:152)
==8043==  Uninitialised value was created by a heap allocation
==8043==    at 0x4C2AB80: malloc (in /usr/lib/valgrind/vgpreload_memcheck-amd64-linux.so)
==8043==    by 0x422C54: load (dictionary.c:130)
==8043==    by 0x4208E2: main (speller.c:40)
==8043== 

WORDS MISSPELLED:     955
WORDS IN DICTIONARY:  143091
WORDS IN TEXT:        17756
TIME IN load:         3.20
TIME IN check:        0.12
TIME IN size:         0.00
TIME IN unload:       13.72
TIME IN TOTAL:        17.04

==8043== 
==8043== HEAP SUMMARY:
==8043==     in use at exit: 0 bytes in 0 blocks
==8043==   total heap usage: 367,084 allocs, 367,084 frees, 82,227,504 bytes allocated
==8043== 
==8043== All heap blocks were freed -- no leaks are possible
==8043== 
==8043== For counts of detected and suppressed errors, rerun with: -v
==8043== ERROR SUMMARY: 9913620 errors from 8 contexts (suppressed: 0 from 0)

I do understand that conditional jump errors ar about var that is not initialised but does that make check50 itself gives error on memory?

0

Your problem is that you are trying to use uninitialised children from nodes.

That could lead to segmentation faults (if you're lucky), or worse.

Valgrind warns you, in order to protect you from those errors.


In this case, I see 2 problems with uninitialised nodes:

  • For your root node, you forget to initialise isword
  • For all other nodes, you forget to initialise both the 27 children and the isword boolean.

Finally, to quote Cliff B:

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

1
  • Thank you. It fixed my problem
    – Shin
    Oct 13 '18 at 18:42

You must log in to answer this question.

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