dictionary.c

/**
 * Implements a dictionary's functionality.
 */
#include <cs50.h>
#include <stdbool.h>
#include <stdio.h>
#include <stdint.h>
#include <stdlib.h>
#include <string.h>

#include "dictionary.h"

// the multiplier for the hash function
#define MULTIPLIER (37)

// node structure for hashtable to store dictionary
typedef struct sllist
{
    //string word;
    char* wrd;
    struct sllist *next;
}
node;

// functions used
unsigned int hash(const char* s);
node* create(char* w);
node* insert(node* head, char* w);
bool search(node* head, const char* w);
void destroy(node* head);

// max number of linked list head pointers
const int HASH_MAX = 150000;

// the hashtable to put the dictionary in
node* hashTable [150000];

// the number of words in the dictionary
int wordCount = 0;

/**
 * Returns true if word is in dictionary else false.
 */
bool check(const char *word)
{
    // hash the word
    int hashTableNo = hash(word);
    
    bool wordIsInDictionary = false;
    
    if(hashTable[hashTableNo] == NULL)
    {
        return false;
    }
    else
    {
        // print to console to see what's stored in the variables
        node* ptr = hashTable[hashTableNo];
        printf("Check: The hash number: %i\n", hashTableNo);
        printf("Check: The dictionary word: %s\n", ptr->wrd);
        printf("Check: The pointer: %i\n", (int)hashTable[hashTableNo]);
        printf("Check: The text word: %s\n", word);
            
        wordIsInDictionary = search(ptr, word);
        
    }
    // TODO
    return wordIsInDictionary;
}

/**
 * Loads dictionary into memory. Returns true if successful else false.
 */
bool load(const char *dictionary)
{
    
    FILE *fp = fopen(dictionary, "r");
    if (fp == NULL)
    {
        printf("Could not open %s.\n", dictionary);
        unload();
        return 1;
    }
    
    
    
    char word[LENGTH + 1];
    
    while(fscanf(fp, "%s", word) != EOF)
    {
        // hash the word
        int hashTableNo = hash(word);
        
        if(hashTable[hashTableNo] == NULL)
        {
            hashTable[hashTableNo] = create(word);
        }
        
        else
        {
            hashTable[hashTableNo] = insert(hashTable[hashTableNo], word);
        }
        
        wordCount++;
        
        // print to console to see what's stored in the variables
        node* ptr = hashTable[hashTableNo];
        while(ptr != NULL)
        {
            printf("Load: The hash number: %i\n", hashTableNo);
            printf("Load: The dictionery word: %s\n", ptr->wrd);
            printf("Load: The dictionery word: %s\n", hashTable[hashTableNo]->wrd);
            printf("Load: The pointer: %i\n", (int)hashTable[hashTableNo]);
            ptr = ptr->next;
        }
    }
    return true;
}

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

/**
 * Unloads dictionary from memory. Returns true if successful else false.
 */
bool unload(void)
{
    for(int i = 0; i < 150001; i++)
    {
        if(hashTable[i] != NULL)
        {
            destroy(hashTable[i]);
        }
        
    }
    
    
    return true;
}

// hash function adapted from: http://www.cs.yale.edu/homes/aspnes/pinewiki/C(2f)HashTables.html?highlight=%28CategoryAlgorithmNotes%29
unsigned int hash(const char* s)
{
    unsigned long h;
    unsigned const char *us;
    
    // cast s to an unsigned const char
    // this ensures that elements of s will be treated as having values >= 0
    us = (unsigned const char *) s;
    
    h = 0;
    while(*us != '\0')
    {
        h = h * MULTIPLIER + *us;
        us++;
    }
    
    return h % HASH_MAX;
}

node* create(char* w)
{
    
    // dynamically allocate space for a new node
    node *ptr = malloc(sizeof(node));
    
    //check to make sure we didn't run out of memory
    
    // initialize the node's val field
    ptr->wrd = w;
    
    // initialize the node's next field (will be null for the first item added to the list)
    ptr->next = NULL;
    
    printf("Create: %s\n", ptr->wrd);
    
    // return the pointer to the newly created sllnode
    return ptr;
}

node* insert(node* head, char* w)
{
     // dynamically allocate space for a new sllnode
    node *ptr = malloc(sizeof(node));
    
    //check to make sure we didn't run out of memory
    
    // populate and insert the node at the beginning of the linked list
    ptr->wrd = w;
    ptr->next = head;
    
    // return pointer to new head of list
    return ptr;
}

bool search(node* head, const char* w)
{
    node* ptr = head;
    while(ptr != NULL)
    {
       if(ptr->wrd == w)
       {
           return true;
       }
       
       printf("Search: The checked loaded word: %s\n", ptr->wrd);
       printf("Search: The checked word in the text: %s\n", w);
       
       ptr = ptr->next;
    }
    return false;
}

void destroy(node* head)
{
    
    if(head->next == NULL){
        free(head);
        return;
    }
    
    else
    {
        node* head2 = head->next;
        free(head);
        destroy(head2);
    }
    
}