I'm working on the Speller program in Pset5. As always, i'm using a modular approach to construct all the required constituent functions one by one. However, something quite odd is happening in my speller program. I'm implementing a hash table with the Murmurhash3 hash function and all seems to be working well. I implemented the following load function:
bool load(const char* dictionary)
{
char word[46] = {'\0'}; // create array to hold words that are being read
uint32_t hash[4]; /* Output for the hash */
uint32_t seed = 42; /* Seed value for hash */
uint32_t index = 0; // variable to store index obtained from hash
FILE* inptr = fopen(dictionary, "r"); // open the dictionary file
while (fscanf(inptr, "%s", word) != EOF) // read dictionary word by word
{
MurmurHash3_x64_128(word, strlen(word), seed, hash);
index = hash[3] & hashmask(18);
if(hash_table[index] == NULL)
{
hash_table[index] = create_ll(word);
if(hash_table[index] == NULL)
return false;
}
else
{
hash_table[index] = insert_ll(hash_table[index], word);
if(hash_table[index] == NULL)
return false;
}
}
fclose(inptr);
return true;
}
The function seems to be succesful in creating a hash table. The hashmask function is simply a function to create a hashmask of a certain size (to go from a 128-bit hash to a 18 bit hash, since i have 2^18 buckets). I'm resolving the resulting collisions by chaining with linked lists. The hash table is defined globally so i can access it from any function (and it is initialized to NULL by default). The problem arises when i try to 'print' the linked list. I'm using the following simple print_list function:
void print_list(node* ptr)
{
if(ptr == NULL)
return;
node* trav = ptr;
while(trav != NULL)
{
printf("%s ", trav->word);
trav = trav->next;
}
printf("\n");
return;
}
I then use a simple for loop to go through the hash_table and print any linked lists it might encounter:
for(int i = 0; i < #OfBuckets; i++)
{
if(node_array[i] != NULL)
print_list(node_array[i]);
}
This works fine as long as i don't use the aforementioned load function to create the hash table. If i use the load function, for some reason the print_list function prints a newline character instead of the string stored in a particular node. Can anyone spot the mistake in my load function? Any and all help will be greatly appreciated.
I found the problem (see solution in comments below answer).
create_ll
andinsert_ll
) to debug why your load isn't working.