pset5 dictionary and valgrind

Question

I am currently working on pset5 and having some issues with errors that were identified by valgrind. My dictionary program seems to run fine- it passes the check50 and it is almost as fast as the staff solution. I thought I was finished with this HW until I ran valgrind and discovered many errors, making me think that I am not understanding some fundamental things.

I have pasted one valgrind issue below and the code that is associated it. Any suggestions or help as to what I am missing is much appreciated.

==17838== 280,000 bytes in 5,000 blocks are definitely lost in loss record 4 of 5

==17838== at 0x4C2AB80: malloc (in /usr/lib/valgrind/vgpreload_memcheck-amd64-linux.so)

==17838== by 0x4015F3: make_node (dictionary.c:216)

==17838== by 0x401346: load (dictionary.c:95)

==17838== by 0x400A0D: main (speller.c:45)

Code:

//initialize the bucket backbone of the hash table.  buckets is 5000
for (int i = 0; i < buckets; i++)     (93)
{
    hashtable[i] = make_node();      (95)
}

//a function to initialize a new node
struct node* make_node()  (214)
{
    struct node* temp = malloc(sizeof(node));    (216)
    temp->next = NULL;     (217)
    return temp;      (218)
}


//update- my unload fxn is listed below. thanks!
bool unload(void)
{
node* freebird = malloc(sizeof(node));
if (freebird == NULL)
{
    return false;
}

for (int i = 0; i < buckets; i++)
{
    freebird = hashtable[i];
    while (freebird->next != NULL)
    {
        node* freebird2 = freebird->next;
        free(freebird);
        freebird = freebird2;
    }
}

return true;

}

Answer 1

I see a couple issues, maybe not all. Your code allocates a node for every element in hashtable[], so none of the elements are null. In unload(), you check while (freebird->next != NULL). Consider that some elements in hashtable[] will have ->next = null. Also, when they're not null, they will be the first node in a linked list and the last node in the linked list will have next = null. This means that one element for every bucket, the last node in the linked list, whether it is an unused single node or the last node in a linked list, will not be freed. The nodes in hashtable[] will simply not be freed when the program terminates (the address remains in the array), but any nodes at the end of a linked list will actually be lost because the rest of the list has been freed.

Additionally, you have node* freebird = malloc(sizeof(node)); in unload. The code then immediately reassigns another address to freebird, so the memory allocated with that malloc will be lost. You don't have to malloc memory to a pointer when it is created. Instead, you could set it to null until you assign another address to it, as you will later. In this case, you actually should set it to null so that you don't leave a garbage address in it and you don't lose any memory with a malloc.

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