So when I originally wrote my code for the dictionary.c, I forgot to create the header nodes for each 'bucket' in the hash table. It ran well when every first node of each linked list had a letter, but it keeps failing the check50's since (it seems) check50 doesn't load a full dictionary with a word for each letter of the alphabet. I learned the segfault was because the line in unload() which checks if the next node in a linked list is NULL would run start with nodes that never even existed, thus the first table[i]->next has no value since it itself doesn't exist. Line 102-107 is where I tried to add a head to each table[i], but it keeps on segfaulting(the terminal's output below).
What am I doing wrong, and how can I fix this segfault?
$ ./speller dictionaries/small texts/cat.txt
Segmentation fault
Here is my 'small.txt'
cat
caterpillar
Here is my 'cat.txt'
A cat is not a caterpillar.
// Implements a dictionary's functionality
#include <stdbool.h>
#include <strings.h>
#include <string.h>
#include "dictionary.h"
// Represents a node in a hash table
typedef struct node
{
char word[LENGTH + 1];
struct node *next;
}
node;
//head of each 'bucket' in the hash table
node *head = NULL;
// Number of buckets in hash table
const unsigned int N = 26;
// Hash table
node *table[N];
//Global Number of Words Loaded
int dcount = 0;
int firstWord[26]={0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, };
// Returns true if word is in dictionary else false
bool check(const char *word)
{
// TODO
//1.Hash to obtain a hash value
//printf("Hashing %s....\n", word);
int index = hash(word);
if(firstWord[index]==0)
{
return false;
}
//2.Access the linked list at that index in the hash table
node *cursor = table[index];
//3.Traverse the linked list, looking for the word(strcasecmp)
while(true)
{
if(strcasecmp(word, cursor->word)==0)
{
return true;
}
else
{
if(cursor->next !=NULL)
{
cursor = cursor->next;
}
else
{
return false;
}
}
}
return false;
}
// Hashes word to a number
unsigned int hash(const char *word)
{
//It has been proven that this function can return an appropriate hash value: a=0, b=1, ect ect
//DONE
//The Concept: each index of this array corresponds to a letter of the alphabet, starting from 0.
//The way this hash function works is that it checks to see which index the word it is given belongs to.
//Implementation:
//1)Cast the 1st character as an ascii value(cast to int), first with the lowercase being checked.
//2)Check if the value is even a letter
if((int)word[0]>64 && (int)word[0]<91)
{
int index = (int)word[0] - 65;
//3)Subtract a certain amount which matches the ascii value to the index
//5)that value is the hash value for the word
return index;
}
//4)Subtract a different amount if it is capital
if((int)word[0]>96 && (int)word[0]<123)
{
int index = (int)word[0] - 97;
//3)Subtract a certain amount which matches the ascii value to the index
//5)that value is the hash value for the word
return index;
}
return 0;
}
// Loads dictionary into memory, returning true if successful else false
bool load(const char *dictionary)
{
int k = 0;
while(k <25)
{
table[k] = head;
k++;
}
//printf("Load Function Running\n");
//DONE: This function can successfully load a dictionary into a hash table
//Open file into pointer ptr
FILE *ptr = fopen(dictionary, "r");
if(ptr == NULL)
{
return false;
}
while(true)
{
size();
//It has been proven that this section WILL load the next word through each iteration.
//LOAD NEW WORD
char tWord[LENGTH];
int r = fscanf(ptr, "%s", tWord);
if( r == EOF)
{
//printf("Displaying contents in 'z'\n");
node *cursor = table[25];
while (false)
{
printf("-%s\n", cursor->word);
if(cursor->next!=NULL)
{
cursor = cursor->next;
}else
{
break;
}
}
return true;
}
//APPEND TO LINKED LIST
node *nptr = malloc(sizeof(tWord));
if(nptr == NULL)
{
printf("QUIT: nptr is NULL, returning 1\n");
return false;
}
nptr->next=NULL;
strcpy(nptr->word, tWord);
int index = hash(tWord);
node *tptr = table[index]->next;
nptr->next = tptr;
table[index]->next=nptr;
firstWord[index]=1;
}
//Test if read properly
printf("load function terminated.\n");
return false;
}
// Returns number of words in dictionary if loaded else 0 if not yet loaded
unsigned int size(void)
{
//printf("dcount = %i\n", dcount);
dcount++;
return dcount;
}
// Unloads dictionary from memory, returning true if successful else false
bool unload(void)
{
//return false;
// TODO
for(int i = 0; i <= 25; i++)
{
node *cursor = table[i];
int j=0;
//if(i==25){printf("Z!\n");}
while (true)
{
//if(i==25){printf("NEW WORD!\n");}
j++;
free(table[i]);
if(i==0){printf("NEW WORD! : table.[i]->word == '%s'\n", table[i]->word);}
if(table[i]->next != NULL)
{
//cursor = cursor->next;
table[i]=table[i]->next;
cursor = table[i]->next;
}
else
{
break;
}
}
if(i==25)
{
return true;
}
}
return false;
}
