P9q2uZXM

1/*
2Issue: while the code runs properly in theory, there is an issue. 
3The dictionary passed into the load() function has most conventional words. 
4
5However, when I run the program 'speller', certain unexpected words are flagged as misspelled.
6These words include 'And', 'La', 'polyester'... (basically random words, case-insensitive)
7However, these words exist in the dictionary && only 1 or 2 instances of the word is flagged, not all.
8HOWEVER, If I run the program in debug mode i.e. step by step, the bug doesn't seem to occur.
9
10When I submit my code, I get mostly "Wrong Results" due to this bug (it seems).
11Can't seem to figure out what's going wrong for quite a while.
12
13FOR REF: speller.c code - https://pastebin.com/QQPbSv0F
14*/
15
16// Implements a dictionary's functionality
17
18#include <stdbool.h>
19#include <ctype.h>
20#include <stdio.h>
21#include <stdlib.h>
22#include <string.h>
23#include <strings.h>
24#include <math.h>
25
26#include "dictionary.h"
27
28// Represents a node in a hash table
29typedef struct node
30{
31    char word[LENGTH + 1];
32    struct node *next;
33}
34node;
35
36// Number of buckets in hash table
37const unsigned int N = 65536;                                  // 2 to the power 16
38
39// Hash table
40node *table[N];
41
42//Counter to keep track of number of words in dictionary.
43unsigned int sizetracker = 0;                                   //for size() function at the end
44
45// Returns true if word is in dictionary else false
46bool check(const char *word)
47{
48    char wordbuffer[LENGTH+1];                                  //create an array of char to convert words to lowercase
49
50    for (int i = 0, n = strlen(word); i < n; i++)               //upto last character of word
51    {
52        wordbuffer[i] = tolower(word[i]);
53    }
54    wordbuffer[LENGTH] = '\0';                                  //to add null terminator to lowercased word
55
56    int hashval = hash(wordbuffer);                             //find HASH VALUE
57
58    for (node *tmp = table[hashval]; tmp != NULL; tmp = tmp->next)
59    {
60        if(strcasecmp(wordbuffer,tmp->word) == 0)               //Compare lowercase word and word in dictionary
61        {
62            memset(wordbuffer, 0, (LENGTH+1));                  //Reset/Clear the wordbuffer to 0. Otherwise, some letters tend to stay over from previous iteration
63            return true;
64        }
65    }
66    memset(wordbuffer, 0, (LENGTH+1));                          //Reset/Clear the wordbuffer to 0. Otherwise, some letters tend to stay over from previous iteration
67    return false;
68}
69
70// Hashes word to a number
71// Using the Knuth's Multiplicative Method from https://gist.github.com/badboy/6267743
72unsigned int hash(const char *word)
73{
74    int lettersum = 0;                                          //Find Sum of Letters
75
76    for (int i = 0, n = strlen(word); i<n; i++)
77    {
78        lettersum += word[i];                                   //Letter by letter, calculate semi-unique sum for particular group of letters
79    }
80
81    unsigned long hash = lettersum*2654435761;
82    unsigned int power = pow(2,16);
83    hash = hash%power;
84
85    return hash;                                                //Return semi-unique value
86}
87
88// Loads dictionary into memory, returning true if successful else false
89bool load(const char *dictionary)
90{
91    FILE *dict = fopen(dictionary, "r");                        //Open Dictionary file
92    if (dict == NULL)
93    {
94        return false;
95    }
96
97    char wordbuffer[LENGTH+1];                                  //Create character array for operations
98
99    while(fscanf(dict, "%s", wordbuffer) != EOF)                //read each line into 'wordbuffer'
100    {
101        sizetracker++;                                          //increment for each word
102        node *n = malloc(sizeof(node));                         //assign memory for each word
103        if (n == NULL)
104        {
105            return false;
106        }
107        strcpy(n->word, wordbuffer);                            //copy word from 'wordbuffer' (from dictionary) into node
108        n->next = table[hash(wordbuffer)];                      //Make ptr of node point to whereever the table[hashvalue] is pointing to i.e. previous word with same hash value or NULL, if first word).
109        table[hash(wordbuffer)] = n;                            //Make table[hashvalue] point to the new node
110    }
111
112    fclose(dict);                                               //Close dictionary file
113
114    return true;
115}
116
117// Returns number of words in dictionary if loaded else 0 if not yet loaded
118unsigned int size(void)
119{
120    return sizetracker;
121}
122
123// Unloads dictionary from memory, returning true if successful else false
124bool unload(void)
125{
126    for (int i = 0; i < N; i++)                                 //For each element of the table array
127    {
128        if(table[i] != NULL)                                    //If something exists
129        {
130            node* current = table[i];                           //New node - Current - points to whereve the table[Hashvalue] points to
131            node* next = NULL;                                  //New Node - next - points to nothing, for now
132            while (current != NULL)                             //While current is pointing at something i.e. the linked list exists
133            {
134                next = current->next;                           //make next point to the subsequent node
135                free(current);                                  //free the current node
136                current = next;                                 //make Current point to whereever the 'Next' node is pointing
137            }
138            table[i] = NULL;                                    //Remove table[hashvalue] ptr to be sure.
139        }
140    }
141    return true;
142}