3

EDIT: Fixed the problem. The issue was not with the check or unload function but with the load function which had a small but very significant logic error. Figured it out with some great help from a CS50 community member

I've been working on speller for the last couple of weeks and have not been able to successfully run the code on large texts. I would really appreciate any help since I'm feeling completely helpless having tried everything I possibly could.

The program compiles fine. When I run the program, I seem to have issues with the unload function and the check function. The unload function gives me an error "double free or corruption (fasttop)\n Aborted". The check function works fine for the small texts/cat.txt file but for longer texts seems to go on endlessly without ever finding the misspelled words.

It's possible that there could be a problem with my load or hash functions though I think that's not where the problem lies.

I'm sharing the code my code for your reference. I would appreciate any help!

// Implements a dictionary's functionality

#include <stdbool.h>

#include "dictionary.h"

#include <stdio.h>
#include <stdlib.h>
#include <ctype.h>
#include <string.h>
#include <strings.h> //use strcasecmp to compare two strings case sensitively

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

// Number of buckets in hash table
const unsigned int N = 26;

// Hash table
node *table[N];

int wordcount = 0;

// Returns true if word is in dictionary else false
bool check(const char *word)
{
    // TODO
    int hindex = hash(word);
    node* cursor = table[hindex];
    while(cursor != NULL)
    {
        if(strcasecmp(cursor->word, word) == 0)
        {
            //printf("Word *%s* FOUND in dictionary (TRUE)\n", cursor->word);
            return true;
        }
        cursor = cursor->next;
    }
    //printf("Word *%s* NOT FOUND in dictionary (FALSE)\n", word);
    return false;
}

// Hashes word to a number
unsigned int hash(const char *word)
{
    // TODO
    int hashindex = (tolower(word[0]) - 'a') % 26;
    return hashindex;
}

// Loads dictionary into memory, returning true if successful else false
bool load(const char *dictionary)
{
    // TODO
    //open dictionary file for reading
    FILE* dict = fopen(dictionary, "r");

    //buffer to read file into
    char dictword[LENGTH + 1];

    //scan dict file until end of file for each word of [LENGTH + 1] length and store in buffer called dictword
    while(fscanf(dict, "%s", dictword) != EOF)
    {
        //allocate memory for a new node to save dictionary word into
        node* newnode = malloc(sizeof(node));

        //copy word from buffer to node
        strcpy(newnode->word, dictword);

        //word counter increments after word is copied into the node
        wordcount++;

        //dictionary word is hashed to determine the hash index for the linked list it will be attached to
        int haindex = hash(dictword);

        //if the hashtable index is not pointing to anything making it point to the new node and the new node next to NULL.
        if (table[haindex] == NULL)
        {
            table[haindex] = newnode;
            newnode->next = NULL;
        }
        //if the hashtable index is already pointing to a node, then make the new node point to what hash table index is pointing at (contd.) (1/2)
        // then reset the hashtable to point to the next node (2/2)
        if (table[haindex] != NULL)
        {
            newnode->next = table[haindex];
            table[haindex] = newnode;
        }
        //printf("\nword *%s* added to dictionary with hash value: *%i*\n", newnode->word, haindex);
    }
    //printf("\ndictionary loaded successfully\n");
    //close dictionary file
    fclose(dict);
    return true;
    //return wordcount;
}

// Returns number of words in dictionary if loaded else 0 if not yet loaded
unsigned int size(void)
{
    // TODO
    //printf("Dictionary word count: %i\n", wordcount);
    return wordcount;
}

// Unloads dictionary from memory, returning true if successful else false
bool unload(void)
{
    // TODO
    for (int i = 0 ; i < N ; i++)
    {
        node* cursor = table[i];
        node* temp = NULL;
        while (cursor != NULL)
        {
            temp = cursor;
            cursor = cursor->next;
            free(temp);
        }
    }
    return true;
}
2
  • Hi. Since you've shared effectively all the code, can you please edit the question and just put the entire code in so that we can copy it out for testing? thanks.
    – Cliff B
    May 5 '20 at 18:57
  • Thanks, @CliffB for responding! I've updated the post to reflect my code. Any help would be much appreciated. Thank you! May 5 '20 at 19:02
1

This is a good lesson for all! I can completely understand your frustration!!!

This is a very interesting problem because it is a pure logic error. Most problems on this forum are due to syntax or incorrect usage of a function. This is the exception. It's a well hidden, in plain sight logic flaw. It's also the cause of all the issues in this code. The lesson here is that one simple error can cause all kinds of problems in other areas without causing any issues where it is and leaving only faint clues!

The problem actually lies in the load function!

Load appears to be working fine, but check and unload appear broken. Check works fine for words that are in the dictionary, but goes into an infinite loop for misspelled words that don't appear in the dictionary. Unload fails because it can't find the end of the linked list. Are you getting any suspicions yet? ;-)

The problem is that the last node in each linked list in the tree is supposed to have node->next = NULL, but it doesn't. Why?

Look at this code (comments removed):

    if (table[haindex] == NULL)
    {
        table[haindex] = newnode;
        newnode->next = NULL;
    }

    if (table[haindex] != NULL)
    {
        newnode->next = table[haindex];
        table[haindex] = newnode;
    }

The intent was to have two cases - one to handle the first node added, the other to handle all other cases. Note that these should be two mutually exclusive cases. This should have correctly set the needed NULL.

Here's the problem. The code uses two IF statements that are fully decoupled. After the first if but before the second if, what is the value of table[index]? It has just been set to something valid and not null. Because of this, both if statements will be executed when the first node is added. After both execute, there will be two duplicate nodes in the list (or more specifically, pointers to the same node). That will produce a circular pointer at the end - the last node points back at itself instead of pointing to NULL.

So what's the fix? The best fix is easy. Instead of two IF statements, it should be an if/else construct. That would guarantee that only one of the two code blocks could possibly be executed and would absolutely couple the conditions together.

It could be fixed by reversing the order of the two if statements and their code blocks (it would work correctly) but that would be a bad practice. If the code were to be edited at a later date, it wouldn't be clear that the two conditions are coupled. Also, it's less efficient - two conditions need to be tested and processed instead of one.

How does this affect unload()? Unload will get to the last node that points back to itself. It saves the address of that last node as the next node to be deleted and deletes it the first time successfully. Then, it tries to delete the same address again, but it's already deleted! That's a classic double-free.

So, a very simple oversight - using two ifs instead of if/else - caused immense problems in two other functions without really signaling a problem where it really exists. This does happen more often than you'd imagine, so thoroughly understanding it is a tremendous debugging skill!

Happy programming! ;-)

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

3
  • I literally cried when I saw your answer. Thank you so much for your help! I had to stare at your answer a few times to actually understand where the mistake was. I'm still not 100% sure if my if/esle construction worked. Is it ok if I DM you if/else code? I'm not sure if I will be violating the academic honesty code? May 5 '20 at 21:11
  • If you did as I said - delete the second if statement line and just replace with else, then it looks like it worked fine. I actually tested it in my IDE. If you still want to DM me, I'm on slack.
    – Cliff B
    May 5 '20 at 21:14
  • 1
    I guess there is no way to DM but I played around with the code and figured out the if/else construction. Thank you so much again! I will remember this important lesson for a long time. May 5 '20 at 21:27

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .