0

I'm just about to finish pset5 but I'm stumped on this valgrind error. Check50 tells me everything works well except that I am leaking memory. Valgrind tells me the memory leak is coming from line 44 which is in my check function: "node *cursor = malloc(sizeof(node));". I've clearly allocated memory, but I don't know how to free it. The unload function must not include this chunk of memory. I've tried two things to solve this:

  1. adding some loop that will free memory, similar to the one in the unload function. This didn't help. (I've included it gray-ed out at the end of my check function).

  2. I've tried initializing node *cursor without allocating memory. The program works well, but valgrind tells me I'm trying to use a variable that doesn't have a value, referring to this node *cursor. I don't know why valgrind tells me this when the program runs just fine this way, but whatever valgrind and I don't get along.

Any insight would be appreciated!

Valgrind error: enter image description here

// Implements a dictionary's functiionality
#include <ctype.h>
#include <stdbool.h>
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <strings.h>


#include "dictionary.h"

unsigned int hash_index(const char *word);

// Represents a node in a hash table
typedef struct node
{
    char word[LENGTH + 1];
    struct node *next;
}
node;

// Number of buckets in hash table
const unsigned int N = 10000;

// Hash table
node *table[N];

int dictsize = 0;

bool check(const char *word)
{
    //create copy of word and set it to lowercase
    int n = strlen(word);
    char word_copy[LENGTH + 1];

    for (int i = 0; i < n; i++)
    {
        word_copy[i] = tolower(word[i]);
    }

    word_copy[n] = '\0';

    //hash word
    int hash_number = hash_index(word_copy);
    //create cursor
    node *cursor  =malloc(sizeof(node));
    cursor = table[hash_number];

    while (cursor != NULL)
    {
        if (strcasecmp(cursor->word, word_copy)==0)
        {
            return true;
        }
        cursor = cursor -> next;
    } 
    //this is my attempt at freeing mallocc on line 44
   /* cursor = table[hash_number];
    while (cursor != NULL)
    {
        node *tmp = cursor;
        free(tmp);
        cursor = cursor -> next;
    }*/
    return false;
}

// Hash function posted by reddit user delipity
unsigned int hash_index(const char *word)
{
    unsigned int hash = 0;
    for (int i = 0, n = strlen(word); i < n; i++)
    {
        hash = (hash << 2) ^ word[i];
    }
    return hash % N;
}

bool load(const char *dictionary)
{
    //open file
    FILE *dict = fopen(dictionary, "r");
    if (dict == NULL)
    {
        printf("Cannot open file\n");
        return false;
    }
//create array to place word
    char word[LENGTH + 1];
//load into hash table
    while (fscanf(dict, "%s", word) != EOF)
    {
        node *new_node = malloc(sizeof(node));
        if (new_node == NULL)
        {
            printf("no new_node\n");
            return false;
        }

        dictsize++;

        strcpy(new_node->word, word);

        int hash_code = hash_index(new_node -> word);

        if (table[hash_code] == NULL)
        {
            table[hash_code] = new_node;
        }
        else
        {
            new_node->next = table[hash_code];
            table[hash_code] = new_node;
        }
    }
    fclose(dict);
    return true;
}

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

bool unload(void)
{
    node *cursor;

    for (int i = 0; i < N; i++)
    {
        cursor = table[i];

        while (cursor != NULL)
        {
            node *tmp = cursor;
            cursor = cursor -> next;
            free(tmp);
        }
    }
    return true;
}
2
  • can you post your dictionary.c file?
    – stensal
    Jun 11 '20 at 20:49
  • I've added the code correctly now!
    – Nick
    Jun 11 '20 at 21:10
0

This is a very common newbie error. First, understand that valgrind is telling you which line is creating the memory that is being leaked, not where it's actually leaking.

Look at this code:

//create cursor
node *cursor  =malloc(sizeof(node));
cursor = table[hash_number];

This code creates a temporary pointer var, cursor and initializes it by allocating memory to it. That pointer is then immediately reassigned, thus losing track of the memory that was just allocated.

The newbie error is that new programmers somehow 'learn' that one must always allocate memory to a pointer when created. Remember that creation and initialization are two different operations, even though they are usually done in the same line. Initialization doesn't always mean that memory must be allocated to a pointer.

It is always best practice to initialize a pointer immediately when created. However, you don't have to allocate memory to it to initialize it. Instead, you can set it to NULL immediately. node *cursor = NULL; This initializes it without allocating memory to it.

Here are two ways that you could do this correctly. The first shows how to fix your code:

//create cursor
node *cursor  = NULL;
cursor = table[hash_number];

That eliminates the unneeded memory allocation and the leak.

This second method represents the best practice, since you're immediately putting the pointer to use.

//create cursor
node *cursor  = table[hash_number];

This immediately initializes the cursor to exactly what you want to use it for.

BTW, there's usually no reason to allocate memory in check(). It should simply be looking at existing memory.

Happy programming! ;-)

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

10
  • Thank you! This helped tremendously on how to create and initialize a node. However, when I try both of these solutions, it still doesn't pass check50's valgrind error. This time it says: "Looks like you're trying to use a variable that might not have a value? Take a closer look at line 49 of dictionary.c." Do you know how to avoid this error?
    – Nick
    Jun 12 '20 at 1:46
  • What is line 49? Just because one problem is fixed doesn't mean all are fixed. Frequently, fixing one issue can either expose another issue that was masked, or can introduce another problem.
    – Cliff B
    Jun 12 '20 at 1:47
  • Line 49 is "while (cursor != NULL)", which is the next line after I initialize the cursor node. '//create cursor' 'node *cursor = NULL;' 'cursor = table[hash_number];' ' while (cursor != NULL)'
    – Nick
    Jun 12 '20 at 1:48
  • What does the new code look like? Just paste in the new code here, plus a line or two before and after.
    – Cliff B
    Jun 12 '20 at 1:49
  • This is the change I made: //create cursor <br/> node *cursor = NULL; <br/> cursor = table[hash_number];<br/> while (cursor != NULL)
    – Nick
    Jun 12 '20 at 1:51

You must log in to answer this question.

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