0

I have done check50 and the only error is "valgrind tests failed; rerun with --log for more information". I can't find the source of the memory leak and I thought that my unload made sense. Here is what I have:

// Implements a dictionary's functionality

#include <stdbool.h>
#include <ctype.h>
#include <string.h>
#include <strings.h>
#include <stdio.h>
#include <stdlib.h>

#include "dictionary.h"

int wordcount = 0; // initialize word count
bool isloaded = false; // may not need

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

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

node *table[N]; // Hash table

bool check(const char *word) // Returns true if word is in dictionary else false
{
    int n = strlen(word); // make lowercase
    char copy[LENGTH + 1];
    for (int i = 0; i < n; i++)
    {
        copy[i] = tolower(word[i]);  
    }
    copy[n] = '\0';
    int x = hash(copy); // get hash number using the now lowercase word
    node *cursor = table[x]; // temp pointer to same place as xth element in hash table, x determined with hash function
    
    while (cursor != NULL) 
    {
        if (strcasecmp(copy, cursor->word) == 0) // case insensitive btw the word and what the pointer is pointing to in the linked list
        {
            return true;
        }
        else
        {
            cursor = cursor->next;
        }
    }
    return false;
}

// SOURCE: delipity on Reddit; https://www.reddit.com/r/cs50/comments/1x6vc8/pset6_trie_vs_hashtable/cf9189q/
unsigned int hash(const char *word) // check to see if this will appear for lowercase
{
    unsigned int hash = 0;
    for (int i = 0, n = strlen(word); i < n; i++)
    {
        hash = (hash << 2) ^ word[i];
    }
    return hash % N;
}

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

bool load(const char *dictionary) // Loads dictionary into memory, returning true if successful else false
{
    FILE *file = fopen(dictionary, "r"); // open dictionary file
    if (!file)
    {
        return false;
    }
    char word[LENGTH + 1];
    
    while(fscanf(file, "%s", word) != EOF) // read strings from file one at at time until hit EOF
    {
        node *n = malloc(sizeof(node)); // allocate memory for new node, check if returned null
        if (n == NULL)
        {
            unload(); 
            return false;
        }
        strcpy(n->word, word);
        int index = hash(n->word); // use hash function to take string and return an index
        
        node *head = table[index];
        // insert into linked list
        if (head == NULL) // ie if its the first element
        {
            table[index] = n;
            wordcount++;
        }
        else
        {
            n->next = table[index];
            table[index] = n;
            wordcount++;
        }
    }
    fclose(file); 
    isloaded = true;
    return true;
}

bool unload(void) // Unloads dictionary from memory, returning true if successful else false
{
    node *head = NULL;
    node *cursor = head;
    while (cursor != NULL)
    {
        node *temp = cursor;
        cursor = cursor->next;
        free(temp);
    }
    return true;
}

And this is the valgrind message:

HEAP SUMMARY:
==11693==     in use at exit: 8,013,096 bytes in 143,091 blocks
==11693==   total heap usage: 143,096 allocs, 5 frees, 8,023,416 bytes allocated
==11693== 
==11693== 8,013,096 bytes in 143,091 blocks are still reachable in loss record 1 of 1
==11693==    at 0x4C2FB0F: malloc (in /usr/lib/valgrind/vgpreload_memcheck-amd64-linux.so)
==11693==    by 0x401275: load (dictionary.c:86)
==11693==    by 0x4009B4: main (speller.c:40)
==11693== 
==11693== LEAK SUMMARY:
==11693==    definitely lost: 0 bytes in 0 blocks
==11693==    indirectly lost: 0 bytes in 0 blocks
==11693==      possibly lost: 0 bytes in 0 blocks
==11693==    still reachable: 8,013,096 bytes in 143,091 blocks
==11693==         suppressed: 0 bytes in 0 blocks
==11693== 
==11693== For counts of detected and suppressed errors, rerun with: -v
==11693== ERROR SUMMARY: 937 errors from 1 contexts (suppressed: 0 from 0)

If I'm interpreting this correctly, the ERROR SUMMARY suggests that there's a single source of the memory error (hopefully that's correct). If anyone could find what I am missing here, I would greatly appreciate it.

1

Let's take a close look at unload:

bool unload(void) // Unloads dictionary from memory, returning true if successful else false
{
    node *head = NULL;
    node *cursor = head;
    while (cursor != NULL)
    {
        node *temp = cursor;
        cursor = cursor->next;
        free(temp);
    }
    return true;
}

In short, it does absolutely nothing. Think about what it's doing. First, it allocates a temporary node pointer called head, which is initialized to NULL. Then another temp node pointer is created called cursor, which is then set equal to head, meaning that cursor is now set to NULL. Then a while loop is set to run until cursor is NULL, which it already is, so the while loop never executes. Let's not forget yet another temp node pointer called temp inside the loop. Want to guess what it would be set to, if the loop actually executed?

Wow! That's a lot of temporary cursor pointers when only 2 are needed.

Also, why doesn't unload look at table[] at all? That's where all the linked lists start!

As you attempt to rewrite unload, think very, very carefully about every variable that is created and ask yourself if it's doing the same thing that another existing variable could do.

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

| improve this answer | |

You must log in to answer this question.

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