0

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).

2
  • we'd need to see your two functions (create_ll and insert_ll) to debug why your load isn't working.
    – curiouskiwi
    Feb 7, 2018 at 4:58
  • @curiouskiwi I already found the problem and fixed it accordingly. The problem was a combination of two things; i defined the structure node in such a way that the word member was a char* and i assigned i string to it in create_ll and insert_ll by copying the address. This of course wouldn't work because the memory it was pointing to would be freed as soon as the function returned (it was a function parameter after all). I now defined simply defined a char array of a finited size as a struct member and i copy the parameter string using strcpy.
    – PvtWitt
    Feb 7, 2018 at 13:45

0

You must log in to answer this question.

Browse other questions tagged .