1

I chose to implement speller with a hash table and the code seems to be working fine and passes check50 except for a memory leak. I read other posts reporting similar issues and I think that the issue is that I'm allocating memory in my load function to store each word in each node of the table and it seems like that particular memory ( for each node->word which is a char[] variable) is not freed (but it seems like it's only in some cases...) but if I try freeing that memory by first trying to free the data in each node I get a double free error...

If anyone can guide me on what is actually the problem and what I'm doing wrong it would be really appreciated...

Here is my code for both the load() and unload() functions as well as the report from valgrind:

Load:

typedef struct node {

char word[LENGTH + 1];
struct node* next;

} node;

node *hashtable[SIZE];

//Initialize each pointer of the table to null.
node* initialize(node* table[]) {

  for (int i = 0; i < SIZE; i++) 
      table[i] = NULL;

  return *table;
}

bool load(const char *dictionary)
{

  initialize(hashtable);

  FILE* w = fopen(dictionary, "r");

  if (w == NULL) 
      return false;

  char string[LENGTH + 1];

  int index = 0;

  while (fscanf(w, "%s", string) == 1) {

      index = hash(string);

      node *wd = malloc(sizeof(node));

      if (wd == NULL) {

          printf("LOAD: No more memory for new node.");
          return false;
      }

      wd->next = NULL;
      strcpy(wd->word, string);

      if (hashtable[index] == NULL) {

          hashtable[index] = wd; 
      }

      else {

          wd->next = hashtable[index];
          hashtable[index] = wd;
      }
  }

  fclose(w);

  return true;
}

Unload:

bool unload(void)
{

  int i;
  node *ptr = NULL;
  node *tmp = NULL;
  bool isUnloaded;

  for (i = 0; i < SIZE; i++) {

        isUnloaded = false;

          if (hashtable[i] == NULL) {

              i++;
              free(hashtable[i]);
              isUnloaded = true;
          }

          else {

             ptr = hashtable[i];

             while (ptr->next != NULL) {

                  tmp = ptr->next;
                  //free(ptr->word);
                  free(ptr);
                  ptr = tmp;
                  //free(tmp->word);
                  //free(ptr);
                  //free(ptr->word);
                  isUnloaded = true;
              }
          }
  }

  free(ptr);

  return (isUnloaded) ? true : false;

}

I left commented out some of the different combinations I tried for freeing the node->word... Finally here is what valgrind says:

==41326== HEAP SUMMARY:
==41326==     in use at exit: 71,960 bytes in 1,285 blocks
==41326==   total heap usage: 143,093 allocs, 141,808 frees, 8,014,232 
bytes allocated
==41326== 
==41326== 71,960 bytes in 1,285 blocks are definitely lost in loss 
record 1 of 1
==41326==    at 0x4C2AB80: malloc (in 
/usr/lib/valgrind/vgpreload_memcheck-amd64-linux.so)
==41326==    by 0x401403: load (dictionary.c:116)
==41326==    by 0x400A6D: main (speller.c:40)
==41326== 
==41326== LEAK SUMMARY:
==41326==    definitely lost: 71,960 bytes in 1,285 blocks
==41326==    indirectly lost: 0 bytes in 0 blocks
==41326==      possibly lost: 0 bytes in 0 blocks
==41326==    still reachable: 0 bytes in 0 blocks
==41326==         suppressed: 0 bytes in 0 blocks
==41326== 
==41326== For counts of detected and suppressed errors, rerun with: -v
==41326== ERROR SUMMARY: 1 errors from 1 contexts (suppressed: 0 from 
0)

The reports say that the problem is this line in the load() function:

node *wd = malloc(sizeof(node));

but I have no idea how to solve this...

2 Answers 2

0

No wonder the source is the malloc, as it's the only place where you allocate nodes for your linked lists. But you allocated there for a reason, and I don't see you allocated more than you needed.

unload is not working properly.

I don't exactly get the logic of that if-else, but inside the for loop, you should basically just

        ptr = hashtable[i];
        while (ptr != NULL) {
            tmp = ptr->next;
            free(ptr);
            ptr = tmp;
        }
        hashtable[i] = NULL; // optional

I'm not sure what you expect your variable isUnloaded to contain. I cannot imagine a case you want your function to return false.

Also, while not wrong, in load

      wd->next = NULL;
      strcpy(wd->word, string);
      if (hashtable[index] == NULL) {
          hashtable[index] = wd; 
      }
      else {
          wd->next = hashtable[index];
          hashtable[index] = wd;
      }

can be rewritten to

      strcpy(wd->word, string);
      wd->next = hashtable[index]; 
      hashtable[index] = wd;
1
  • Thanks for your answer! I realize that some of my code can still be optimized and rewritten in a more compact way. I still need to clean it up because some things I tried to add more for debugging purposes. As for the isUnloaded variable, I was trying to implement a sentinel value that would return false if there was a problem in freeing the memory but I know that right now it always returns true... still need to work on that as well as the other things you mentioned.
    – Mynah
    May 12, 2017 at 15:09
-1

EDIT:

Right after posting my question I actually found the answer! It was a just a small detail...

In my original unload function, all nodes were freed properly except for the head of each linked list of the hashtable (hashtable[i]). I noticed this by running valgrind with various texts and trying to see if there was a difference in the memory lost. I saw that actually there was no difference and the same amount of memory kept being lost independently of the text I used and that the amount of blocks lost were the same as the size of my hashtable. So I juts changed the placement of my last call to free to intergrate it in the loop like so:

else {

         ptr = hashtable[i];

         while (ptr->next != NULL) {

             tmp = ptr->next;
             free(ptr);
             ptr = tmp;   
         }  
      }

      free(tmp);
      isUnloaded = true;
  }

  return (isUnloaded) ? true : false;

}

And voila, valgrind doesnt yell at me anymore :)

==42140== 
==42140== HEAP SUMMARY:
==42140==     in use at exit: 0 bytes in 0 blocks
==42140==   total heap usage: 143,093 allocs, 143,093 frees, 8,014,232 
bytes allocated
==42140== 
==42140== All heap blocks were freed -- no leaks are possible
==42140== 
==42140== For counts of detected and suppressed errors, rerun with: -v
==42140== ERROR SUMMARY: 0 errors from 0 contexts (suppressed: 0 from 
0)
3
  • The code shown in your answer looks like it does double-free (freeing same memory block twice) whenever an entry of the hash table is empty. Was that your actual solution? Also, I hope you removed that odd i++; from the loop body.
    – Blauelf
    May 15, 2017 at 8:19
  • @Blauelf I know it was a while back but I edited my answer to show the actual solution. Hopefully it is more clear now.
    – Mynah
    Jun 7, 2017 at 19:41
  • The part in front of the else would also be interesting. I somehow expect this code to fail to unload on certain small dictionaries (with multiple entries in some bins and none in others).
    – Blauelf
    Jun 8, 2017 at 8:48

You must log in to answer this question.

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