I'm very close to completing pset5; all smiley faces except the Valgrind memory leak. I'm hoping someone can help find the problem. I am only leaking 112 bytes and have tried to fix the issue by creating new methods (multiple). Unfortunately, I keep running into the same problem. If I free(table) in the unload method after freeing all other nodes my program fails all previous tests for some reason.
:( program is free of memory errors valgrind tests failed; rerun with --log for more information. running valgrind --show-leak-kinds=all --xml=yes --xml-file=/tmp/tmp3g6pfuv5 -- ./speller substring/dict substring/text... checking for output "MISSPELLED WORDS\n\nca\ncats\ncaterpill\ncaterpillars\n\nWORDS MISSPELLED:
4\nWORDS IN DICTIONARY: 2\nWORDS IN TEXT: 6\n"... checking that program exited with status 0... checking for valgrind errors... 112 bytes in 2 blocks are still reachable in loss record 1 of 1: (file: dictionary.c, line: 310)
Here are the results I get when I run valgrind ./speller texts/cat.txt from the terminal:
~/pset5/speller/ $ valgrind ./speller texts/cat.txt ==9475== Memcheck, a memory error detector ==9475== Copyright (C) 2002-2017, and GNU GPL'd, by Julian Seward et al. ==9475== Using Valgrind-3.13.0 and LibVEX; rerun with -h for copyright info ==9475== Command: ./speller texts/cat.txt ==9475==
MISSPELLED WORDS
==9475== Invalid free() / delete / delete[] / realloc() ==9475== at 0x4C30D3B: free (in /usr/lib/valgrind/vgpreload_memcheck-amd64-linux.so) ==9475== by 0x40145C: freeSLList (dictionary.c:261) ==9475== by 0x401444: freeSLList (dictionary.c:258) ==9475== by 0x401444: freeSLList (dictionary.c:258) ==9475== by 0x401444: freeSLList (dictionary.c:258) ==9475== by 0x401444: freeSLList (dictionary.c:258) ==9475== by 0x401444: freeSLList (dictionary.c:258) ==9475== by 0x401444: freeSLList (dictionary.c:258) ==9475== by 0x401444: freeSLList (dictionary.c:258) ==9475== by 0x401444: freeSLList (dictionary.c:258) ==9475== by 0x401444: freeSLList (dictionary.c:258) ==9475== by 0x401444: freeSLList (dictionary.c:258) ==9475== Address 0x55d10f0 is 0 bytes inside a block of size 56 free'd ==9475== at 0x4C30D3B: free (in /usr/lib/valgrind/vgpreload_memcheck-amd64-linux.so) ==9475== by 0x401450: freeSLList (dictionary.c:259) ==9475== by 0x401444: freeSLList (dictionary.c:258) ==9475== by 0x401444: freeSLList (dictionary.c:258) ==9475== by 0x401444: freeSLList (dictionary.c:258) ==9475== by 0x401444: freeSLList (dictionary.c:258) ==9475== by 0x401444: freeSLList (dictionary.c:258) ==9475== by 0x401444: freeSLList (dictionary.c:258) ==9475== by 0x401444: freeSLList (dictionary.c:258) ==9475== by 0x401444: freeSLList (dictionary.c:258) ==9475== by 0x401444: freeSLList (dictionary.c:258) ==9475== by 0x401444: freeSLList (dictionary.c:258) ==9475== Block was alloc'd at ==9475== at 0x4C2FB0F: malloc (in /usr/lib/valgrind/vgpreload_memcheck-amd64-linux.so) ==9475== by 0x401319: insert_top (dictionary.c:310) ==9475== by 0x4012B8: load (dictionary.c:182) ==9475== by 0x400904: main (speller.c:40) ==9475== ==9475== Invalid free() / delete / delete[] / realloc() ==9475== at 0x4C30D3B: free (in /usr/lib/valgrind/vgpreload_memcheck-amd64-linux.so) ==9475== by 0x40145C: freeSLList (dictionary.c:261) ==9475== by 0x401444: freeSLList (dictionary.c:258) ==9475== by 0x401400: unload (dictionary.c:244) ==9475== by 0x400DA9: main (speller.c:152) ==9475== Address 0x672f0c0 is 0 bytes inside a block of size 56 free'd ==9475== at 0x4C30D3B: free (in /usr/lib/valgrind/vgpreload_memcheck-amd64-linux.so) ==9475== by 0x401450: freeSLList (dictionary.c:259) ==9475== by 0x401444: freeSLList (dictionary.c:258) ==9475== by 0x401400: unload (dictionary.c:244) ==9475== by 0x400DA9: main (speller.c:152) ==9475== Block was alloc'd at ==9475== at 0x4C2FB0F: malloc (in /usr/lib/valgrind/vgpreload_memcheck-amd64-linux.so) ==9475== by 0x401319: insert_top (dictionary.c:310) ==9475== by 0x4012B8: load (dictionary.c:182) ==9475== by 0x400904: main (speller.c:40) ==9475== ==9475== Invalid free() / delete / delete[] / realloc() ==9475== at 0x4C30D3B: free (in /usr/lib/valgrind/vgpreload_memcheck-amd64-linux.so) ==9475== by 0x40145C: freeSLList (dictionary.c:261) ==9475== by 0x401400: unload (dictionary.c:244) ==9475== by 0x400DA9: main (speller.c:152) ==9475== Address 0x673f1c0 is 0 bytes inside a block of size 56 free'd ==9475== at 0x4C30D3B: free (in /usr/lib/valgrind/vgpreload_memcheck-amd64-linux.so) ==9475== by 0x401450: freeSLList (dictionary.c:259) ==9475== by 0x401400: unload (dictionary.c:244) ==9475== by 0x400DA9: main (speller.c:152) ==9475== Block was alloc'd at ==9475== at 0x4C2FB0F: malloc (in /usr/lib/valgrind/vgpreload_memcheck-amd64-linux.so) ==9475== by 0x401319: insert_top (dictionary.c:310) ==9475== by 0x4012B8: load (dictionary.c:182) ==9475== by 0x400904: main (speller.c:40) ==9475== Unloaded: 1
WORDS MISSPELLED: 0 WORDS IN DICTIONARY: 143091 WORDS IN TEXT:
6 TIME IN load: 1.35 TIME IN check: 0.00 TIME IN size: 0.02 TIME IN unload: 0.02 TIME IN TOTAL: 1.40==9475== ==9475== HEAP SUMMARY: ==9475== in use at exit: 7,976,248 bytes in 142,433 blocks ==9475== total heap usage: 143,096 allocs, 1,321 frees, 8,023,416 bytes allocated ==9475== ==9475== 7,976,248 bytes in 142,433 blocks are still reachable in loss record 1 of 1 ==9475== at 0x4C2FB0F: malloc (in /usr/lib/valgrind/vgpreload_memcheck-amd64-linux.so) ==9475== by 0x401319: insert_top (dictionary.c:310) ==9475== by 0x4012B8: load (dictionary.c:182) ==9475== by 0x400904: main (speller.c:40) ==9475== ==9475== LEAK SUMMARY: ==9475== definitely lost: 0 bytes in 0 blocks ==9475== indirectly lost: 0 bytes in 0 blocks ==9475== possibly lost: 0 bytes in 0 blocks ==9475== still reachable: 7,976,248 bytes in 142,433 blocks ==9475== suppressed: 0 bytes in 0 blocks ==9475== ==9475== For counts of detected and suppressed errors, rerun with: -v ==9475== ERROR SUMMARY: 658 errors from 3 contexts (suppressed: 0 from 0)
I used the following method to insert a node to the beginning of the *table[index];
> // modified from https://www2.hawaii.edu/~walbritt/ics212/examples/linkedlist.c
// modified from https://www.opentechguides.com/how-to/article/c/142/linked-list-insert.html
/**
* https://www.opentechguides.com/how-to/article/c/142/linked-list-insert.html
* Inserting a node to the top of a list
* This is probably the easiest and fastest method of adding an element to a linked list. Here are the steps.
*
* Create the new node, let's say N.
* Set the nodes data field (N→data = data).
* Set the next pointer of a new node to head pointer (N→next = head).
* Set the head to point to the new node (head = N).
*
* @return the head of the linked list passed as a parameter after inserting a new node containing data
* @param data: is the string containing the data to add to the new node at the top of the linked list
* @param head: a pointer to the beginning of the linked list in RAM.
*/
/* Add a new node to the top of a list */
node * insert_top(char * data, node *head)
{
node *new_node;
new_node = (node *) malloc(sizeof(node)); // still leaking 112 bytes in 2 blocks as did the other insert method... I guess something is wrong in the unload() method.
strcpy(new_node -> word, data);
//new_node -> word = data;
new_node->next = head;
head = new_node;
return head;
}
Here is my unload method. I tried to use the recursive pseudocode mentioned in the short video on the linked lists.
// Unloads dictionary from memory, returning true if successful else false
/** Your spell checker must not leak any memory. Be sure to check for leaks with Valgrind.
* Ultimately, be sure to free in unload any memory that you allocated in the load!
* Recall that Valgrind is your newest best friend.
* Know that Valgrind watches for leaks while your program is actually running,
* so be sure to provide command-line arguments if you want Valgrind to analyze speller while
* you use a particular dictionary and/or text, as in the below.
* Best to use a small text, though, else Valgrind could take quite a while to run.
*
* $ valgrind ./speller texts/cat.txt
*
* @return true if the memory was successfully unloaded; false otherwise.
*
*/
bool unload(void)
{
freeSLList(*table);
return true;
}
// recursive method to destroy the linked list bzsed on description in Hash Tables https://youtu.be/nvzVHwrrub0.
void freeSLList(node *n)
{
if(n == NULL)// base case
{
// stop
free(n);
}
else
{
freeSLList(n->next);
free(n);
}
free(n);
}
