HashTable full of single value

Question

I think the problem is in my load function. I am able to successfully create a hash for each word, and I can call my createNode and insertNode functions to such a degree that I create a full hashtable whose "length" covers all the words in the dictionary. However, when I go to compare words from text files with the hashtable, every value in my hashtable equals the last word from the dictionary.

Here is the relevant code:

Define Node for a Linked List of Strings

typedef struct _strNode
{
    char *value;
    //pointer to next node - Initialize as NULL
    struct _strNode* next;
}
strNode;

Define hashtable as an array of linked lists

strNode* hashtable[1220];

Create strNode Function

strNode* createStrNode(char *val)
{
    strNode *n = malloc(sizeof(strNode));
    if (n == NULL)
    {
        return NULL;
    }
    n->value = val;
    n->next = NULL;
    return n;
};

Function for Inserting a New Node within an existing linked list of strings

strNode* insertStrNode(strNode* head, char* val)
{
    // call create new node function and assign to a pointer
    strNode* insert = createStrNode(val);
    if (insert == NULL)
    {
        return NULL;
    }
    // change pointers next value from null to 'first', i.e. most 
    // recently added node, here called 'head'
    insert->next = head;
    return ins;
};

Loads dictionary into memory, returning true if successful else false

bool load(const char *dictionary)
{
    FILE* dict = fopen(dictionary, "r");
    if (dict == NULL)
    {
        printf("Could not open %s.\n", dictionary);
        unload();
        return false;
    }
    char* str = malloc(sizeof(char) * 46);
    while (fscanf(dict, "%s", str) != EOF)
    {
        int hash = hashString(str);
        if (hashtable[hash])
        {
            hashtable[hash] = insertStrNode(hashtable[hash], str);
            if (hashtable[hash] == NULL)
            {
                printf("Out of Memory\n");
                unload();
                fclose(dict);
                return false;
            }
        }
        else
        {
            hashtable[hash] = malloc(sizeof(strNode));
            hashtable[hash] = createStrNode(str);
            if (hashtable[hash] == NULL)
            {
                printf("Out of Memory\n");
                unload();
                fclose(dict);
                return false;
            }
        }
    }
    fclose(dict);
    return true;
}

Within the load function, I have called printf to check the value of the hash integer as well as the value of str. The entire dictionary with the distributed hashes prints normally.

Then, within the check function (not given here, it works), I have printed the hash and str values and they have come out as expected.

However, within my findStrNode function (see below), when I printf the val being compared with the linked-list value - the stored value is always the value of the last word in the dictionary, for every word.

Returns true if word is in dictionary else false

bool check(const char *word)
{
    int hash = hashString(word);
    bool found = findStrNode(hashtable[hash], word);
    return found;
}

Function for Finding a Particular Value within linked List of strings

bool findStrNode(strNode* head, const char* val)
{
    bool found = false;
    for (strNode* trav = head; trav != NULL; trav = trav->next)
    {
        // compare character by character tolowercase to see if string 
        // is found
        bool identical = true;
        bool keepGoing = true;
        int j = 0;
       // assume strings are identical until either reaching the end of 
       // one string or character are not the same
       // if we reach the end of both strings simultaneously, we should 
       // assume equality
       while (identical && keepGoing)
       {
           if (trav->value[j] == val[j] == '\0') {
               keepGoing = false;
           }
           if ((trav->value[j] == '\0' && val[j] != '\0') 
                || (trav->value[j] != '\0' && val[j] =='\0') 
                || (tolower(trav->value[j]) != tolower(val[j])))
           {
               identical = false;
           }
           j++;
        }
        // if identical is still true, then we have found an existing 
        // word
        if (identical)
        {
            found = true;
            break;
        }
    }
    return found;
};

I'm at a loss as to how my hash table saves the last dictionary value overtop of every other value in the hash-table. When I run this code outside of the context of this particular setup, it works perfectly. I can create, insert, find, and destroy my hash-table of linked-lists and I do not get this weird behavior. Please help!

Answer 1

You allocate space for one word. Then you copy its address to all your value pointers. Of course it's all the same word, as you re-use the same space all the time.

I used a char value[LENGTH + 1] instead, and strcpy. Or you could malloc a new one each time you fscanf.

You have multiple other problems in your code.

For example, in your check function, you seem to emulate what strcasecmp does. But is your hash the same in the first place? Do "DavidJMalan" and "DAVIDJMALAN" and "davidjmalan" all result in the same hash? (maybe you should create a lowercased copy first, you then could use strcmp instead of strcasecmp)

Then, after

hashtable[hash] = insertStrNode(hashtable[hash], str);

if the new node could not be allocated, you already overwrote your linked list with NULL, making the existing nodes unreachable, as you don't have any reference to them.

But wait, there's more memory leak.

        hashtable[hash] = malloc(sizeof(strNode));
        hashtable[hash] = createStrNode(str);

allocates a node and on the second line throws away the pointer, leaving the node unreachable.

if (trav->value[j] == val[j] == '\0')

doesn't exactly do what you want. It's the same as

if ((trav->value[j] == val[j]) == 0)

or

if ((trav->value[j] == val[j]) == false)

or

if (trav->value[j] != val[j])

You probably meant

if (trav->value[j] == '\0' || val[j] == '\0')

but it would have been easier to make your while loop a for loop, like

for (int j = 0; trav -> value[j] != '\0' || val[j] != '\0'; j++)
    // if different set identical=false and break

Or don't write the loop and use one of the strcmp-type functions.