Unload-function seems to trigger segfault

Question

I'm having some difficulties with pset5 - Mispellings. My program, which uses a hash-table, seemed to work fine until I implemented the unload-function. I used the function shown in the walkthrough by Zamyla and let a for-loop iterate over the hashtable.

node* cursor = hashtable[i];

while (cursor !=NULL)
{
    node* temp=cursor;
    cursor = cursor->next;
    free(temp);
}
// free cursor to make sure last node is also freed
free(cursor);

Now it doesn't run anymore... The program crashes with both dictionaries and with multiple texts.

This is what my program outputs after implementing unload:

MISSPELLED WORDS

Segmentation fault

When I comment-out most of my unload function, and simply let it return "true" or "false", then my program returns the misspelled words. Looking at the output, the program crashes before it can actually print the first misspelled word. This confuses me because unload (at speller.c:140) is called after the for-loop (on line 76) which checks if the word is in the dictionary. Therefore you would expect the crash to occur after the program has printed the misspelled words.

Without the unload-function Valgrind gives back 2 errors, the first being:

==1413== Conditional jump or move depends on uninitialised value(s) 
==1413==    at 0x4E66E4F: toupper (ctype.c:52)
==1413==    by 0x401127: hashfunction (dictionary.c:32)
==1413==    by 0x401291: load (dictionary.c:107)
==1413==    by 0x4009BD: main (speller.c:45)

As you can see, the corresponding line in dictionary.c refers to my hash-function, for which I adapted the example used in the Hash Tables video by Lauren.

int hash_function(char* key)
{
    // hash on first letter of string
    int hash = toupper(key[0]) - 'A';
    return hash % SIZE;
}

When I actually use the unload-function and not let it simply return "true" or "false". Then the uninitialised value seems to be the culprit. According to Valgrind:

==1413== Jump to the invalid address stated on the next line
==1413==    at 0x6373E40: ???
==1413==    by 0x4E58EC4: (below main) (libc-start.c:287)
==1413==  Address 0x6373e40 is 0 bytes inside a block of size 56 alloc'd
==1413==    at 0x4C2AB80: malloc (in /usr/lib/valgrind /vgpreload_memcheck-amd64-linux.so)
==1413==    by 0x40125C: load (dictionary.c:98)
==1413==    by 0x4009BD: main (speller.c:45)

Here I'm lost, this error only occurs when I use my unload-function. However, Valgrind states that the error originates from the hash-function inside my load-function. What confuses me even more is that, looking at the output, the program crashes when checking the words because the program prints out MISSPELLED WORDS (when the dictionary is already loaded) and after that the program segfaults. So where do I look? My hash-function, my load- or my unload-function? And did anyone run into similar problems?

This is my first question so far and I'm erring on the side of caution with the whole Academic Honesty thing. So if it's necessary maybe I can provide more code. Hopefully you guys can point me in the right direction because I'm feeling quite lost here...

Thanks,

Conor

Haarlem, The Netherlands

Answer 1

My guess is that you have a problem in your load() function. Both the unload and hash functions appear to be ok, so I'm thinking that there is a bug in load that is only being exposed by the unload function when it tries to walk the trie. It is possible that load is accessing invalid memory somewhere, or maybe setting a bad pointer in the trie, and when unload tries to access that memory using the bad pointer, it fails. Without seeing more code, it isn't possible to trace the problem. Can you post your load function?