PSET5: Missing Words from Text and Memory Leaks

Question

UPDATE: I just fixed the capitalized spell-checking errors.

UPDATE 2: free didn't totally free the string "caterpillar". Look at image:

My code seems to encounter a weird bug where it does not count the number of words in a text file correctly. However, it can correctly count the number of words in the dictionary. In my example I made a custom sample.txt file containing the words Cat, cetarpilar, Caterpillar, and xss. When run the results show that there are 3 words in the text rather than 4. It can correctly detect cetarpilar as the misspelled word but not xss.

When I run check50, it seems evey thing is correct aside from memory leaks. What am I missing here?

Here is my code:

// Implements a dictionary's functionality

#include <stdbool.h>

#include <stdio.h>

#include <stdlib.h>

#include <string.h>

#include <strings.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
const unsigned int N = 26;

// Hash table
node *table[N];

// Number of words in dictionary:
unsigned int numWords = 0;

// Returns true if word is in dictionary else false
bool check(const char *word)
{
    int pos = hash(word);

    node *tmp = table[pos];

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

        tmp = tmp->next;
    }

    return false;
}

// Hashes word to a number
unsigned int hash(const char *word)
{
    int first = word[0];

    if (first < 123 && first > 96)
    {
        return first;
    }

    return first + 32;
}

// Loads dictionary into memory, returning true if successful else false
bool load(const char *dictionary)
{
    FILE *fDict = fopen(dictionary, "r");

    if (fDict == NULL)
    {
        return false;
    }

    // Longest word in the english dictionary is
    // "pneumonoultramicroscopicsilicovolcanoconiosis"
    // which has 45 characters. This length is stored
    // as a constant in dictionary.h as "LENGTH"

    // fscanf(*file, "%s\n", word of size LENGTH)
    // REMEMBER: Whenever you use file operation functions,
    // the file cursor will move to a new line. So when you
    // use feof remember to push the cursor back one line.

    char word[LENGTH+1];
    int ifEOF = fscanf(fDict, "%s", word);

    while (ifEOF > 0)
    {
        int pos = hash(word);

        node *n = malloc(sizeof(node));
        strcpy(n->word, word);

        if (table[pos] == NULL)
        {
            table[pos] = n;
        }
        else
        {
            n->next = table[pos];
            table[pos] = n;
        }

        ifEOF = fscanf(fDict, "%s", word);

        numWords++;
    }

    fclose(fDict);

    return true;
}

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

// Unloads dictionary from memory, returning true if successful else false
bool unload(void)
{
    for (int i = 0; i < N; i++)
    {
        if (table[i] != NULL)
        {
            node *tmp = table[i];
            node *cursor = table[i];

            while (cursor != NULL)
            {
                cursor = cursor->next;
                free(tmp);
                tmp = cursor;
            }

            free(tmp);
            free(cursor);
        }
    }

    for (int j = 0; j < N; j++)
    {
        if (table[j] != NULL)
        {
            return false;
        }
    }

    return true;
}

Answer 1

I'm surprised it didn't seg fault. The hash function generates results > N. That means that it's creating entries in the table[] array beyond it's range.

When unload runs, it's not finding the table entries that were created out of range.

As for the discrepancy in the word counts, does your sample text test file have a blank line at the end? It needs to. It's a unique issue in the distro code that it doesn't count the last line unless it ends with a line feed.

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