3
\$\begingroup\$

This is a program that loads a dictionary into a hash-table, and spell checks a text file provided as a command-line argument. The dictionary is formatted as such (just alphabetically):

python
bar
foo
code
review

When the program is done I am provided with output that looks like : Output


This is part of a problem set where I was handed a base to build atop of (speller.c), which I'll provide below but am not looking for input on. Despite the goal being to create the most efficient and fastest code possible, I'd rather have input mostly focused on my code-style in forms such as readability and commenting. Again, if you decide to read through speller.c, please do not focus your critique on as it was not written by me.

Some of the requirements are:

  • You may assume that any dictionary passed to your program will be structured exactly like ours, lexicographically sorted from top to bottom with one word per line, each of which ends with \n. You may also assume that dictionary will contain at least one word, that no word will be longer than LENGTH (a constant defined in dictionary.h) characters, that no word will appear more than once, and that each word will contain only lowercase alphabetical characters and possibly apostrophes.
  • You may assume that check will only be passed strings with alphabetical characters and/or apostrophes.
  • Your implementation of check must be case-insensitive.

speller.c

#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
    getrusage(RUSAGE_SELF, &before);
    bool loaded = load(dictionary); // THIS IS LOAD
    getrusage(RUSAGE_SELF, &after);

    // abort if dictionary not loaded
    if (!loaded)
    {
        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);
    }
}

dictionary.c

/*
* dictionary.c
* Implements speller.c's functionality
*/

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

#include "dictionary.h"


// Global variables and arrays for simple access
char buffer[LENGTH+1] = {'\0'}; // Declares the buffer to store one line or one word in total
unsigned int wordcount = 0;
int hash_index;

node* hashtable[HASHTABLE_SIZE] = {NULL}; // Stores pointer to node datatype
node* current_head_node;  // Will always be the current node, or first in a linked list
FILE* dictionary_ref;


/**
 * Returns true if word is in dictionary else false.
 */
bool check(const char* word)
{
    // Load word into buffer, and convert it to lower
    for (int i = 0, wordlen = strlen(word); i < wordlen; i++) {
        buffer[i] = tolower(word[i]);
        buffer[i+1] = '\0'; // Make sure the word gets terminated
    }

    // Figure out where word in buffer belongs, and make head node to point there
    hash_index = hash(buffer);
    current_head_node = hashtable[hash_index];

    // Iterate through a linked list
    while (current_head_node != NULL) {

        // Check if word in buffer is also in dictionary
        if (strcmp(buffer, current_head_node->word) == 0) {
            swap(&current_head_node, &hashtable[hash_index]);
            return true;
        }

        // Go to next node
        current_head_node = current_head_node->next;
    }

    return false;
}

 /**
 * Loads dictionary into memory. Returns true if successful else false.
 */
bool load(const char* dictionary)
{
    // Open dictionary file, and error-check
    dictionary_ref = fopen(dictionary, "r");
    if (dictionary_ref == NULL)
        return false;


    while (fscanf(dictionary_ref, "%s", buffer) > 0) {

        // Figure which index to store word in buffer
        hash_index = hash(buffer);

        // Create new node
        current_head_node = malloc(sizeof(node));
        if (current_head_node == NULL) {
            printf("malloc returned NULL");
            return false;
        }

        strcpy(current_head_node->word, buffer);

        // Figure out whether or not the i'th element of array has been used,
        // and act accordingly
        if (hashtable[hash_index] == NULL)
            current_head_node->next = NULL;

        else
            current_head_node->next = hashtable[hash_index];

        // Point hashtable to the most recent addition
        hashtable[hash_index] = current_head_node;

        wordcount++;
    }

    return true;
}


/**
 * Unloads dictionary from memory. Returns true if successful else false.
 */
bool unload(void)
{
    // Close dictionary reference
    fclose(dictionary_ref);

    node* previous_head = NULL;

    for (int i = 0; i < HASHTABLE_SIZE; i++) { // Iterate through hashtable
        current_head_node = hashtable[i];

        while (current_head_node != NULL) { // Iterate the list

            // Be sure we don't free hashtable[0 - 1]
            if (previous_head != NULL)
                free(previous_head);

            // Advance previous_head to current_head,
            // and then iterate current_head to the next
            previous_head = current_head_node;
            current_head_node = current_head_node->next;

        }
        free(previous_head); // Free the last element in linked list
        previous_head = NULL; // Reset so that we can repeat the above
    }

    return true;
}
\$\endgroup\$
2
\$\begingroup\$
  1. Recommend eliminating all global variables except for the few needed and make those static. Aside from hashtable[], re-architect the rest to make local,

  2. Missing #include "dictionary.h", Certainly this should be included in the post.

  3. dictionary.c should insure dictionary.h is self including all needed <*.h> files. By having dictionary.c include dictionary.h first, that is easily tested.

    #include "dictionary.h"
    #include <string.h>
    #include <ctype.h>
    ...
    //#include "dictionary.h"
    
  4. LENGTH is not defined, Hopefully such a generic named define would not be in "dictionary.h". If it is, suggest a dictionary like name DICTIONARY_BUFFER_LENGTH. Same for HASHTABLE_SIZE.

  5. node is not declared. Like above, node is a very generic type name. Suggest dictionary_noode or the like.

  6. Use type size_t as the array index/size type. Type int may be insufficient.

    // for (int i = 0, wordlen = strlen(word); i < wordlen; i++) {
    for (size_t i = 0, wordlen = strlen(word); i < wordlen; i++) {
    
  7. buffer[] null character termination need only occur once after the loop.

    // for (int i = 0, wordlen = strlen(word); i < wordlen; i++) {
    //   buffer[i] = tolower(word[i]);
    //   buffer[i + 1] = '\0'; // Make sure the word gets terminated
    // }
    size_t = wordlen = strlen(word);
    for (size_t i = 0; i < wordlen; i++) {
      buffer[i] = tolower(word[i]);
    }
    buffer[wordlen] = '\0';
    
  8. word, next not declared in current_head_node->word, current_head_node->next;

  9. As the declaration of node* current_head_node; is far from the malloc() call,a review takes extra time to know if the type is right. For code that is easier to write correctly, review and maintain, consider.

    // current_head_node = malloc(sizeof(node));
    current_head_node = malloc(sizeof *current_head_node);
    
  10. Code lacks overflow protection.

    // fscanf(dictionary_ref, "%s", buffer)
    fscanf(dictionary_ref, "%(some_value)s", buffer)
    
  11. Test not needed. free(NULL) is well defined, effectively a no-op.

    // if (previous_head != NULL) free(previous_head);
    free(previous_head);
    
  12. Goal: "Your implementation of check must be case-insensitive." If limited to A-Za-z, converting to lower or upper makes little difference. When using extended (8-bit) character sets, robust code would use a round-trip as extended alphabets do not always have a 1-to-1 mapping.

    ch = toupper(tolower((unsigned char)ch));
    
\$\endgroup\$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.