// Implements a dictionary's functionality
#include <stdio.h>
#include <stdbool.h>
#include <stdlib.h>
#include "dictionary.h"
#include <string.h>
#include <strings.h>
#include <ctype.h>
// Represents a node in a hash table
typedef struct node
{
char word[LENGTH + 1];
struct node *next;
}
node;
// Number of buckets in hash table
const unsigned int N = 10000;
// Hash table
node *table[N];
// My Globals
int word_count = 0;
bool loaded = false;
// Returns true if word is in dictionary else false
bool check(const char *word)
{
// make a lowercase copy of word
int word_len = strlen(word);
char word_copy[word_len + 1];
for (int i = 0; i < word_len; i++)
{
word_copy[i] = tolower(word[i]);
}
word_copy[word_len] = '\0';
// char *lower_word = tolower(word);
int hash_value = hash(word_copy); // get hash value of word
node *cursor = table[hash_value]; // go to that spot in hash table
// iterate through linked list
while(cursor != NULL)
{
// check for a match in any of the linked list's words
if (strcasecmp(cursor->word, word_copy) == 0)
{
return true;
}
else if (cursor == NULL)
{
return false;
}
else
{
cursor = cursor->next;
}
}
return false;
}
// Hashes word to a number
unsigned int hash(const char *word)
{
// hash table by engineer man https://www.youtube.com/engineerman
unsigned long int value = 0;
unsigned int i = 0;
unsigned int key_len = strlen(word);
for (; i < key_len; ++i)
{
value = value * 37 + word[i];
}
value = value % N;
return value;
}
// Loads dictionary into memory, returning true if successful else false
bool load(const char *dictionary)
{
char word[LENGTH + 1];
// open dictionary file
FILE *dict = fopen(dictionary, "r+");
// check if opened successfully
if (dict == NULL)
{
return false;
}
// read words from dictionary file
while (fscanf(dict,"%s", word) != EOF)
{
// allocate memory for new word
node *n = malloc(sizeof(node));
if (n == NULL)
{
unload();
return false;
}
strcpy(n->word, word);
n->next = NULL;
int index = hash(n->word);
word_count++;
// insert word to linked list
if (table[index] == NULL)
{
table[index] = n;
}
else
{
n->next = table[index];
table[index] = n;
}
}
loaded = true;
return true;
}
// Returns number of words in dictionary if loaded else 0 if not yet loaded
unsigned int size(void)
{
if (loaded)
{
return word_count;
}
return 0;
}
// Unloads dictionary from memory, returning true if successful else false
bool unload(void)
{
node *cursor = NULL;
node *tmp = NULL;
// iterate through hash table
for (int i = 0; i < N; i++)
{
cursor = table[i];
// iterate through linked list
while (cursor != NULL)
{
tmp = cursor;
// set cursor to next item in linked list
cursor = cursor->next;
free(tmp);
}
}
return true;
}
Valgrind is saying that 1 block of memory is still reachable. I would assume that there is a problem with unload, but it seems to be fine. The result is the same whether I run cat.txt or birdman.txt. It also passed all of the check50 tests except for leaking memory. Any ideas why this might be happening?
dictionary.c
in one block so someone can run/debug your code. – stensal Jul 3 '20 at 0:44