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 :
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(¤t_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;
}
