Pset5 - Code for dictionary.c works but valgrind returns memory leak

Question

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...

Answer 1

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;

Answer 2

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)