0

I am currently doing Speller. I have written all the functions and the program compiles but during self testing it is printing "misspelled words" and stays stuck at a blinking cursor. It completely freezes the terminal. I ran check50 to see if I could get any clues there and it sometimes has the correct misspelled words but on almost every test there it gives a "free(): double free detected in tcache 2". I figured that meant I was freeing some part of memory twice and tried a few adjustments in my unload function but it doesnt seem to be working right. I'll gladly take any pointers (haha puns). Also it appears my program doesnt recognize easy 3 letter words like "the". I would appreciate any advice. Below is my code included in its entirety:

// Implements a dictionary's functionality

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

//create integer to count amount of words in dictionary
int WORDCOUNT = 0;

// 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 = 610;

// Hash table
node *table[N];

// Returns true if word is in dictionary, else false
bool check(const char *word)
{
    //get the hash value of new word
    int hvalue = hash(word);
    //for each word at that hash value
    node *temp = table[hvalue];
    while(temp != NULL)
    {
        //check to see if the string match
        if (strcasecmp(word, temp->word) == 0)
            //if they match return true
        {
            return true;
        }
        else
        {
            temp = temp->next;
        }
    }
    //if none of the strings at the hash value match the word return false
    return false;
}

// Hashes word to a number
unsigned int hash(const char *word)
{
    //create integer
    int hash_value = 0;
    // look at first 5 letters of the word
    for(int x = 0; x < 5; x++)
    //make sure letter is lowercase and add value of letter to hash value
    {
        hash_value = hash_value + tolower(word[x]);
    }
    //return hash value
    return hash_value;
}

// Loads dictionary into memory, returning true if successful, else false
bool load(const char *dictionary)
{
    //Establishes buffers to load dictionary onto
    char next_word[LENGTH + 1];
    // open dictionary file to read
    FILE *dic = fopen(dictionary, "r");

    //if file is unable to open return false
    if (!dic)
    {
        printf("Error Unable to Open File");
        return false;
    }
    //read each string from dictionary
    while(fscanf(dic, "%s", next_word) != EOF)
    {

        //create node for new word
        node *newword = malloc(sizeof(node));
        //if new node is null return false
        if (!newword)
        {
            return false;
        }
        //copy string from file into buffer
        else
        {
            strcpy(newword->word, next_word);
            newword->next = NULL;

            //hash word to obtain hash value
            int hashed = hash(next_word);

            if(table[hashed] == NULL)
            {
                //insert node into hash table
                table[hashed]  = newword;
                WORDCOUNT++;
            }
            if(table[hashed] != NULL)
            {
                WORDCOUNT++;
                newword->next = table[hashed];
                table[hashed] = newword;
            }
        }
    }
    //close file
    fclose(dic);
    return true;

}

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

    // returns word count
    return WORDCOUNT;
}

// Unloads dictionary from memory, returning true if successful, else false
bool unload(void)
{
    node *temp = NULL;
    node *nextvalue = NULL;
    // loop over each number in hash table
    for(int x = 0; x < N - 1; x++)
    {
        //create temp pointer to first value at hash table
        temp = table[x];
        //loop over each word saved at hash value
        while(temp != NULL)
        {
            //create "curser" that points at next value
            nextvalue = temp->next;
            //free temp
            free(temp);
            temp = nextvalue;
        }
    }
    return true;
}

1 Answer 1

1

This is a bug well hidden in plain sight. ;-) If you traced the program in debug, it runs all the way through to the unload() function, inside the while loop. It's failing when it hits the end of the first linked list that it processes.

This is a big clue. If you look closer, you see that when the code gets to the end of the first linked list, the address in the next field is the same as the current node. This means that there's a problem with the way the first node is added to any linked list in the tree. That means the problem lies in the load() function.

Now, look at this code from the while loop and think carefully how it is processed:

        if(table[hashed] == NULL)
        {
            //insert node into hash table
            table[hashed]  = newword;
            WORDCOUNT++;
        }
        if(table[hashed] != NULL)
        {
            WORDCOUNT++;
            newword->next = table[hashed];
            table[hashed] = newword;
        }

When the first if code block is processed, it sets table[hashed] to a non-null value. Now, think very carefully. Will the next if statement be true or false? What is stored in table[hashed] at this point? Null or the address of the node just created? The short version is that the second if statement will ALWAYS execute, no matter if the first one does or not.

Maybe the second if statement should be changed to something else??? ;-)

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

1
  • And here's a challenge. Can you figure out how to remove both if statements and do the same processing? It is possible in 3 lines!
    – Cliff B
    Jul 27, 2021 at 19:21

You must log in to answer this question.

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