0

After chasing down and eliminating memory leaks, I think I am getting close to finishing speller. So far, valgrind says no memory leaks, and the output is formatted correctly. However, when running my code on the cat.txt file to test, 'a' and 'A' are reported as misspelled. Debug50 shows that my load function is skipping over the 'a' in the dictionary file. I think this also has something to do with my converting the word to lowercase in the hash function, but I am not sure. No other post has been able to answer my question, so any advice is greatly appreciated!

My code in it's entirety is as follows:

// Implements a dictionary's functionality

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

#include "dictionary.h"

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

// Number of buckets in hash table - initially set to 1
const unsigned int N = 26; // 676;

// Hash table
node *table[N];

// global variable for counting number of words in dictionary
unsigned int word_counter = 0;

// Returns true if word is in dictionary, else false
bool check(const char *word)
{
    
    // obtain hash code for word
    unsigned int hcode = hash(word);
    
    // access hash table at index returned from hash function
    node *cursor = table[hcode]->next;

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

// the below is based on the sdbm hash function, with the parameters and some variable names changed to fulfill the requirements of this pset. all credit due to the creators of the sdbm hash function. source: https://www.programmingalgorithms.com/algorithm/sdbm-hash/c/
// Hashes word to a number
unsigned int hash(const char *word)
{
    unsigned int length = strlen(word);
    unsigned int hash = 0;
    
    // convert word to lowercase using tolower()
    int normalized_word[length];
    for (int j = 0; j < length; j++)
    {
        normalized_word[j] = tolower(word[j]);
    }
    
    // hash normalized word
    for (int i = 0; i < length; i++)
    {
        hash = (*normalized_word) + (hash << 6) + (hash << 16) - hash;
    }

    // starting below is my own addition to the sdbm hash function and not part of the original code

    if (hash > N)
    {
        hash = hash % N;
    }

    return hash;
}

// Loads dictionary into memory, returning true if successful, else false
bool load(const char *dictionary)
{
    // fopen dictionary, check if successful
    FILE *d = fopen(dictionary, "r");
        if (d == NULL)
        {
            printf("Unable to load dictionary. \n");
            return false;
        }

        // create array to read chars from dictionary into
        char dictword[LENGTH + 1];

        // read strings one at a time, until EOF
        char ch;
        while ((ch = fgetc(d)) != EOF)
        {
            fscanf(d, "%s", dictword);

            // create new node for each word
            node *n = malloc(sizeof(node)); // valgrind says memory leak is on this line
            if (n == NULL)
            {
                printf("Error.\n");
                return false;
            }
            // copy dictionary word into new node, set pointer to NULL
            strcpy(n->word, dictword);
            n->next = NULL;
            word_counter++;

            // run word through hash function and return hash code
            unsigned int hcode = hash(n->word);

            // if node is already present at index
            if (table[hcode] != NULL)
            {
                n->next = table[hcode];
                table[hcode] = n;
            }
            else
            {
                table[hcode] = n;
            }
        }
    fclose(d);
    return true;
}

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

// Unloads dictionary from memory, returning true if successful, else false
bool unload(void)
{
    for (int i = 0; i < N; i++)
    {
        // set two pointers to first element in linked list
        node *cursor = table[i];
        node *tmp = NULL;
        
        while (cursor != NULL)
        {
            tmp = cursor;
            cursor = cursor->next;
            free(tmp);
        }
    }
    return true;
}

When running ./speller texts/cat.txt, output is as follows:

MISSPELLED WORDS

A
a

WORDS MISSPELLED:     2
WORDS IN DICTIONARY:  143091
WORDS IN TEXT:        6
TIME IN load:         0.03
TIME IN check:        0.00
TIME IN size:         0.00
TIME IN unload:       0.00
TIME IN TOTAL:        0.03

Many thanks in advance!

1

I'm surprised there aren't more problems! Look at the following code:

    while ((ch = fgetc(d)) != EOF)
    {
        fscanf(d, "%s", dictword);

The while statement scans the first letter from each line in the input file. Next, the fscanf line scans the rest of the "current" line.

In the case of a dictionary where "A" is the entire line, the fgetc call will scan the A, and the fscanf will scan the second word. This is a unique case that happens each time a word is one letter long. It just happens to be the first line in your dictionary.

I would expect that when a word is more than one letter, it would essentially read and discard the first letter of each word and then put the rest of each word in a node. In other words, the only words that would be correctly placed in a dictionary are those that would follow a single letter word.

This is a common newbie mistake. Calling fgetc() to check for EOF doesn't simply check for EOF. It actually does a char read and moves the file position pointer to the next char, thus corrupting the logic.

Have you considered doing the fscanf inside the while statement? ;-)

There are more issues. When I run the code with my own small dictionary as both input and output, I get a seg fault. I've also found that it will incorrectly identify misspelled words as correct.

There may be more problems, but one question-one problem. ;-)

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

3
  • Your advice about fscanf worked a treat! I had the code the code that way earlier, but changed it for some reason. I'm not sure why you are receiving a segmentation fault, as I cannot recreate that on my end. Running the cat.txt, lalaland.txt, and austen.txt files output the same as the keys say they should show. The only way now that I know something is still not right is that check50 returns all red. I know I have more problems to address, but any suggestions on where I should focus my attention next?
    – Rachel D
    Jun 14 at 21:30
  • The seg fault happens when using a very small dictionary (like check50 uses for almost all tests.) If you always use the full dictionary, it won't show up. Try using the small dictionary as both dictionary and test file.
    – Cliff B
    Jun 14 at 21:40
  • 1
    Interesting, I don't get a seg fault while N = 26, but if I try to increase the size of the table then that will result in a seg fault. Using the small dictionary does show 'cat' and 'caterpillar' as being misspelled now, and valgrind says my memory leak is when I try opening the dictionary and when declaring a new node. Guess it's back to the drawing board for me.
    – Rachel D
    Jun 14 at 21:51

You must log in to answer this question.

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