Pset 5: Speller - Double free or corruption (fasttop) error

Question

Having to post a new question as the I reworked my code and space restrictions won't allow me to post it in the original thread.

I changed my code based on @CliffB 's suggestion. However, now I am getting a double free or corruption (fasttop) error. Here is my full code:

// Implements a dictionary's functionality

#include <cs50.h>
#include <ctype.h>
#include <stdbool.h>
#include <ctype.h>
#include <stdio.h>
#include <stdlib.h>
#include "dictionary.h"

// Represents a node in a hash table
typedef struct node
{
    char word[LENGTH + 1];
    struct node *next;
}
node;

// TODO: Choose number of buckets in hash table
const unsigned int N = 26;

// Hash table
node *table[N];

// prototypes
int strcasecmp(char *s1, const char *s2);
char *strcpy(char *dest, const char *source);

int word_count = 0;

// Returns true if word is in dictionary, else false
bool check(const char *word)
{
    // TODO
    // hash word through the hash function
    int index = hash(word);

    // traversal pointer
    node *tmp = table[index];

    while (tmp != NULL)
    {
        if (strcasecmp(tmp->word, word) == 0)
        {
            return true;
            break;
        }
        tmp = tmp->next;
    }
    return false;
}

// Hashes word to a number
unsigned int hash(const char *word)
{
    // TODO: Improve this hash function
    return toupper(word[0]) - 'A';
}

// Loads dictionary into memory, returning true if successful, else false
bool load(const char *dictionary)
{
    // TODO
    // initiate all node pointers to null
    for (int i = 0; i < N; i++)
    {
        table[i] = NULL;
    }

    // open the dictionary
    FILE *file = fopen(dictionary, "r");

    if (!file)
    {
        printf("Dictionary not found\n");
        return 1;
    }

    // check for a valid file pointer
    if (file == NULL)
    {
        fclose(file);
        printf("Could not open dictionary\n");
        return 2;
    }
    printf("Dictionary opened\n");

    // create an array of max length of word in dictionary
    char buffer[LENGTH + 1];

    // read words from the dictionary, one at a time using fscanf
    // fscanf inputs: file pointer, format and location in memory where it will place the scanned value
    while (fscanf(file, "%s", buffer) != EOF)
    {
        // allocate memory for one node
        node *n = malloc(sizeof(node));

        if (n == NULL)
        {
            printf("not enough memory for a node\n");
            return 3;
            break;
        }

        // copy scanned word into the node
        // and set its next pointer to null
        strcpy(n->word, buffer);
        n->next = NULL;

        // hash the word using the hash function
        int index = hash(n->word);

        // add node to the linked list
        if (table[index] == NULL)
        {
            table[index] = n;
            word_count++;
        }
        n->next = table[index];
        table[index] = n;
        word_count++;

        printf("%s\n", table[index]->word);

    }
    printf("%i\n", word_count);
    fclose(file);

    return true;
}

// Returns number of words in dictionary if loaded, else 0 if not yet loaded
unsigned int size(void)
{
    // TODO
    return word_count;
}

// Unloads dictionary from memory, returning true if successful, else false
bool unload(void)
{
    // TODO
    // loop over each linked list in the hash table
    for (int i = 0; i < N; i++)
    {
        while (table[i] != NULL)
        {
            node *tmp = table[i]->next;
            free(table[i]);
            table[i] = tmp;
        }
    }
    return true;
}

The load function loads the dictionary correctly (print statement inside it confirms this). However, the unload function returns a 'double free or corrupt (fasttop)' error. Valgrind points to this line: node *tmp = table[i]->next; (line 178)

Valgrind output:

==10050== Process terminating with default action of signal 2 (SIGINT)
==10050==    at 0x109BE4: unload (dictionary.c:178)

Where am I going wrong? Can someone please help?

One more question: I tried looping through the hash table and printing all the words that were loaded into it; however, I get stuck in an infinite loop after the last word ending with 'a', i.e. 'azusa'. Here is the code for printing the words:

for (int i = 0; i < N; i++)
{
    for (node *tmp = table[i]; tmp != NULL; tmp = tmp->next)
    {
        printf("%s\n", table[i]->word);
    }
}

Appreciate your help and advice.

Thanks!

Answer 1

Let's look carefully at this one. First, one has to figure out where the error occurs. Valgrind shows it to be line 148 in unload.

        node *tmp = table[i]->next;

Since this isn't a free() call, something is probably wrong with the tree, most likely table[i]->next. If you insert a print statement before this line and print out the address in table[i]->next, it shows the same address on 3 loop passes. Also, it never shows an address of nil, so it isn't getting to the end of the list, or the end of the list isn't right. Clearly something is wrong.

Best place to look is the code that builds the linked list. First, I'll note that the table[] array is properly initialized to NULL, so that's not the issue. Look at the following code that adds each new node to the linked list.

// add node to the linked list
    if (table[index] == NULL)
    {
        table[index] = n;
        word_count++;
    }
    n->next = table[index];
    table[index] = n;
    word_count++;

Now let's walk through the addition of the first node. The code hits the if statement. Since the condition is true, it inserts the first node correctly.

But what happens next? The code drops to the code that follows and inserts that same node a second time. It also sets the next pointer for the node to point back on itself. That means that instead of the end of the linked list pointing to NULL, it points back at itself and anything that tries to follow it will either loop back or hit an error, as is the case here.

BTW, the word count will be off by the number of non-null entires in table[]

In unload(), the code walks to the end of the list and deletes all the nodes. When it hits that last node, it deletes it and then circles back to try and access it again, but it's already been freed.

That, in a nutshell, is the problem.

There are a couple ways to fix this. One is to encapsulate the last 3 lines above in an else clause code block.

Another is more efficient. Why is an if or an if/else needed at all? Since the table[] array is initialized to null, those last 3 lines will always work on their own and the if statement and associated code block can just be deleted.

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