// Implements a dictionary's functionality
#include <ctype.h>
#include <stdbool.h>
#include <stdio.h>
#include <stdlib.h>
#include "dictionary.h"
#include <string.h>
#include <strings.h>
int LOWCASEALPHABET[] = { 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 };
int ALPHABET[] = { 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 };
//char ALPHABETT[] = {a, b, c, d, e, f, g, h, i, j, k, l, m, n, o, p, q, r, s, t, u, v, w, x, y, z};
int word_count = 0;
// Represents a node in a hash table
typedef struct node
{
char word[LENGTH + 1];
struct node * next;
}
node;
// TODO: Choose number of buckets in hash table
const unsigned int N = 26;
// Hash table
node *table[N];
// Returns true if word is in the dictionary, else false
bool check(const char *word)
{
// returns an int to which that string corresponds to as an index within the hash table
int i = hash(word);
//cursor pointing at the same node as the start of the indexed element pointer
node *cursor = table[i];
//check if reaches end of linked list in hash table
while (table[i]->next != NULL)
{
//check if node's string value is same as the argument input from dictionary
if (strcasecmp(cursor->word, word) == 0)
{
return true;
}
//traversing through the linked list, cursor gets updated with new node on each itteration starting from head
cursor = cursor->next;
}
return false;
}
// Hashes word to a number
unsigned int hash(const char *word)
{
int i;
//elements in hash table set alphabetically
for (i = 0; i < 27; i++)
{
//check if first char == to element position of alphabet
if (word[0] == ALPHABET[i] || word[0] == LOWCASEALPHABET[i])
{
break;
}
}
return i;
}
// Loads dictionary into memory, returning true if successful, else false
bool load(const char *dictionary)
{
// TODO
// open dictionary file
//read strings from file one at a time
// create a new node for each word
// hash word to obtain a hash value
//insert node into hash table at that location
FILE * fp;
//open file
fp = fopen(dictionary, "r");
if (fp == NULL)
{
return 1;
}
//array that stores what fscanf scans from file
char temp[LENGTH + 1];
while (fscanf(fp, "%s", temp) != EOF)
{
//allocates memory for node
node *n = malloc(sizeof(node));
if (n == NULL)
{
return 1;
}
//puts value into node
strcpy(n->word, temp);
//puts index of node
int hash_index = hash(temp);
//if the element index in array linked list is not occupied, put node into it
if (table[hash_index] == NULL)
{
//pointing to n node
table[hash_index] = n;
n->next = NULL;
word_count++;
//if the element is occupied, link the new node to point to head of element node, then get the head of the element head to point to new node
}
else
{
n->next = table[hash_index];
table[hash_index] = n;
word_count++;
}
}
fclose(fp);
return true;
}
// Returns number of words in the dictionary if loaded, else 0 if not yet loaded
unsigned int size(void)
{
//as your loading the hash table, keep track of the number of words you added to the dictionary so far so you can return that value in your size function
return word_count;
}
// Unloads dictionary from memory, returning true if successful, else false
bool unload(void)
{
for (int i = 0; i < N; i++)
{
node *head = table[i];
node *cursor = head;
//need two pointers to point at the start of the linked node array element and have one going one step ahead while the other frees the memory of that node
//then the pointer that freed memory points to whatever the other pointer that went ahead
if (cursor != NULL)
{
node *temp = cursor;
//traversing through the linked list, temp gets updated with new node on each iteration starting from the head
cursor = cursor->next;
free(temp);
}
}
return true;
}
when I run: "help50 valgrind ./speller texts/cat.txt" at the terminal I get the below output
==21845== 8,011,696 (1,456 direct, 8,010,240 indirect) bytes in 26 blocks are definitely lost in loss record 2 of 2
==21845== at 0x483B7F3: malloc (in /usr/lib/x86_64-linux-gnu/valgrind/vgpreload_memcheck-amd64-linux.so)
==21845== by 0x401AE7: load (dictionary.c:85)
==21845== by 0x4012AE: main (speller.c:40)
"Looks like your program leaked 8,011,696 bytes of memory. Did you forget to free memory that you allocated via malloc? Take a closer look at line 85 of dictionary.c"
How can there be a memory leak when the unload function frees all the nodes and when creating a hashtable I need to allocate the memory until way later when the hash table is completed and used
Also I know I haven't indented properly, I am still looking for a tool to use or I will later look more into the conventional way, so apologies if it's not the clearest
Also line 85 is node *n = malloc(sizeof(node));