Pset5 Speller - Weird Load Function Bug (Edited w/ Code)

Question

bool load(const char *dictionary)
{
    // TODO
    FILE *fdict = fopen(dictionary, "r");
    if (fdict == NULL)
    {
        return false;
    }

    // create container string to hold word
    char *string = malloc(sizeof(LENGTH+1));
    if (string == NULL)
    {
        return false;
    }

    // initialize new node
    node *n = malloc(sizeof(node));
    if (n == NULL)
    {
        return false;
    }

    //condition begins by scanning file
    while (fscanf(fdict, "%s", string) != EOF)
    {
        // assign values to n
        n->next = NULL;
        strcpy(n->word, string);

        // obtain hashcode for table
        int hcode = hash(n->word);

        // if no elements at hcode, fill with n. else, attatch table[hcode] as next and slot n as table[hcode].
        if (table[hcode] == NULL)
        {
            table[hcode] = n;
        }
        else
        {
            n->next = table[hcode];
            table[hcode] = n;
        }
        count++;

        n = malloc(sizeof(node));
    }

    free(n);
    //n = NULL;
    free(string);
    fclose(fdict);
    return true;
} 

Load() was working perfectly, except that it would not load the first word in the large dictionary, "a". I debugged for a bit and found that after initiating fscan() at the point in the loop where the longest word ("pneumonoultramicroscopicsilicovolcanoconiosis") would be scanned by fscan(), the last 12 characters of the longest word would immediately replace "a" where it existed in its linked list on the hash table before any data is actually allocated into a linked list.

Node before error:

Node after scanning long word:

The memory address remains the same, for all intents and purposes it is the same node, but now the n->word value would be changed to "lcanoconiosis". Does anyone know what might cause this? I'm completely at a loss, as nothing touches the hash table at this point in the loop. Theoretically I could hardcode an exception in check() to always count "a", but I'd rather know what's happening in case this happens again.

EDIT: included text of code instead of code screenshot (10/5/23)

Answer 1

I suspect that this problem exists with each and every linked list that the table[] elements point to. (i.e., if the hash value is the first letter of each word, the first word in the dictionary file for each letter fails to show up in the table array.)

It would have been helpful to see the declaration of table, but I'll assume that it's the standard array of pointers to nodes.

The problem is that an important step is missing from the code. Look at this from your code:

// if no elements at hcode, fill with n. else, attatch table[hcode] as next and slot n as table[hcode].
    if (table[hcode] == NULL)
    {
        table[hcode] = n;
    }

The problem is that table[] is not initialized. When an array of pointers is declared, the array elements are NOT set to null by default. Instead, they contain whatever garbage data was left in physical memory. Since this is NOT NULL, the if test fails and the code assumes that there's a node there already.

So, the code goes to the else block, gets n->next, which is NULL and puts it in as the new node at the front of the list. The next node to be added will see that the first node is null now, and will insert the second node as the first node in the list. From here on, everything works as it should.

Simply put, every node in table MUST be set to NULL manually, using a for loop before table can be used and populated with live data.

Best practice: Pointers of any type should ALWAYS be immediately manually initialized, no matter what, either with NULL or live data at the time of their creation, to prevent this exact issue.

If this answers your question, please click on the check mark to accept. Let's keep up on forum maintenance. ;-)