0

I have been wandering through the code and forums for couple of hours now and I will be glad if you point out what I am doing wrong.

So, first of all, all checks I have made in the workspace passed. Valgrind says everything was freed and my output is identical to the output of staff (with the exception of run-time of course :) ).

But when I send the code to check50, it uploads but it seems to not produce any text output which check50 needs. Code compiles and dies after that.

Here is the link i got from check50: https://cs50.me/checks/ecb007611a9d8d6576f37a54e791c383584468d6

I would be glad if anyone could check the code because me and my duck can't find anything. It is really hard to zero out the error when check50 does give any valid output :/

Source codes are below, aswell as valgrind output. I used trie to store the dictionary.

Thank you for any effort! :)

/** * Implements a dictionary's functionality. */

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

#include "dictionary.h"

/**
 *
 */
dictNode * GetNode (void) {
    dictNode * newNode = malloc(sizeof(dictNode));
    for(int i = 0; i < ALPHABET_SIZE; i++) {
        newNode->alphabet[i] = NULL;
        newNode->isEndOfWord = false;
    }
    return newNode;
}
/**
 *
 */
void InsertKey(dictNode *head, char *key) {
    dictNode * traversePointer = head;
    for(int i = 0; i < strlen(key); i++) {
        if(*(key + i) == '\'') {
            if ((traversePointer->alphabet[26]) == NULL) {
                traversePointer->alphabet[26] = GetNode();
                traversePointer = traversePointer->alphabet[26];
            }
            else {
                traversePointer = traversePointer->alphabet[26];
            }
        }
        else if (*(key + i) >= 'a' || *(key + i) <= 'z') {
            if ((traversePointer->alphabet[*(key + i) - 'a']) == NULL) {
                traversePointer->alphabet[*(key + i) - 'a'] = GetNode();
                traversePointer = traversePointer->alphabet[*(key + i) - 'a'];
            } else {
                traversePointer = traversePointer->alphabet[*(key + i) - 'a'];
            }
        }
    }
    traversePointer->isEndOfWord = true;
}

bool FreeTrie(dictNode * traverse) {

    if (traverse == NULL) return true;

    for (int i = 0; i < 27; i++) {
        FreeTrie(traverse -> alphabet[i]);
    }

    free (traverse);
    return true;
}

bool CheckDict(dictNode * head, const char * key) {
    char keyLower[LENGTH];
    for(int i = 0; key[i]; i++) {
        keyLower[i] = (char)tolower(key[i]);
    }
    dictNode * traversePointer = head;
    for(int i = 0; i < strlen(key); i++) {
        if (*(keyLower + i) == '\'') {
            if(traversePointer -> alphabet[26] == NULL) {
                return false;
            } else {
                traversePointer = traversePointer -> alphabet[26];
            }
        } else {
            if((traversePointer -> alphabet[*(keyLower + i) - 'a']) == NULL) {
                return false;
            } else {
                traversePointer = traversePointer -> alphabet[*(keyLower + i) - 'a'];
            }
        }
    }
    if (traversePointer -> isEndOfWord == true) {
        return true;
    } else {
        return false;
    }
}

/**
 * Returns true if word is in dictionary else false.
 */
bool check(const char *word)
{
    return CheckDict(trieHead, word);
}

/**
 * Loads dictionary into memory. Returns true if successful else false.
 */
bool load(const char *dictionary2) {
    FILE *inFile = fopen(dictionary2, "r");
    if (inFile == NULL) {
        return false;
    }

    char character = 0;
    while( character != EOF) {
        char buffer[LENGTH];
        charCounter = 0;
        while((character = fgetc(inFile)) != '\n' && (character != EOF))
        {
            buffer[charCounter++] = character;
            //printf("%c", character);
            //printf("Char counter is %d \n", charCounter);
        }
        buffer[charCounter] = '\0';
        if (strlen(buffer) >= 1) {
            InsertKey(trieHead, buffer);
        }
        //printf("%s \n", buffer);
    }
    fclose(inFile);
    return true;
}

/**
 * Returns number of words in dictionary if loaded else 0 if not yet loaded.
 */
unsigned int size(void)
{
    unsigned int count = CheckSize(trieHead);
    if (count) {
        return count;
    } else {
        return 0;
    }
}

unsigned int CheckSize(dictNode * traversePointer) {

    if(traversePointer == NULL) return 0;


    unsigned int count = 0;

    for (int i = 0; i < 27; i++) {
        count += CheckSize(traversePointer -> alphabet[i]);
    }

    if (traversePointer -> isEndOfWord) {
        return count + 1;
    } else {
        return count;
    }
}

/**
 * Unloads dictionary from memory. Returns true if successful else false.
 */
bool unload(void)
{
    return FreeTrie(trieHead);
}

/** * Implements a spell-checker. */

#include <ctype.h>
#include <stdio.h>
#include <sys/resource.h>
#include <sys/time.h>

#include "dictionary.h"
#undef calculate
#undef getrusage

// default dictionary
#define DICTIONARY "dictionaries/large"

// prototype
double calculate(const struct rusage *b, const struct rusage *a);


int main(int argc, char *argv[])
{
    // check for correct number of args
    if (argc != 2 && argc != 3)
    {
        printf("Usage: speller [dictionary] text\n");
        return 1;
    }

    // structs for timing data
    struct rusage before, after;

    // benchmarks
    double time_load = 0.0, time_check = 0.0, time_size = 0.0, time_unload = 0.0;

    // determine dictionary to use
    char* dictionary = (argc == 3) ? argv[1] : DICTIONARY;

    // load dictionary
    trieHead = GetNode();
    getrusage(RUSAGE_SELF, &before);
    bool loaded = load(dictionary);
    getrusage(RUSAGE_SELF, &after);

    // abort if dictionary not loaded
    if (!loaded)
    {
        printf("Could not load %s.\n", dictionary);
        return 1;
    }

    // calculate time to load dictionary
    time_load = calculate(&before, &after);

    // try to open text
    char *text = (argc == 3) ? argv[2] : argv[1];
    FILE *fp = fopen(text, "r");
    if (fp == NULL)
    {
        printf("Could not open %s.\n", text);
        unload();
        return 1;
    }

    // prepare to report misspellings
    printf("\nMISSPELLED WORDS\n\n");

    // prepare to spell-check
    int index = 0, misspellings = 0, words = 0;
    char word[LENGTH+1];

    // spell-check each word in text
    for (int c = fgetc(fp); c != EOF; c = fgetc(fp))
    {
        // allow only alphabetical characters and apostrophes
        if (isalpha(c) || (c == '\'' && index > 0))
        {
            // append character to word
            word[index] = c;
            index++;

            // ignore alphabetical strings too long to be words
            if (index > LENGTH)
            {
                // consume remainder of alphabetical string
                while ((c = fgetc(fp)) != EOF && isalpha(c));

                // prepare for new word
                index = 0;
            }
        }

        // ignore words with numbers (like MS Word can)
        else if (isdigit(c))
        {
            // consume remainder of alphanumeric string
            while ((c = fgetc(fp)) != EOF && isalnum(c));

            // prepare for new word
            index = 0;
        }

        // we must have found a whole word
        else if (index > 0)
        {
            // terminate current word
            word[index] = '\0';

            // update counter
            words++;

            // check word's spelling
            getrusage(RUSAGE_SELF, &before);
            bool misspelled = !check(word);
            getrusage(RUSAGE_SELF, &after);

            // update benchmark
            time_check += calculate(&before, &after);

            // print word if misspelled
            if (misspelled)
            {
                printf("%s\n", word);
                misspellings++;
            }

            // prepare for next word
            index = 0;
        }
    }

    // check whether there was an error
    if (ferror(fp))
    {
        fclose(fp);
        printf("Error reading %s.\n", text);
        unload();
        return 1;
    }

    // close text
    fclose(fp);

    // determine dictionary's size
    getrusage(RUSAGE_SELF, &before);
    unsigned int n = size();
    getrusage(RUSAGE_SELF, &after);

    // calculate time to determine dictionary's size
    time_size = calculate(&before, &after);

    // unload dictionary
    getrusage(RUSAGE_SELF, &before);
    bool unloaded = unload();
    getrusage(RUSAGE_SELF, &after);

    // abort if dictionary not unloaded
    if (!unloaded)
    {
        printf("Could not unload %s.\n", dictionary);
        return 1;
    }

    // calculate time to unload dictionary
    time_unload = calculate(&before, &after);

    // report benchmarks
    printf("\nWORDS MISSPELLED:     %d\n", misspellings);
    printf("WORDS IN DICTIONARY:  %d\n", n);
    printf("WORDS IN TEXT:        %d\n", words);
    printf("TIME IN load:         %.2f\n", time_load);
    printf("TIME IN check:        %.2f\n", time_check);
    printf("TIME IN size:         %.2f\n", time_size);
    printf("TIME IN unload:       %.2f\n", time_unload);
    printf("TIME IN TOTAL:        %.2f\n\n",
     time_load + time_check + time_size + time_unload);

    // that's all folks
    return 0;
}

/**
 * Returns number of seconds between b and a.
 */
double calculate(const struct rusage *b, const struct rusage *a)
{
    if (b == NULL || a == NULL)
    {
        return 0.0;
    }
    else
    {
        return ((((a->ru_utime.tv_sec * 1000000 + a->ru_utime.tv_usec) -
                 (b->ru_utime.tv_sec * 1000000 + b->ru_utime.tv_usec)) +
                ((a->ru_stime.tv_sec * 1000000 + a->ru_stime.tv_usec) -
                 (b->ru_stime.tv_sec * 1000000 + b->ru_stime.tv_usec)))
                / 1000000.0);
    }
}

/** * Declares a dictionary's functionality. */

#ifndef DICTIONARY_H
#define DICTIONARY_H

#include <stdbool.h>

// maximum length for a word
// (e.g., pneumonoultramicroscopicsilicovolcanoconiosis)
#define LENGTH 45
#define ALPHABET_SIZE 27

/**
 *
 */
typedef struct dictStruct {
    struct dictStruct *alphabet[ALPHABET_SIZE];
    struct dictStruct *parent;
    bool isEndOfWord;
} dictNode;


int charCounter;
int debugCounter;
dictNode * trieHead;


/**
 * Returns true if word is in dictionary else false.
 */
bool check(const char *word);

/**
 * Loads dictionary into memory. Returns true if successful else false.
 */
bool load(const char *dictionary);

/**
 * Returns number of words in dictionary if loaded else 0 if not yet loaded.
 */
unsigned int size(void);

/**
 * Unloads dictionary from memory.  Returns true if successful else false.
 */
bool unload(void);


/**
 *
 */
dictNode * GetNode (void);

/**
 *
 */
bool CheckDict(dictNode * head, const char * key);

unsigned int CheckSize(dictNode * traversePointer);
#endif // DICTIONARY_H

Valgrind output "./speller texts/austinpowers.txt"

1

It crashes for me when I try to run this.

The issue is in load:

InsertKey (head=0x0, key=0x7fffffffd9f0 "a") at dictionary.c:40

line 40 is: if ((traversePointer->alphabet[*(key + i) - 'a']) == NULL) {

traversePointer is NULL at this point, so you can't dereference it to access the alphabet element. If you try to dereference a NULL pointer, you will get a segfault.

I'm surprised that it worked on your IDE.

1
  • I have found the mistake, thanks to you. Much obliged! – soulwriter Dec 17 '17 at 11:12
0

tldr: Moved trieHead initialization into dictinary.c

Ok. I have found the mistake. I thought the check50 uploads and checks all three files speller.c, dictionary.c and dictionary.h

I have made one small addition to speller.c I initialized the head of the trie there...

trieHead = GetNode();

So when check50 was going through my code, it did not have the pointer to the trieHead because it did not have it initialized in speller.c which I had in my workspace, therefore it worked only locally.

You must log in to answer this question.

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