'CS50 speller problem segmentation fault first, then I found it failed to load the dictionary correctly
100% newbie in coding, this is a really tough problem-set for me.
Took me few days to finally got my program to compile. However I am getting segmentation fault when I actually running the program. So I tried to delete the function with error and see how it goes, to my surprise the segmentation fault no longer show up and did actually ran. Turns out my program does not properly created a hash table out of the dictionary.
So my guess, the root problem is that my check function was trying to assign table[index] which does not exist to my temp node and hence gave me segmentation fault, was my guess correct?
So my next bet is to get my program to load the dictionary correctly, however I am not capable of spotting any errors after repeatedly checking the load function, did I miss anything?
hereby attached my code:
// Represents a node in a hash table
typedef struct node
{
char word[LENGTH + 1];
struct node *next;
}
node;
//set up counter to count no. of word in dictionary
int counter;
// Choose number of buckets in hash table
const unsigned int N = 26;
// Initialize Hash table
node *table[N];
// Returns true if word is in dictionary, else false
bool check(const char *word)
{
// get hash index
int index=hash(word);
//loop to run thru the linked list and do comparison
for(node* temp=table[index];temp->next!=NULL;temp=temp->next)
{
if (strcasecmp(temp->word, word)==0)
{
return true;
}
}
return false;
}
// Hashes word to a number
unsigned int hash(const char *word)
{
// the very basic ,slow hash function indexing A-Z to 0-26
char A= toupper(word[0]);
int Z= A-65;
return (Z);
}
// Loads dictionary into memory, returning true if successful, else false
bool load(const char *dictionary)
{
FILE *file=fopen(dictionary ,"r");
if(!file)
{
return false;
}
char word[LENGTH + 1];
while(fscanf(file,"%s",word)!=EOF)
{
//make new node n
node*n=malloc(sizeof(node));
if(n==NULL)
{
return false;
}
//input data into node n
strcpy(n->word,word);
n->next=NULL;
//get index from hash function
int index=hash(word);
//check linked list in hash table ,if empty> assign n in linked list
if(table[index]==NULL)
{
table[index]=n;
counter++;
}
//update linked list in hash table
else
{
n->next=table[index];
table[index]=n;
counter++;
}
return true;
}
fclose(file);
return true;
}
// Returns number of words in dictionary if loaded, else 0 if not yet loaded
unsigned int size(void)
{
if (counter!=0)
{
return (counter);
}
else
{
return 0;
}
}
// Unloads dictionary from memory, returning true if successful, else false
bool unload(void)
{
for(int i=0;i<26;i++)
{
while(table[i]!=NULL)
{
node* temp=table[i]->next;
free(table[i]);
table[i]=temp;
}
}
return true;
}
First, I ran a valgrind for debug and i got the following error message:
Invalid read of size 8
==24218== at 0x4019BC: check (dictionary.c:32)
==24218== by 0x4015FB: main (speller.c:113)
==24218== Address 0x30 is not stack'd, malloc'd or (recently) free'd
...
==11431== ERROR SUMMARY: 1 errors from 1 contexts (suppressed: 0 from 0)
line 8 was in check function
for(node* temp=table[index];temp->next!=NULL;temp=temp->next)
And the program ran after I temporarily set the check function to simply return true, it ran and gave the following result:
WORDS MISSPELLED: 0
WORDS IN DICTIONARY: 1
WORDS IN TEXT: 17756
TIME IN load: 0.00
TIME IN check: 0.02
TIME IN size: 0.00
TIME IN unload: 0.00
TIME IN TOTAL: 0.02
seems that it is having problem loading dictionary into a hash table hopefully the program will run normally after load function corrected.
update : as requested, hereby attached the main program ,however it was written by staffs of CS50, unlikely to be the problem
int main(int argc, char *argv[])
{
// Structures for timing data
struct rusage before, after;
// Benchmarks
double time_load = 0.0, time_check = 0.0, time_size = 0.0, time_unload = 0.0;
// Determine dictionary to use
char *dictionary = (argc == 3) ? argv[1] : DICTIONARY;
// Load dictionary
getrusage(RUSAGE_SELF, &before);
bool loaded = load(dictionary);
getrusage(RUSAGE_SELF, &after);
// Exit if dictionary not loaded
if (!loaded)
{
printf("Could not load %s.\n", dictionary);
return 1;
}
// Calculate time to load dictionary
time_load = calculate(&before, &after);
// Try to open text
char *text = (argc == 3) ? argv[2] : argv[1];
FILE *file = fopen(text, "r");
if (file == NULL)
{
printf("Could not open %s.\n", text);
unload();
return 1;
}
// Prepare to report misspellings
printf("\nMISSPELLED WORDS\n\n");
// Prepare to spell-check
int index = 0, misspellings = 0, words = 0;
char word[LENGTH + 1];
// Spell-check each word in text
char c;
while (fread(&c, sizeof(char), 1, file))
{
// Allow only alphabetical characters and apostrophes
if (isalpha(c) || (c == '\'' && index > 0))
{
// Append character to word
word[index] = c;
index++;
// Ignore alphabetical strings too long to be words
if (index > LENGTH)
{
// Consume remainder of alphabetical string
while (fread(&c, sizeof(char), 1, file) && isalpha(c));
// Prepare for new word
index = 0;
}
}
// Ignore words with numbers (like MS Word can)
else if (isdigit(c))
{
// Consume remainder of alphanumeric string
while (fread(&c, sizeof(char), 1, file) && isalnum(c));
// Prepare for new word
index = 0;
}
// We must have found a whole word
else if (index > 0)
{
// Terminate current word
word[index] = '\0';
// Update counter
words++;
// Check word's spelling
getrusage(RUSAGE_SELF, &before);
bool misspelled = !check(word);
getrusage(RUSAGE_SELF, &after);
// Update benchmark
time_check += calculate(&before, &after);
// Print word if misspelled
if (misspelled)
{
printf("%s\n", word);
misspellings++;
}
// Prepare for next word
index = 0;
}
}
// Check whether there was an error
if (ferror(file))
{
fclose(file);
printf("Error reading %s.\n", text);
unload();
return 1;
}
// Close text
fclose(file);
// Determine dictionary's size
getrusage(RUSAGE_SELF, &before);
unsigned int n = size();
getrusage(RUSAGE_SELF, &after);
// Calculate time to determine dictionary's size
time_size = calculate(&before, &after);
// Unload dictionary
getrusage(RUSAGE_SELF, &before);
bool unloaded = unload();
getrusage(RUSAGE_SELF, &after);
// Abort if dictionary not unloaded
if (!unloaded)
{
printf("Could not unload %s.\n", dictionary);
return 1;
}
// Calculate time to unload dictionary
time_unload = calculate(&before, &after);
// Report benchmarks
printf("\nWORDS MISSPELLED: %d\n", misspellings);
printf("WORDS IN DICTIONARY: %d\n", n);
printf("WORDS IN TEXT: %d\n", words);
printf("TIME IN load: %.2f\n", time_load);
printf("TIME IN check: %.2f\n", time_check);
printf("TIME IN size: %.2f\n", time_size);
printf("TIME IN unload: %.2f\n", time_unload);
printf("TIME IN TOTAL: %.2f\n\n",
time_load + time_check + time_size + time_unload);
// Success
return 0;
}
Sources
This article follows the attribution requirements of Stack Overflow and is licensed under CC BY-SA 3.0.
Source: Stack Overflow
| Solution | Source |
|---|
