Get a MISSPELLED WORD memory error from check50 PSET5

Question

I've gone through other threads but can't find what the problem is. I don't see any errors when I run valgrind but when running check50 for PSET5 get the following error:

Cause Did not find "MISSPELLED WOR..." in "tput: No value..." Log running valgrind --show-leak-kinds=all --xml=yes --xml-file=/tmp/tmph519di5q -- ./speller substring/dict substring/text... checking for output "MISSPELLED WORDS\n\nca\ncats\ncaterpill\ncaterpillars\n\nWORDS MISSPELLED: 4\nWORDS IN DICTIONARY: 2\nWORDS IN TEXT: 6\n"...

Could not find the following in the output: MISSPELLED WORDS

ca cats caterpill caterpillars

WORDS MISSPELLED: 4 WORDS IN DICTIONARY: 2 WORDS IN TEXT: 6 Actual Output: tput: No value for $TERM and no -T specified tput: No value for $TERM and no -T specified MISSPELLED WORDS

ca cats caterpill caterpillars

My code is:

// Implements a dictionary's functionality

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

#include "dictionary.h"

// count total words in dictionary, updated in hash function
int word_total = 0;

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

int getCount(struct node* head);

// TODO: Choose number of buckets in hash table - adjust to get optimal performace (speed),
const unsigned int N = 120000000;

// Hash table
node *table[N];

// Returns true if word is in dictionary, else false
bool check(const char *word)
{
    // TODO

    int hash_no = hash(word);
    // test function - printf("word hash: %i\n", hash_no);

    // see if hash in table
    // set tempN node to compare
    node *tempN = table[hash_no];
    while (tempN != NULL)
    {
        if (strcasecmp(word, tempN->word) == 0)
        {
            return true;
        }
        tempN = tempN->next;
    }
    return false;
}

// Hashes word to a number
unsigned int hash(const char *word)
{
    // to upper case
    char temp[LENGTH + 1];
    strcpy(temp, word);

    for (int i = 0; i < strlen(temp); i++)
    {
        temp[i] = toupper(temp[i]);
    }

    // TODO: Improve this hash function,
    int len = strlen(temp);
    int value = 1;
    for (int i = 0; i < len; i++)
    {
        if (i == len - 1 || i > 4)
        {
            break;
        }
        else
        {
            value = (value + temp[i]) / len;
        }
    }
    return value;
}

// Loads dictionary into memory, returning true if successful, else false
bool load(const char *dictionary)
{
    // set memory for each node

    char newword[LENGTH + 1];
    FILE *dict = fopen(dictionary, "r");
    if (dict == NULL)
    {
        printf("dictionary not found\n");
        return false;
    }

    while (fscanf(dict, "%s", newword) != EOF)
    {
        node *n = malloc(sizeof(node));
        if (n == NULL)
        {
            printf("not enough memory\n");
            fclose(dict);
            return false;
        }

        strcpy(n->word, newword);
        int hash_loc = hash(n->word);
        if (!check(n->word))
        {
            n->next = table[hash_loc];
            table[hash_loc] = n;
            word_total++;
        }
        else
        {
            // Word already exists, free the node
            free(n);
        }
    }
    fclose(dict);
    return true;
}

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

// 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];
        while (cursor != NULL)
        {
            node *ptr = cursor->next;
            free(cursor);
            cursor = ptr;
        }
    }
    return true;
}

Any hints on areas to look at would be appreciated.

Answer 1

Some problems.

1. Your N is way too large to be done on the heap like this. 120 Million pointers to nodes is a much bigger heap allocation that I would suggest making. That's going to be about 1GB on the heap. I wouldn't recommend that.

2. your unload has no false return path; given it's a boolean function that should return false on failure you should have a case for failure in which it would return false. It also does not update size/word_total which it really should on success.

3. Your hash function doesn't make use of N to guarantee that you will produce a safe index into tables. You should probably return value % N. Also while you are at it, suggest computing strlen in the function only once; so move int len = strlen(...); above the strcpy and just perform it on word instead of temp and make it a const. Not sure why you are adding the condition of i == len - 1 into the loop as that read won't be a problem since you have i < len. for example if temp is "ABCDE" its strlen is 5, i < len means i < 5 means max i is 4, i[4] is 'E' so you are fine. I would put the i > 4 piece of the check into the loop bounds. so i < len && i <= 4. Also even if every letter you encountered has max ascii value of 255, because of your division you will never get an end value greater than 255. So your N value is needlessly large.

4. Your comment is wrong in introducing word_count you update the count in load not hash. ( which is a good thing ) you should update or remove that comment.

5. I would walk through your program and use the examples they gave you. Test the output for matches with the provided samples. Do they match? Ignore valgrind for a moment. Quite literally look at the hints section into the Testing section and carry out the tests they suggest. what are your results?

6. if you are on the 2023 version at least the specs say they wont duplicate words in the dictionary provided, so you don't have to call check from hash. not life changing but it will speed up things for you.