13

The problem is mainly caused by the if statement on line 69 if (temp->word != NULL) { // some code } valgrind is angry because you never really initialized the member word of your struct pointed to by temp, yet you're trying to check whether it has NULL as a value. While the latter might be true, technically there's no guarantee that word will be ...


13

This appears to be a clang bug that we are investigating. Will update once we know more. UPDATE We have changed check50 and submit50 so the 32-byte "leak" no longer happens. We will be updating the Speller distribution Makefile as well. In the meantime, you can edit the Makefile to remove the -fsanitize flags (per Martino's answer below) to prevent the ...


6

It depends. There are a lot of factors involved. Does the hash function have a limited number of possible values (like 26 if it's based on the first letter)? How much data are you processing? How much memory is available to store these hash table elements? etc. If you have a hash function that is capable of an unlimited number of hash values (as a ...


5

Assuming you're reading the word correctly into new_node -> word and looking at the insertion part of your code if (hashtable[hashvalue]->next == NULL) hashtable[hashvalue]->next = new_node; else new_node->next = new_node; there's a few things that I want to point out here. First, if hashtable[hashvalue] is equal to NULL, there won't ...


4

If we're NOT using a sorted linked-list, then every time we search for a node in that list, we have to traverse through the whole list in the worst case (if the node we're searching for is the last node in the list or it's not in the list at all). The advantage of using a sorted linked-list is that we can quit searching as soon as we hit a larger/smaller ...


4

Following the hint by @anastasy-korobetskaya, I have arrived at this workaround. Sadly, it only helps to get rid of the problem in the IDE, not upon submission, but at least it should allow you to test your memory allocs and frees correctly. Open the file Makefile. It should read: speller: clang -fsanitize=signed-integer-overflow -fsanitize=undefined -...


3

You can set each element individually to NULL using a for loop. I see a small problem with it though. SIZE = 25, so that's elements 0 to 24. Interestingly, because of the way that the hash function is written, it will still work, but all words beginning with a or z will be hashed to 0 and placed in the same linked list. ;-) It also looks like you're trying ...


3

The errors give a very good clue to the problem. Program is "case sensitive" and must be "case insensitive". Perhaps investigate how you can use strcasecmp (as Zamyla mentions in the check walkthrough). From the man page [emphasis added]: The strcasecmp() function compares the two strings s1 and s2, ignoring the case of the characters. It returns an ...


3

Well, this was easy, if not hidden right out in the open. ;-) Look at the core piece of the check code: // Compare 2 strings if (strcasecmp(cursor->word,word) == 0) { return 0; } So, I'm guessing that you're not aware that false is represented by 0 and true by any non-zero integer? Easy mistake to make for new ...


3

I'll take a run at explaining it. This is a very popular hash function for this pset and other uses. It uses a seed value because changing the starting hash value, the seed value, has an effect on how many or how few hash collisions (different inputs producing the same hash as output) occur. For example, using a large prime number may produce less ...


2

It's actually not suggested. It's just an example on a hash function. They, however, expect something a little bit more complicated than this if you chose to implement a hash table for pset6. Another thing is that toupper(key[0]) - 'A' doesn't really get evaluated to a value in [0, 26], but rather, it gets evaluated to a value in [0, 25] assuming key[0] ...


2

suppose we are to implement speller using an array instead of a hash-table or a trie. a main problem that we have is that we don't know the number of words in the dictionary in advance (yes, we know the number of words in the given dictionary per the specs, but our program should allow loading custom dictionaries). as a result, we would have to ...


2

A global variable is one that can be used anywhere in the program. Generally, globals are considered to be a bad practice, but there are times where they are perfectly appropriate for the situation. This is one of those cases. (There are those that say a global should NEVER be used. When you find one of those people, always evaluate their advice with an ...


2

You insert at the end of the linked list. Insertion is faster at the beginning. Instead of nodeNew->next = NULL; current = &hashTable[index]; /* iterate over nodes until reached to the end of the chain */ while ( current != NULL && current->next != NULL){ current = current->next; } current->next = ...


2

Also, implement size, which is a pretty simple function, and see how many words your function loads. My original load function only took in the first word, even though it had seemed like it would work fine when I wrote and reviewed it.


2

I think you should just follow the steps described, write your code. Compile it. Run it. If it runs without errors or segmentation faults keep going to the next function. If you want though to be sure you could use gdb and run your program line by line. If you see that it repeats the reading of the words in the dictionary, and it executes the commands it ...


2

This test in check if(temp->next != NULL) is the heart of the problem. What is the value of temp->next if there is only one word in the "position"? It is, of course, null. Realize that check50 doesn't use the "large dictionary" (you can detect that by looking at the check50 log). Don't you want to continue into the while loop when hastable[position] ...


1

Looks like you're writing to some place you were not supposed to, overwriting your other variables on the stack. Your hash function might not respect the range of 0-676 you specified. Input like the empty string "", or "'", or "a'", would have negative output. I used another simple type of hash function, which went like this int hashthis (char* word) { ...


1

In check: Always normalize (lowercase) your word before hashing, and hash the normalized version. (This might be the reason for too many misspelled words) Other, more random thoughts: Your hash function might not be most efficient in distributing over all the table entries, but should work. In check: Also, your first test whether the list is empty is ...


1

What's causing your seg fault on this line is the sizeof operator: newNode->word = malloc(sizeof(strlen(word) + 1)); What you really meant here was: malloc((strlen(word) + 1) * sizeof(char));


1

In check, you don't copy the terminator, you could add a tmpWord[wordLen] = 0; between the for- and the while loop. It makes little to compare word and tmpWord (the lowercase version of word), but strcmp(targetList->word, tmpWord) might be work. Also, you never store anything in your hash table. After copying the word to the structure, I'd expect ...


1

The strcmp() function doesn't return a bool (true/false), it returns a number, depending on whether they are equal, or depending on which is "greater". If they are equal, strcmp returns 0. Unfortunately, a 0 is interpreted as false. There may be other issues, but this is probably the biggest one. If this answers your question, please click on the check ...


1

The max length of a word really is 45. But riddle me this: When you created/declared the buffer and set the size, did you set it to 45 (or set LENGTH = 45 and use LENGTH in the declatation)? Did you remember or forget to allow space for the end of string marker \0 ? And just for grins, depending on how you are reading from the dictionary file, you may ...


1

The problem lies in the following: alphabet[hash_value] = new_node; The alphabet[] array is an array of integers. 'new_node' is a pointer to a node. This line of code is trying to stuff a memory address (the contents of new_node) into an int (alphabet[hash_value]). Your underlying problem is that you defined the alphabet array as type int when you ...


1

This line: for(int i = 0; !feof(dict); i++) The feof indicator will not be set until AFTER fscanf finds the end of file. So you will have to read past the end of file, store it (i have no idea how you're hashing the words, so I don't know if the key will be a valid entrance, I don't know how you're counting the words or where, which would be a relevant ...


1

There are a few things that your load function should be doing: Just as with a dictionary, you want everything to be arranged alphabetically. That means you should have first created an array of 26 buckets corresponding to the first letter of every word you load. When you add a word to your hash table, your hash function determines which bucket it belongs ...


1

Yes, the dictionary file is expected to be a file that contains a sorted list of words, one per line. Your mission is, indeed, to create in the LOAD function, code that will take those words and insert them into a tree or trie in memory so that you can check words from a test file against them later. LOAD will either take a command line parameter that ...


1

use tools like gdb and valgrind to detect the cause of the problem and solve it! your load function: also do you think relying on feof may cause you to allocate more memory than you need? are you sure the member named word in your struct has enough space to store the current word? just else is enough as oppose to else if (hashtable[index] != NULL). see why?...


1

Without seeing the load and hash functions, it's almost impossible to know what's wrong. It could be that the hash function isn't giving the same result for the same word each time, or the word that is being processed has some stray characters or non-alphas attached, which could change the hash. Or, there's a problem with how the load is being done. You ...


1

First of all your parentheses are possibly wrong placed. From what I get, you want to find if the upper case of key[1] is within 'M' and 'Z'. You should keep in mind that a programing language is more strict than a natural language. So even if in English you can say "if n is larger than 0 and smaller than 2", in programming you have to say "if n is larger ...


Only top voted, non community-wiki answers of a minimum length are eligible