pset5 - not sure where memory leak lies

Question

I've looked through a few answers and I was unable to make this work. My code fails the last check since I'm getting "still reachable" errors. Help50 seems to think I'm doing something wrong in hash() but valgrind calls out load(), even though I've freed my node and initially set its next pointer to NULL. Code is as follows (got rid of the #includes):

// 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 = 25;

// Hash table, array of node pointers
node *table[N];

// Word counter and pointer for number of words loaded in dictionary
int num_dict_words = 0;
int *num_dict_words_p = &num_dict_words;

// Returns true if word is in dictionary, else false
bool check(const char *word)
{
    // Hash word to obtain bucket
    int bucket = hash(word);

    // Create cursor holding value of head pointer in that bucket
    node *cursor = table[bucket];

    while (cursor != NULL)
    {

        int result = strcasecmp(cursor->word, word);

        if (result == 0)
        {
            return true;
        }

        else
        {
            cursor = cursor->next;
        }
    }
    //printf("%s not found\n", word);
    return false;
}

// Hashes word to a number (takes str and returns index)
unsigned int hash(const char *word)
{
    /*djb2 hash function, created in 1991 by Daniel J. Bernstein
    Lots of hash functions here: http://www.cse.yorku.ca/~oz/hash.html*/
    unsigned long hash_num = 5381;

    char *lc_word = malloc(strlen(word) * sizeof(char));

    int word_len = strlen(word);

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

    int lc_word_len = strlen(lc_word);

    // Don't read the null terminator
    //for (int i = 0, word_len = strlen(lc_word); i < word_len-1; i++)
    for (int i = 0; i < lc_word_len-1; i++)
    {
        hash_num = (hash_num * 33 + lc_word[i]);
    }
    // Needs to be less than N to fit in hash table
    hash_num = hash_num % N;

    free(lc_word);

    return hash_num;
}

// Loads dictionary into memory, returning true if successful, else false
bool load(const char *dictionary)
{
    // Create hash table of size n where each bucket holds a head ptr to NULL
    for (int i = 0; i < N; i++)
    {
        node *head = NULL;
        table[i] = head;
    }

    // Open dictionary file
    FILE *f = fopen(dictionary, "r");

    // Check for memory error
    if (f == NULL)
    {
        return false;
    }

    // Create array to hold word (temporarily) that was read from file
    char tmp_word[LENGTH+1];

    // Scan file line by line, 3rd argument is char array to read word into
    while (fscanf(f, "%s", tmp_word) != EOF)
    {
        // Create new node
        node *n = malloc(sizeof(node));

        // Set next value to be NULL
        n->next = NULL;

        // Ensure malloc worked
        if (n == NULL)
        {
            return false;
        }

        // Copy word into node from tmp_word
        strcpy(n->word, tmp_word);

        // Use hash to determine which linked list we place this new node into
        int idx = hash(n->word);

        // Set the node's next value to be the value in the head pointer
        n->next = table[idx];

        // Reset "head" to hold the address of n (of new word)
        table[idx] = n;

        *num_dict_words_p = *num_dict_words_p + 1;
    }

    // Close dictionary file
    fclose(f);

    return true;
}

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

// Unloads dictionary from memory, returning true if successful, else false
bool unload(void)
{
    // Loop thru all items in TABLE array
    for (int i = 0; i < N; i++)
    {
        //node *cursor = table[i];

        /*while (cursor != NULL)
        {
            // Set tmp to hold cursor value
            node *tmp = cursor;

            // Move cursor to next value
            cursor = cursor->next;

            // Free memory at 1 position before cursor
            free(tmp);
        }*/

        for (node *cursor = table[i]; cursor != NULL; cursor = cursor->next)
        {
            node *tmp = cursor;

            if (cursor != NULL)
            {
                cursor = cursor->next;
                free(tmp);
            }

            else
            {
                free(tmp);
            }
        }

    return true;

    }

    // If that didn't work
    return false;
}

Answer 1

The code has some issues. I'll point you at two of them.

First, in the hash function, when creating variables to hold the string, does the code leave enough room for the end of string marker that follows the word?

Second, there's a huge amount of memory that's "still accessible". That says that there's a huge block of memory that isn't freed. Valgrind points at the line in load where each node is created. That's not where the problem lies, but tells you to look at where that memory is freed. In other words, the unload() function.

Interestingly, some memory is freed, but not all.

Hint: how many passes through the outer for loop are actually executed?
It's an easy fix. ;-)

But, there's another problem in unload. Look very closely at the inner for loop. cursor is being double-incremented, once in the for statement and a second time inside the for loop itself. That means that half of the nodes will be skipped.

The inner loop can be greatly simplified. The if statements can be removed and the code inside the inner for loop code block (between the curly braces) can be reduced to 3 lines of code, or 2 lines if you do the following.

If you move node *tmp = cursor; to the beginning of the unload function, you reduce the number of times that this line executes, and cursor is created and destroyed from hundreds of thousands of times, to exactly one.

This should get you thinking! ;-)

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