0

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

0

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?

2
  • Thanks for the tip! :-) Indeed, the problem was in my load function. I used a while loop with the following condition while(!feof(cursor)). I checked the man-page and it turns out that feof() returns zero when it reaches the end of the file. Now Valgrind is error-free! I do wonder, though, did my code just keep on malloc'ing forever and ever?
    – hoekschop
    Apr 3 '16 at 15:59
  • Turns out I cheered too soon... Valgrind reported no errors because load didn´t even run! I felt quite stupid yesterday. Today, with the help of gdb I found out that I was creating a node for the last-line in the dictionary. Hashing the zero-terminator gave a negative number which led to a segfault when checking if(hashtable[i] == NULL). I fixed this by checking whether the first character of the word isalpha and if not freeing the node and returning true. I still have to fix one memory leak but at least my program works and check50 returns only smiles...
    – hoekschop
    Apr 4 '16 at 13:41

You must log in to answer this question.

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