CODEWITHSUNDEEP
cmallocnodesvalgrindtrie
tiff
tiff

Reputation: 131

Memory Allocation error identified by valgrind

bool load(const char *dictionary)
{
// TODO
//create alphanumeric frequency trie from dictionary stored in temporary location

// open dictioary
FILE *dict = fopen(dictionary, "r");
if (dict == NULL)
{
    return false;
}

//beggining of dictionary trie called 'root'
root = (trie*) malloc( sizeof(trie) );
if (root == NULL)
{
    printf("error allocating memory to root for load");
    return false;
}

//beggining of traversal node called 'current' and "attachment" to read/traverse root node
trie* current = NULL;
int a = (int)'a';
int z = (int)'z';
int cha = 0;
current = root;

//construct trie letter branches from ch (character) of single word-lines in dictionary
for ( char ch = fgetc(dict) ; EOF != ch ; ch = fgetc(dict) )
{
            //set cursor letter to indexable value
            if ( ch == '\'' )
            {
                cha = (z + 1) - a;
                //printf("@%d ",cha);
            }
            else
            {
                cha = (ch - a);
                //printf("%d ",cha);
            }

            //create or traverse existing letter branch for next letter ch in word-line
            if( current->children[cha] == NULL && ) //(cha >= 0 && cha <=26) )
            {
                //printf("L");
                current -> children[cha] = (trie*) malloc( sizeof(trie) );
                current = current -> children[cha];
            }
            else //if ( cha >= 0 && cha <=26 )
            {
                current = current -> children[cha];
            }
    //for end of word-line in dictionary label as word and reset cursor node to root of dictionary trie (tree)
    if ( ch == '\n' )
    {
        //printf("\n");
        current->is_word = true;
        wordcount++;
        current = root;
        //printf("%d", wordcount);
    }
}

My program compiles and works exactly as specified for a problem I'm working on however i'm failing the valgrind test at the beginning of the if statement below. Valgrind Test returns "Invalid read of size 8." I'm hoping the code I provided below is enough to clarify where I'm insulting the system's memory.

if( (cha >= 0 && cha <=26) && current->children[cha] == NULL )
{
    current -> children[cha] = (trie*) malloc( sizeof(trie) );
    current = current -> children[cha];
}
else if ( cha >= 0 && cha <=26 )
{
    current = current -> children[cha];
}

Also below is the structure of my trie node:

#define COUNT 27
typedef struct trie
{
    bool is_word;
    struct trie *children[COUNT];
}
trie;

//instantiation structures and variables
trie* root;
int wordcount = 0;
bool loaded;
//freetrie function prototype
void freetrie(trie* step);

Here's how I free malloc memory for the trie nodes:

void freetrie(trie* root)
{
    for(int i = 0; i < 27; i++)
    {
        if (root -> children[i] != NULL)
        {
            freetrie(root -> children[i]);
        }
    }
    free(root);
    return;
}
bool unload(void)
{
    // TODO
    // free memory allocated by load for dictionary
    trie* current = root;
    freetrie(current);
    return true;
}

Upvotes: 0

Views: 114

Answers (1)

user7860670
user7860670

Reputation: 37600

The line if( current->children[cha] == NULL && (cha >= 0 && cha <=26) ) executes index boundary check only after accessing array, it should be rewritten to verify that index is valid before accessing array at that position. It is also a good idea to get rid of magic numbers:

#define TRIE_CHILDREN_COUNT 27

typedef struct trie
{
    bool is_word;
    struct trie *children[TRIE_CHILDREN_COUNT];
}
trie;


if((0 <= cha) && (cha < TRIE_CHILDREN_COUNT) && (NULL == current->children[cha]))

Upvotes: 2

Related Questions