When I run check50 the code fails on the last check below:
"valgrind tests failed; rerun check50 with --log added to end of command for more information." See https://cs50.me/checks/678bfd51ae43a417ff5c59394aa4cc0f7a50802e for more detail.
Clicking the link for more details shows the following:
"running valgrind ./speller substring/dict substring/text...
checking for output "MISSPELLED WORDS ca cats caterpill caterpillars WORDS MISSPELLED: 4 WORDS IN DICTIONARY: 2 WORDS IN TEXT: 6 "...
checking that program exited with status 0...
checking for valgrind errors...
Invalid read of size 1: (file: dictionary.c, line: 36)
Invalid read of size 1: (file: dictionary.c, line: 72)
41 bytes in 6 blocks are definitely lost in loss record 1 of 2: (file: dictionary.c, line: 54)
552 bytes in 1 blocks are still reachable in loss record 2 of 2: (file: dictionary.c, line: 155)"
I have copied my dictionary.c code in full at bottom, but here are the problematic lines according to valgrind:
Invalid read of size 1: (file: dictionary.c, line: 36) - this is first line of hash function I found online
for (const char* ptr = word; *ptr != '\0'; ptr++)
Invalid read of size 1: (file: dictionary.c, line: 72)
if (strcmp(trav -> word, lowercaseword) == 0)
41 bytes in 6 blocks are definitely lost in loss record 1 of 2: (file: dictionary.c, line: 54)
char* lowercaseword = malloc((wordlength + 1) * sizeof(char));//malloc space for lowercaseword (plus 1 for "\0")
552 bytes in 1 blocks are still reachable in loss record 2 of 2: (file: dictionary.c, line: 155)
dictionary_read = fopen(dictionary, "r");
I've looked for similar questions and understand that for example "invalid read of size 1" means the program is trying to read from a byte in memory that I shouldn't have access to. So for the first error (line 36) I tried to adapt the hash function (that I found online) and initialise the const char* ptr to NULL, but that didn't help. As for the other 2 that refer to loss records I am feeling very, erm...lost. Any hints would be gratefully received!
// Implements a dictionary's functionality
#include <stdio.h>
#include <stdbool.h>
#include <stdlib.h>
#include <string.h>
#include <ctype.h>
#include "dictionary.h"
#define BUCKETS 500
//create a node struct
typedef struct node
{
char word[LENGTH + 1];
struct node *next;
}
node;
//declare global variables
//declare array of node pointers with array size of max BUCKETS.
node* hashtable[BUCKETS];//we have 143,091 words
int dictionary_word_counter = 0; //initialise dictionary word counter
//declare hash function
// Adapted by Neel Mehta from
//http://stackoverflow.com/questions/2571683/djb2-hash-function.
unsigned int hash_word(const char* word)
{
unsigned long hash = 5381;
for (const char* ptr = word; *ptr != '\0'; ptr++)
{
hash = ((hash << 5) + hash) + tolower(*ptr);
}
return hash % BUCKETS;
}
// Returns true if word is in dictionary else false
bool check(const char *word)
{
node* head_ptr = NULL;//initialise head pointer to NULL
//ensure that all letters are lowercase before hashing word from text file
int wordlength = strlen(word);//store length of word
char* lowercaseword = malloc((wordlength + 1) * sizeof(char));//malloc space for lowercaseword (plus 1 for "\0")
for (int i = 0; i < wordlength; i++)
{
lowercaseword[i] = tolower(word[i]);
}
//get hash for word and assign it to index
int index = hash_word(lowercaseword);
//declare head pointer
head_ptr = hashtable[index];
// declare trav pointer and set it to point to same node as "head_ptr".
node* trav = head_ptr;
while (trav != NULL)
{
if (strcmp(trav -> word, lowercaseword) == 0)
{
return true;
}
else
{
trav = trav -> next;
}
}
//if while loop run and not return true then word not found so return false
return false;
free(lowercaseword);
}
// Returns number of words in dictionary if loaded else 0 if not yet loaded
unsigned int size(void)
{
if (dictionary_word_counter > 0)//if loaded more than one we assume dictionary has loaded in complete following testing
{
return dictionary_word_counter;
}
return 0;
}
// Unloads dictionary from memory, returning true if successful else false
bool unload(void)
{
node* trav = NULL;//initialise local variable
//set counter for number of nodes that have been sucsessfully freed
int free_node_counter = 0;
//iterate through each bucket
for(int index = 0; index < BUCKETS; index ++)
{
trav = hashtable[index];
while(trav != NULL)
{
node* temp_ptr = trav;
trav = trav -> next;
free(temp_ptr);
free_node_counter ++;
}
}
if (free_node_counter == dictionary_word_counter)
{
return true;
}
else
{
return false;
}
}
// Loads dictionary into memory, returning true if successful else false
bool load(const char *dictionary)
{
//initialise FILE pointer to NULL
FILE* dictionary_read = NULL;
//set up char array to store each word temporarily before hashing.
char temp_word[LENGTH + 1];
//loop to initialise all array elements to NULL
for(int i = 0; i < BUCKETS; i++)
{
hashtable[i] = NULL;
}
//scan dictionary word by word
dictionary_read = fopen(dictionary, "r");
while(fscanf(dictionary_read, "%s", temp_word) != EOF)
{
dictionary_word_counter ++; //keep track of how many words read from dictionary
//malloc space for a new node each time
node* new_node = malloc(sizeof(node));
//check that new node pointer has been created and we have not run out of memory (i.e. pointer is set to NULL)
if (new_node == NULL)
{
unload();
return false;
}
else //copy temp_word into new node
{
strcpy(new_node -> word, temp_word);
}
int index = hash_word(temp_word); //set hastable bucket index to match value returned when run through hash function.
//check if the pointer at bucket is set to NULL
if (hashtable[index] == NULL)
{
hashtable[index] = new_node; //assigns hashtable bucket pointer to address of new node
new_node -> next = NULL; //sets pointer of new node to NULL as so far only node in linked list
}
else
{
new_node -> next = hashtable[index];//assign new node next pointer to bucket pointer
hashtable[index] = new_node;//re-assign bucket pointer to the new node we have inserted
}
}
return true;
fclose(dictionary_read);//close currently open file pointer.
}
