0

I have managed to finish pset5 speller and attempted creating dictionaries with linked-list, hash tables and tries. They are all working successfully and if I create a hash table with 20,000 elements it is significantly faster than the staff answers. However I am still not completely happy with the code for my tries.

The program works great but I have been having issues with Valgrind which I have managed to correct but I am not feeling satisfied with the workaround.

I was originally getting the message:

All heap blocks were freed -- no leaks are possible

Followed by:

ERROR SUMMARY: 10000000 errors from 6 contexts (suppressed: 0 from 0)

The other entries in Valgrind point to the cause of the error being:

==281730== Conditional jump or move depends on uninitialised value(s)
==281730==    at 0x401352: load (dictionary.c:115)
==281730==    by 0x4009FD: main (speller.c:40)
==281730==  Uninitialised value was created by a heap allocation
==281730==    at 0x4C2AB80: malloc (in /usr/lib/valgrind/vgpreload_memcheck-amd64-linux.so)
==281730==    by 0x401288: load (dictionary.c:85)
==281730==    by 0x4009FD: main (speller.c:40)
==281730== 
==281730== Conditional jump or move depends on uninitialised value(s)
==281730==    at 0x4013D1: load (dictionary.c:132)
==281730==    by 0x4009FD: main (speller.c:40)
==281730==  Uninitialised value was created by a heap allocation
==281730==    at 0x4C2AB80: malloc (in /usr/lib/valgrind/vgpreload_memcheck-amd64-linux.so)
==281730==    by 0x401363: load (dictionary.c:118)
==281730==    by 0x4009FD: main (speller.c:40)
 ==281730== Conditional jump or move depends on uninitialised value(s)
==281730==    at 0x4011D0: check (dictionary.c:56)
==281730==    by 0x400D87: main (speller.c:112)
==281730==  Uninitialised value was created by a heap allocation
==281730==    at 0x4C2AB80: malloc (in /usr/lib/valgrind/vgpreload_memcheck-amd64-linux.so)
==281730==    by 0x401363: load (dictionary.c:118)
==281730==    by 0x4009FD: main (speller.c:40)
==281730== 
==281730== Conditional jump or move depends on uninitialised value(s)
==281730==    at 0x4014B7: deletetrie (dictionary.c:178)
==281730==    by 0x4014D5: deletetrie (dictionary.c:182)
==281730==    by 0x4014D5: deletetrie (dictionary.c:182)
==281730==    by 0x4014D5: deletetrie (dictionary.c:182)
==281730==    by 0x401444: unload (dictionary.c:162)
==281730==    by 0x400F0C: main (speller.c:152)
==281730==  Uninitialised value was created by a heap allocation
==281730==    at 0x4C2AB80: malloc (in /usr/lib/valgrind/vgpreload_memcheck-amd64-linux.so)
==281730==    by 0x401363: load (dictionary.c:118)
==281730==    by 0x4009FD: main (speller.c:40)
==281730== 
==281730== Conditional jump or move depends on uninitialised value(s)
==281730==    at 0x4014B7: deletetrie (dictionary.c:178)
==281730==    by 0x4014D5: deletetrie (dictionary.c:182)
==281730==    by 0x4014D5: deletetrie (dictionary.c:182)
==281730==    by 0x401444: unload (dictionary.c:162)
==281730==    by 0x400F0C: main (speller.c:152)
==281730==  Uninitialised value was created by a heap allocation
==281730==    at 0x4C2AB80: malloc (in /usr/lib/valgrind/vgpreload_memcheck-amd64-linux.so)
==281730==    by 0x401363: load (dictionary.c:118)
==281730==    by 0x4009FD: main (speller.c:40)
==281730== 
==281730== Conditional jump or move depends on uninitialised value(s)
==281730==    at 0x4014B7: deletetrie (dictionary.c:178)
==281730==    by 0x4014D5: deletetrie (dictionary.c:182)
==281730==    by 0x401444: unload (dictionary.c:162)
==281730==    by 0x400F0C: main (speller.c:152)
==281730==  Uninitialised value was created by a heap allocation
==281730==    at 0x4C2AB80: malloc (in /usr/lib/valgrind/vgpreload_memcheck-amd64-linux.so)
==281730==    by 0x401363: load (dictionary.c:118)
==281730==    by 0x4009FD: main (speller.c:40)

I believe these errors were due to the pointers within nodes not being initialised to null, so I created loops to iterate through all the child node pointers in any new node that is created to be set to null. This has removed the error but I was wondering if there is a better work around it feels a bit strange that I have to jump through this hoop every time I malloc a new node.

To make things more clear this is the final code with all the corrections (which I have tried to highlight). I have also make arrows to show the original line numbers where Valgrind noted there were errors:

/**
 * Dictionary.c
 * This version uses tries
 * Almost as quick as 20000 block hash table.
 * Holmes takes 0.62 sec
 * Implements a dictionary's functionality.
 */

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

// define a node
// 27 elements for all letters and \'
typedef struct node
{
    struct node* child[27];
    bool is_word;
}
node;

// globally define root as it will be needed in several functions
node* root;

// declare custom function to free trie nodes (see end of code)
bool deletetrie(node *name);

// global variable for dictionary word count
// counts words whilst being added to linked list to save time later
int wordCount;

/**
 * Returns true if word is in dictionary else false.
 */
bool check(const char *word)
{
    // pointer to start checking from root
    node *check = root;

    // iterate through all letters of word
    for(int j = 0, k = strlen(word); j < k; j++)
    {
        // convert to number in alphabet (lower case)
        int children = tolower(word[j]) - 97;
        // if apostrophe make it element 26
        if (word[j] == 39)
        {
            children = 26;
        }

        // if there is no node for the iterated letter
        // that means this is not a word therefore return false
        if (check->child[children] == NULL)                   <=======originally line 56
        {
            return false;
        }

        // move pointer to next array
        check = check->child[children];
    }
    // final check to see if there is a is_word flag
    return check->is_word;
    // default is to return false
    return false;
}

/**
 * Loads dictionary into memory. Returns true if successful else false.
 */
bool load(const char *dictionary)
{
    // load the dictionary file
    FILE* diction = fopen(dictionary, "r");
    // check if any errors loading dictionary
    if (diction == NULL)
    {
        fprintf(stderr, "Could not load the dictionary %s\n", dictionary);
        return false;   
    }

    // create a new node for root of list
    root = malloc(sizeof(node));                         <=======originally line 85
    // check new node does not equal NULL, else return false
    if (root == NULL)
    {
        fclose(diction);
        return false;
    }
=================THIS IS THE CORRECTION I MADE======================        
for (int p = 0; p < 27; p++)
    {
        root->child[p] = NULL;
    }
    root->is_word = false;
=================END OF THE CORRECTION I MADE======================

    // count words now to prevent needing to when during unsigned int size(void)
    wordCount = 0;

    // temporary variable to save each word
    char newWord[LENGTH + 1];

    // continue scanning file until no more strings
    while(fscanf(diction, "%s", newWord) != EOF)
    {
        // set pointer to root node
        node *letter = root;
        // iterate through each letter of word
        for (int i = 0, n=strlen(newWord); i < n; i++)
        {
            // convert to number in alphabet
            int charac = newWord[i] - 97;
            // if apostrophe make it element 26
            if (newWord[i] == 39)
            {
                charac = 26;
            }
            // if no array for letter present, create it
            if (letter->child[charac] == NULL)         <=======originally line 115
            {
                // create a new node in which to place word
                node* newNode = malloc(sizeof(node));         <=======originally line 118
                // check new node does not equal NULL, else return false
                if (newNode == NULL)
                {
                    fclose(diction);
                    return false;
                }
=================THIS IS THE CORRECTION I MADE======================
                for (int p = 0; p < 27; p++)
                {
                    newNode->child[p] = NULL;
                }
                newNode->is_word = false;
=================END OF THE CORRECTION I MADE======================
                // link new array to child element of current array
                letter->child[charac] = newNode;
            }
            // move to next array
            letter = letter->child[charac];
        }
        // set is_word flag to true
        if (letter->is_word == false)                 <=======originally line 132
        {
            letter->is_word = true;
        }
        // add to word counter
        wordCount++;
    }
    // close the dictionary file to prevent memory leaks
    fclose(diction);

    // if successful return true
    return true;
}

/**
 * Returns number of words in dictionary if loaded else 0 if not yet loaded.
 */
unsigned int size(void)
{
    // already counted whilst loading dictionary so no need to count again
    return wordCount;
}

/**
 * Unloads dictionary from memory. Returns true if successful else false.
 */
bool unload(void)
{
    // use custom recursive function to free nodes
    // start from root node
    if (deletetrie(root) == true)                  <=======originally line 162
    {
        return true;
    }
    // default is to return false   
    return false;
}

bool deletetrie(node *name)
{
    // counter to make sure all elements are cleared
    int counter = 0;
    // iterate through all elements in array
    for (int k = 0; k < 27; k++)
    {
        // if element points to another array move pointer to it
        if (name->child[k] != NULL)                 <=======originally line 178
        {
            node* pointer = name->child[k];
            // recursively perform this function on the child array
            deletetrie(pointer);                 <=======originally line 182
        }
        counter++;
    }
    // once all elements are free free the node
    free(name);
    // return true if all elements cleared
    if (counter == 27)
    {
        return true;
    }
    // default to return false
    return false;
}

Is this really the only way to correct my errors?

I would appreciate any other comments on improving my code too.

Thank you.

1
  • Just as an FYI, you might get more answers, more info if you post this on the stackexchange main as a C question instead of in CS50 sub. Feb 14, 2017 at 16:24

1 Answer 1

0

One way would be to use calloc to allocate the nodes instead of malloc. calloc sets the memory to 0. Then, instead of testing for NULL (as here if (letter->child[charac] == NULL)), you would test for 0.

You might also try memset. Something like memset(newNode,0,sizeof(node)) will set all the values to 0. (Again, it would require a change to the if NULL tests).

2
  • Thanks for the reply, I will try that in the future. However when using malloc to make the nodes for a trie is this the correct way to go about it?
    – Souper
    Feb 14, 2017 at 19:50
  • I do not know of a different way to initialize each element other than one at a time. Which doesn't mean there isn't another way! :) Feb 14, 2017 at 21:05

You must log in to answer this question.

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