cs50 pset5 memory leaking code

dictionary.c

/****************************************************************************
 * dictionary.c
 *
 * Computer Science 50
 * Problem Set 5
 *
 * Implements a dictionary's functionality.
 ***************************************************************************/

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

#include "dictionary.h"

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

/**
 * Loads dictionary into memory.  Returns true if successful else false.
 */
bool load(const char* dictionary)
{
    // open the dictionary file
    FILE* file = fopen(dictionary, "r");
    if (file == NULL)
    {
    	fclose(file);
    	return false;
    }
    
    // initialize a trie
    trie = createNode();
    
    // size of longest word + '\n' + \0'
    char word[LENGTH + 2];
    
    // initialize word counter
    num_of_words = 0;
    
    // read lines from the dictionary
    while(fgets(word, LENGTH + 2, file) != 0)
    {
    	// insert word into trie
    	insert(trie, word);
    	
    	// increment word counter
    	num_of_words++;
    }
    
    fclose(file);
    
    return true;
}

/**
 * Returns number of words in dictionary if loaded else 0 if not yet loaded.
 */
unsigned int size(void)
{
    if (trie != NULL)
    	return num_of_words;
    else
    	return 0;
}

/**
 * Unloads dictionary from memory.  Returns true if successful else false.
 */
bool unload(void)
{
    // free the trie structure
    return freeMem(trie);
}

/**
 * Inserts the provided node into the trie data structure in memory.
 */
void insert(node* pntr, char word[LENGTH + 2])
{
	// go through each character in word
	for (int i = 0; i < strlen(word); i++)
	{
		// to store the index
		int index;
		
		// current character
		char c = word[i];
		
		// continue only if alphabetical character of apostrophe
		if (isalpha(c) || c == '\'')
		{
			// assign index of 27 for apostrophe
			if (c == '\'')
				index = MAX - 1;
		
			// calculate index for alphabetical characters
			else
				index = tolower(c) - 'a';
			
			// if pointer exists at index follow it
			if (pntr->next[index] != NULL)
				pntr = pntr->next[index];
			
			// if not allocate a new node and point to it
			else
			{
				node* new = createNode();
				pntr->next[index] = new;
				pntr = pntr->next[index];
			}
		}
	}
	
	// mark as end of a word
	pntr->word = true;
}

/**
 * Searches for the provided word in the the data structure trie.
 * Returns true if found else false.
 */
bool search(node* pntr, const char* word)
{
	// go through each character in word
	for (int i = 0; i < strlen(word); i++)
	{
		// to store the index
		int index;
		
		// current character
		char c = word[i];
		
		// continue only if alphabetical character of apostrophe
		if (isalpha(c) || c == '\'')
		{
			// assign index of 27 for apostrophe
			if (c == '\'')
				index = MAX - 1;
		
			// calculate index for alphabetical characters
			else
				index = tolower(c) - 'a';
			
			// if pointer exists at index follow it
			if (pntr->next[index] != NULL)
				pntr = pntr->next[index];
			
			// if not return false
			else
				return false;
		}
	}
	
	// check to see if end of word
	if (pntr->word)
		return true;
	else
		return false;
}

/**
 * Free's each and ever node in the trie.
 * Returns true if successfull else false.
 */
bool freeMem(node* pntr)
{
	// free each not null pointer
	for (int i = 0; i < MAX; i++)
	{
		if (pntr->next[i] != NULL)
			return freeMem(pntr->next[i]);
	}
	
	// free the node itself
	free(pntr);
	
	return true;
}

/**
 * Initializes a new node and returns it's address.
 */
node* createNode()
{
	// allocate memory for new node
	node* new_node = (node*) malloc(sizeof(node));
	
	new_node->word = false;
	
	// set all pointers to NULL
	for (int i = 0; i < MAX; i++)
		new_node->next[i] = NULL;
		
	return new_node;
}

dictionary.h

/****************************************************************************
 * dictionary.h
 *
 * Computer Science 50
 * Problem Set 5
 *
 * 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

// numeber of items in array
// 26 letters + 1 for apostrophe
#define MAX 27

// define a node to be used in trie
typedef struct node
{
	bool word;
	struct node* next[MAX];
} node;

// global variable for pointer to first node of trie
node* trie;

// global variable for number of words in dictionary
int num_of_words;

/**
 * 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);

/**
 * Initializes a new node and returns it's address.
 */
node* createNode();

/**
 * Inserts the provided node into the trie data structure in memory.
 */
void insert(node* pntr, char word[LENGTH + 2]);

/**
 * Searches for the provided word in the the data structure trie.
 * Returns true if found else false.
 */
bool search(node* pntr, const char* word);

/**
 * Free's each and ever node in the trie.
 * Returns true if successfull else false.
 */
bool freeMem(node* pntr);

#endif // DICTIONARY_H

Makefile

#
# Makefile
#
# Computer Science 50
# Problem Set 5
#


# compiler to use
CC = clang

# flags to pass compiler
CFLAGS = -ggdb3 -O0 -Qunused-arguments -std=c99 -Wall -Werror

# name for executable
EXE = speller

# space-separated list of header files
HDRS = dictionary.h

# space-separated list of libraries, if any,
# each of which should be prefixed with -l
LIBS =

# space-separated list of source files
SRCS = speller.c dictionary.c

# automatically generated list of object files
OBJS = $(SRCS:.c=.o)


# default target
$(EXE): $(OBJS) $(HDRS) Makefile
	$(CC) $(CFLAGS) -o $@ $(OBJS) $(LIBS)

# dependencies 
$(OBJS): $(HDRS) Makefile

# housekeeping
clean:
	rm -f core $(EXE) *.o

speller.c

/****************************************************************************
 * speller.c
 *
 * Computer Science 50
 * Problem Set 5
 *
 * 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 "words"

// 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);
    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);
    }
}