-
Notifications
You must be signed in to change notification settings - Fork 1
/
dictionary.c
152 lines (126 loc) · 3.37 KB
/
dictionary.c
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
// Implements a dictionary's functionality
#include <stdbool.h>
#include "dictionary.h"
#include <stdio.h>
#include <ctype.h>
#include <stdlib.h>
#include <string.h>
#include <strings.h>
// Represents a node in a hash table
typedef struct node
{
char word[LENGTH + 1];
struct node *next;
}
node;
// no. of buckets in hash table - thansk to https://youtu.be/HsnjdbHMZO8?t=944
const unsigned int N = LENGTH * ('z' + 1);
// initialise positive hash value using unsigned int
unsigned int hash_value;
// initialise (positive) hash table word count - init to zero
unsigned int word_count = 0;
// hash table
node *table[N];
// Returns true if word is in dictionary, else false
bool check(const char *word)
{
//hash the word to get hash value
hash_value = hash(word);
//access the linked list
node *cursor = table[hash_value];
//go through the linked list
while (cursor != NULL)
{
//check if the word matches
if (strcasecmp(word, cursor->word) == 0)
{
return true;
}
//move cursor to next node
cursor = cursor->next;
}
return false;
}
// Hashes word to a number
// thansk to https://youtu.be/HsnjdbHMZO8?t=944
// this function could reduce time from 1.38 to 0.04
// former hash function was related to djb2 algorithm
unsigned int hash(const char *word)
{
// This hash function adds the ASCII values of all characters in the word together
long sum = 0;
for (int i = 0; i < strlen(word); i++)
{
sum += tolower(word[i]);
}
return sum % N;
}
// Loads dictionary into memory, returning true if successful, else false
bool load(const char *dictionary)
{
// Open dict
FILE *file = fopen(dictionary, "r");
// If file is not opened, return false
if (file == NULL)
{
return false;
}
// storage space for word
char word[LENGTH + 1];
// Scan dict for strings that are not the end of the file
while (fscanf(file, "%s", word) != EOF)
{
// Allocate memory for new node
node *n = malloc(sizeof(node));
// If malloc returns NULL, return false
if (n == NULL)
{
return false;
}
// Pointer to next node and word itself
strcpy(n->word, word);
// Hash the word to get hash value
hash_value = hash(word);
// Set new pointer
n->next = table[hash_value];
// Set head to new pointer
table[hash_value] = n;
// Increment word count
word_count++;
}
// Close file
fclose(file);
// If dict is loaded, return true
return true;
}
// Returns number of words in dictionary if loaded, else 0 if not yet loaded
unsigned int size(void)
{
return word_count;
}
// Unloads dictionary from memory, returning true if successful, else false
bool unload(void)
{
// Iterate through buckets
for (int i = 0; i < N; i++)
{
// Set cursor to this each bucket location
node *cursor = table[i];
// If cursor is not NULL, free
while (cursor)
{
// Create temp
node *tmp = cursor;
// Move cursor to next node
cursor = cursor->next;
// Free up temp
free(tmp);
}
// If cursor is NULL
if (i == N - 1 && cursor == NULL)
{
return true;
}
}
return false;
}