1

I've successfully implemented the dictionary and it fully works. When I run valgrind I get 2 nodes (224 bytes each) that are leaking. I really don't know how to fix this. Can someone help?

==1316== Conditional jump or move depends on uninitialised value(s)
==1316==    at 0x4014D1: freeNode (dictionary.c:126)
==1316==    by 0x401520: unload (dictionary.c:139)
==1316==    by 0x400F3C: main (speller.c:152)
==1316==  Uninitialised value was created by a heap allocation
==1316==    at 0x4C2AB80: malloc (in /usr/lib/valgrind/vgpreload_memcheck-amd64-linux.so)
==1316==    by 0x4012A7: load (dictionary.c:70)
==1316==    by 0x400A2D: main (speller.c:40)
==1316== 

WORDS MISSPELLED:     644
WORDS IN DICTIONARY:  143091
WORDS IN TEXT:        19190
TIME IN load:         5.44
TIME IN check:        0.27
TIME IN size:         0.00
TIME IN unload:       2.00
TIME IN TOTAL:        7.71

==1316== 
==1316== HEAP SUMMARY:
==1316==     in use at exit: 448 bytes in 2 blocks
==1316==   total heap usage: 365,371 allocs, 365,369 frees, 81,843,792 bytes   allocated
==1316== 
==1316== 448 (224 direct, 224 indirect) bytes in 1 blocks are definitely lost in loss record 2 of 2
==1316==    at 0x4C2AB80: malloc (in /usr/lib/valgrind/vgpreload_memcheck-amd64-linux.so)
==1316==    by 0x401352: load (dictionary.c:89)
==1316==    by 0x400A2D: main (speller.c:40)
==1316== 
==1316== LEAK SUMMARY:
==1316==    definitely lost: 224 bytes in 1 blocks
==1316==    indirectly lost: 224 bytes in 1 blocks
==1316==      possibly lost: 0 bytes in 0 blocks
==1316==    still reachable: 0 bytes in 0 blocks
==1316==         suppressed: 0 bytes in 0 blocks
==1316== 
==1316== For counts of detected and suppressed errors, rerun with: -v
==1316== ERROR SUMMARY: 30 errors from 5 contexts (suppressed: 0 from 0)

Here is my code

     /**
     * Implements a dictionary's functionality.
     */

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

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

    //Number of words in the dictionary
    int count = 0;

    //Root node
    node *root = NULL;

    /**
     * Returns true if word is in dictionary else false.
     */
    bool check(const char *word)
    {
        node *first = root;
        //Iterate over words length
        for(int i=0; i<strlen(word); i++)
        {
          //If the character being analyzed is NULL, return false.
          int index = tolower(word[i])-'a';
          if (word[i] == '\'')
          {
            index = 26;
          }
          if(first->children[index] == NULL)
          {
            first = root;
            return false;
          }
          //If the character is not NULL, go there
          first = first->children[index];
        }
        //Return true if is_word is true
        if(first->is_word)
        {
          first = root;
          return true;
        }
        else
        {
          first = root;
          return false;
        }
    }

    /**
     * Loads dictionary into memory. Returns true if successful else false.
     */
    bool load(const char *dictionary)
    {
      //Opens dictionary in read mode and checks for NULL
      FILE *inptr = fopen(dictionary, "r");
      if (inptr == NULL)
      {
        fclose(inptr);
        return 1;
      }

      //Initialize root and first pointing to it
      root = malloc(sizeof(node));
      node *first = root;

      char word[LENGTH+1];

      //Repeat until end of file
      while (fscanf(inptr, "%s", word) != EOF)
      {
        //Increment counter for every word
        count++;

        //iterate over each letter of the word
        for (int i=0; i<strlen(word); i++)
        {
          int index = tolower(word[i]) - 'a';
          //Changes index if apostrophe is found
          if (word[i] == '\'')
          {
            index = 26;
          }
          //If NULL, malloc node
          if (first->children[index] == NULL)
          {
            node *newNode = malloc(sizeof(node));
            first->children[index] = newNode;
            first = newNode;
          }
          //If there is already a letter, go there
          else
          {
            first = first->children[index];
          }
        }
        //Word was created, so is_word is set to true
        first->is_word = true;
        //First pointer goes back up to root
        first = root;
      }

      fclose(inptr);
      return true;
    }

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


    void freeNode(node* first)
    {
      for(int i=0; i<27; i++)
      {
        if(first->children[i] != NULL)
        {
          freeNode(first->children[i]);
        }
      }
      free (first);
    }

    /**
     * Unloads dictionary from memory. Returns true if successful else false.
     */
    bool unload(void)
    {
      freeNode(root);
      if(root == NULL)
      {
        return true;
      }
      else
      {
        return false;
      }
    }
1
  • I am getting the same result with similar code. I only get it when the dictionary has more than 136773 words. Otherwise, no leak. My code passes Check50, as well. Found a mention of recursion running out of stack [here(cs50.stackexchange.com/questions/16743/… , but haven't nailed down a solution. I'll keep working on it and check back. – mathewcdaniels Feb 21 '17 at 22:28
1

Following up on my previous comment, it seems that I was indeed running out of stack memory. I spent some time streamlining my code by eliminating a couple of temporary pointers that were ultimately unnecessary in my recursive function that unloads the dictionary and adjusting the way '\''s are handled and that seems to have eliminated the small memory leak.

If you can find some places to consolidate your code, hopefully it will work for you, too. Best of luck!

You must log in to answer this question.

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