pset5: I am leaking all of my memory. What am I missing?

Question

This problem set is becoming my bane. I have spent hours on it and I am still getting the same issues with valgrind (definitely losing 7 million bytes). I think my issues lie with load and check and not unload or the word count. I have tried starting over and writing everything out on paper, and while that proved to tidy-up and fix some of my code, the whole of it remains broken. Help would be much appreciated :)

Global stuff and headers:

#include <stdbool.h>
#include <stdio.h>
#include <cs50.h>
#include <string.h>
#include <ctype.h>

#include "dictionary.h"

// define a node
typedef struct node
{
// array to store word
char new[LENGTH + 1];

//create a pointer to the next node
struct node* next;
}node;

// hash function
int hash_fxn (char* key)
{
// hash on 1st letter (apostrophe hashes to 'a')
    int hash = toupper(key[0]) - 'A';
    return hash % 26;
}

// create the base array of the alphabet
node* alphabet[26];

// word counter
int wordcount = 0;

Check function:

   /**
   * Returns true if word is in dictionary else false.
   */
   bool check(const char* word)

{ // TODO

// get space for lowercase shifted word
char lowercase[strlen(word)];

// create space for new node cursor
node* cursor = NULL;

// break down word to all lower-case
for (int i = 0; i < strlen(word); i++)
    lowercase[i] = tolower(word[i]);
lowercase[strlen(word)] = '\0'; // end of string marker

// go to corresponding bin for hash function and search
cursor = alphabet[hash_fxn(lowercase)];

while (cursor != NULL)
{
    // compare strings with strcmp
    if (strcmp(cursor->new, lowercase) == 0)
        return true;  
    cursor = cursor->next;
}

free(cursor);
return false;
}

Load function:

/**
* Loads dictionary into memory.  Returns true if successful else false.
*/
bool load(const char* dictionary)
{
// TODO
// allocate space for the array of linked lists
for (int i = 0; i < 26; i++)
{
    alphabet[i] = NULL;
}

// open dictionary
FILE* dict = fopen(dictionary, "r");

if (dict == NULL)
{
    printf("Dictionary could not be loaded\n");
    return false;
}

// create temporary placeholder node
node* temp = NULL;

// execute while the dictionary is not finished
while (!feof(dict))
{
    // create space for new_node
    node* new_word = malloc(sizeof(node));

    // read word from dictionary and place it in new node
    fscanf(dict, "%s", new_word->new);

    // generate hash value
    int hash_value = hash_fxn(new_word->new);

    // if there is nothing already in the hash bin
    if (alphabet[hash_value] == NULL)
        alphabet[hash_value] = new_word; // set the bin equal to the new node

    // if something is in bin insert at the head of the bin
    else if (alphabet[hash_value] != NULL)
    {
        // insert new_word at head of linked list utilizing temporary storage
        temp = alphabet[hash_value];
        new_word->next = temp;
        alphabet[hash_value] = new_word;        
    }

    // add to wordcount
    wordcount++;
}   

// if all goes according to plan, return true
return true;
}

Unload function:

/**
* Unloads dictionary from memory.  Returns true if successful else false.
*/
bool unload(void)
{
// TODO

for (int i = 0; i < 26; i++)
{
    node* cursor = alphabet[i];
    while (cursor != NULL)
    {
        node* temp = cursor;
        cursor = cursor->next;
        free(temp);
    }
    free(alphabet[i]);
}
return true;
}

Answer 1

I haven't tested the code, but I have several observations. First, do you actually have the code fully working? If not, you really should focus on that first. Correcting memory leaks before getting it working often just complicates the debugging.

Here's a red flag:

// create the base array of the alphabet
node* alphabet[25];

There are 26 letters in the alphabet, not 25.

In check():

• you're not inserting an end of string marker into lowercase.
• the pointer cursor is declared with a malloc and later reassigned to something else. The memory that was malloc'd is lost, a memory leak of 45 bytes for every word checked. Assign the pointer to null instead.

Look at the following code:

  while (cursor != NULL)
  {
      // compare strings with strcmp
      if (strcmp(cursor->new, lowercase) == 0)
          free(lowercase);
          free(cursor);
          return true;  
      cursor = cursor->next;
  }

It looks like you wanted to execute multiple statements when the IF statement is true, but only the first free() will execute based on the IF statement because there are no curly braces. The second free and the return will ALWAYS execute. Next, return statements always immediately terminate the current function and return to the calling code.The assignment of cursor is never executed and is dead code. My guess is that you wanted to enclose the two free() statements and the return statement in curly braces.

You could have declared both cursor and lowercase as regular vars instead of pointers and eliminated the need for mallocs and frees for both.

In LOAD():

This code is a big memory leak:

alphabet[i] = malloc(sizeof(node));
alphabet[i] = NULL;

The first line allocates memory, the second line sets the pointer to null, leaving the previously allocated memory lost but still allocated.

Similarly, temp is declared with a malloc and then reassigned, losing the allocated memory. In a related problem that is probably causing more significant issues, you later free(temp);. Earlier, you temp = alphabet[hash_value]; so the last alphabet[hash_value] that was assigned to temp will be freed and lost from the dictionary.

In the unload() function, cursor will always be null when you hit the free(cursor). There's nothing to free there.

In summary, the biggest problem I see is that you declare a pointer, malloc memory to it, and then reassign the pointer elsewhere, thus losing track of the allocated memory. Instead, you could declare them and assign null to the pointers.

There are probably other issues, but this will get you started again.

If this answers your question, please click on the check mark to accept. Let's keep up on forum maintenance. ;-)