· 5 years ago · May 27, 2020, 11:56 PM
1// Implements a dictionary's functionality
2
3#include <stdbool.h>
4#include <stdio.h>
5#include <stdlib.h>
6#include <stdint.h>
7#include <string.h>
8#include <ctype.h>
9#include <strings.h>
10
11#include "dictionary.h"
12
13// Represents a node in a hash table
14typedef struct node
15{
16 char word[LENGTH + 1]; // LENGH is defined in dictionary.h and by default is set to 45 for each node can store an array of up to 45 chars (string)
17 struct node *next;
18}
19node;
20
21// Number of buckets in hash table
22const unsigned int N = 1000;
23
24// Hash table, remember this is an array of pointers (each node contains a pointer to the head of each linked list at each bucket)!
25node *table[N];
26
27// global counter variable to keep track of the amount of nodes added into the linked list
28int count_of_nodes = 0;
29
30// Returns true if word is in dictionary else false
31bool check(const char *word)
32{
33 int hash_value = hash(word); // hash word fromt he users inputted text file to obtain a hash value
34 node *tmp = table[hash_value]; // create a temp pointer pointing to the same index in table[] hash() returned after hashing the word
35
36 if (tmp != NULL) // if the pointer at the current index of the hash table is not pointing to nothing
37 {
38 while (tmp->next != NULL) // every time when looping through the linked list at this index of table[], if the current node after the one tmp is sitting on isn't NULL
39 {
40 tmp = tmp->next; // then migrate the temp pointer to the next node in the linked list
41
42 if (strcasecmp(word, tmp->word) == 0) // compare the strings for the "word" the user is checking against in speller.c to the current word in the current node in the linked list from the dictionary. if strcasecmp() returns 0 indicating they match
43 {
44 return true; // confirm that these words match, and "word" int he users text file is spelled correctly.
45 }
46 }
47 }
48 return false;
49}
50
51/**
52 * A case-insensitive implementation of the djb2 hash function.
53 * Change NUM_BUCKETS to whatever your number of buckets is.
54 * Adapted by Neel Mehta from: http://stackoverflow.com/questions/2571683/djb2-hash-function.
55 */
56unsigned int hash(const char* word)
57 {
58 unsigned long hash = 5381;
59
60 for (const char* ptr = word; *ptr != '\0'; ptr++)
61 {
62 hash = ((hash << 5) + hash) + tolower(*ptr);
63 }
64 return hash % N;
65 }
66
67// Loads dictionary into memory, returning true if successful else false
68bool load(const char *dictionary)
69{
70
71 char* ptr_wordmem = malloc(LENGTH + 1); // declare a pointer to somewhere in memory where a copied dictionary string in stored in memory will be and allocate it enough space of size LENGTH to fit a string
72 FILE* ptr_dictionary = fopen(dictionary, "r"); // fopen() the dictionary file to be used, in this case, the file being pointed to by *dictionary declared in speller.c & passed into this function
73
74 if (ptr_dictionary == NULL) // check to ensure "ptr_dictionary" is not returning a NULL value. If == NULL, the dictionary file does not exist, and will result in a seg fault.
75 {
76 printf("Error, invalid dictionary used son\n!");
77 return false;
78 }
79
80 while (true)
81 {
82 node *n = malloc(sizeof(node)); // malloc() "node 0" in memory + point our *n pointer to it
83 if (n != NULL) // saftey check to ensure n is not pointing to a NULL value in memory to avoid a seg fault
84 {
85 n->next = NULL; // set the next field of the node our "*n" is currently pointing to: nothing
86 }
87
88 fscanf(ptr_dictionary, "%s", ptr_wordmem); // loop through each character in the string , while there are >= the LENGTH of characters, read each char from the dictionary into the memory ptr_wordmem is pointing to at a time
89 strcpy(n->word, ptr_wordmem); // copy the string in memory being pointed to by "word_in_mem"directly into n->word of this generated node
90 int bucket_index = hash(n->word); // create an int called "bucket_index" to store our bucket number hash returns in our bucket_head int. This is also the index in the array of the hash representing each bucket
91
92 if (table[bucket_index] == NULL) // remember table is an array of ponters. if the pointer at the current bucket_index of table[] is not pointing to anything
93 {
94 table[bucket_index] = n; // set the current pointer at the index of the array of pointers to point to this node as the "start node" of the list, n
95 n->next = NULL; // set "n"->next to point to NULL.
96 return true;
97 }
98 else
99 {
100 n->next = table[bucket_index]->next; //set -> next of "node n" to point to where -> next of the node the "head pointer" at the current bucket_index[] (first node) of table[] is pointing to (next node)
101 n->next = NULL;
102 table[bucket_index] = n; // now point the "head pointer" at the current bucket_index[] to this "new" "node n"
103 return true;
104 }
105 count_of_nodes++;
106 }
107 return false;
108}
109
110// Returns number of words in dictionary if loaded else 0 if not yet loaded
111unsigned int size(void)
112{
113 return count_of_nodes;
114}
115
116// Unloads dictionary from memory, returning true if successful else false
117bool unload(void)
118{
119 for (int i = 0; i < N; i++)
120 {
121 node* tmp = table[i]; // declare a pointer called "tep" that is anticipating to be pointed to something of type node & point it to the same place the pointer at table[i] is pointing to
122
123 while (table[i] != NULL) // check if list is currently NULL, if so, the list is empty and we just return
124 {
125 tmp = table[i]; // then, save the head of the linked list into a the tmp variable, which will be redeclared later
126 table[i] = table[i]->next; // then, set the "head" pointer to the linked list in table[i], to now be the ->next node in the linked list, table[i]->next, as the new head of the linked list that exists in table[i].
127 free(tmp); // safely free the node where the (tmp) variable is currently sitting at 1 node behind the new "head" node at table[i] now, repeat step 1
128 }
129 }
130 return false;
131}