0

I'm working on pset5 right now and I've met this problem that has taken me hours yet no luck to crack. This is how I defined my struct, containing a next[] array of 27 elements.

// define the trie data type
typedef struct trie
{
    bool presence;
    struct trie* next[27];
} trie;

Valgrind is reporting that I accessed 8 bytes of memory inaccessible to me, but I checked the Ascii table and [any lowercase alphabet - 96] should give a number between 1~26, which, since I assign the apostrophe to index 0 of the "next" array, should fit a~z perfectly into index 1~26. I am attaching my code below:

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

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

 int dict_size = 0;

 // define the function that creates a new node
 trie* create(void)
 {
     trie* node = calloc(1, sizeof(trie));
     if (node == NULL)
     {
         unload();
         return 0;
     }
     trie* temp = node;
     free(node);
     return temp;
 }
 trie* root;
 trie* pointer;
 /**
  * Returns true if word is in dictionary else false.
  */
 bool check(const char *word)
 {
     // TODO
     return false;
 }

 /**
  * Loads dictionary into memory. Returns true if successful else false.
  */
 bool load(const char *dictionary)
 {
     // open the dictionary and check for error
     FILE *fp = fopen(dictionary, "r");
     if (fp == NULL)
     {
         printf("Could not open %s.\n", dictionary);
         unload();
         return false;
     }

     // initialize the root of the trie
     root = create();
     pointer = root;
     for (int c = fgetc(fp); c != EOF; c = fgetc(fp))
     {
         if (c == '\'')
         {
             if (pointer->next[0] == NULL)
             {
                 pointer->next[0] = create();
             }
             pointer = pointer->next[0];
         }
         else if (isalpha(c))
         {
             int index = c - 96;
             if (pointer->next[index] == NULL) [LINE 67]
             {
                 pointer->next[index] = create();
             }
             pointer = pointer->next[index];
         }
         else if (c == '\n')
         {
             pointer->presence = true;
             dict_size++;
             pointer = root;
         }
     }
     pointer = root;

     // check whether there was an error
     if (ferror(fp))
     {
         fclose(fp);
         printf("Error reading %s.\n", dictionary);
         unload();
         return false;
     }

     // close text and return true for success
     fclose(fp);
     return true;
 }

 unsigned int size(void)
 {
     return dict_size;
 }

 bool unload(void)
 {
     trie* temp = pointer;
     for (int i = 0; i < 27; i++)
     {
         if (temp->next[i] != 0)
         {
             pointer = pointer->next[i];
             unload();
             pointer = temp;
         }
     }
     free(temp);
     return true;
     }

Above is my code, and the valgrind promt is: Looks like you're trying to access 8 bytes of memory that isn't yours? Did you try to index into an array beyond its bounds? Take a closer look at line 67 of dictionary.c. (which I marked with [LINE 67]). Any insight would be appreciated, thank you!

1

The 8 bytes are a 64 bit pointer. You dereference pointer, which at this time is pointing into unallocated memory, and access its next[index], which is 8 bytes long.

 trie* temp = node;
 free(node);
 return temp;

First of these lines lets temp point to the same memory as node. Second line frees the space. Now, both temp and node point to some memory address that's not allocated any more. Third line returns this address.

You'd better just return node; without those three lines.

While it is not obviously doing something wrong by itself, I don't like this one:

 if (node == NULL)
 {
     unload();
     return 0;
 }

This return 0; is essentially return NULL;, you're returning a null pointer. I have no clear idea how to exit gracefully, but checking here and still returning a NULL pointer makes you handle the case on multiple layers. Maybe you could exit instead of returning, or handle it in the calling layer.

Your unload function does not what you want it to. For a trie, you might want to consider a recursive function to do the actual clean-up, and call it from your unload function, passing the address of the root node.

This recursive function then should call itself for all non-NULL children, and after that free the node itself.

2
  • Thank you Blauelf! Indeed the memory leak was caused by freeing the node before I pass it to the caller, and I realized the node NULL checker does, like you said, need a caller implementation in order for its returned value to have meaning in the parent process. The unload function worked fine though. Again, I appreciate the help! – Haiyun Xu May 22 '17 at 16:32
  • Oh, you're right. Had not recognised how you use a local and a global variable to implement the same function. It would not have been my design of choice, though (I prefer to use global variables as rarely as possible, and on that one only store a pointer to the root node in a global variable, one that I change only in load and unload) – Blauelf May 23 '17 at 7:47

You must log in to answer this question.

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