any help would be much appreciated - I've been trawling other questions similar to this one but all the adjustments I have tried to make don't seem to fix the check50 failure.
The code seems to run fine, and when I run valgrind ./speller texts/cat.txt I get:
==2684==
==2684== HEAP SUMMARY:
==2684== in use at exit: 0 bytes in 0 blocks
==2684== total heap usage: 143,097 allocs, 143,097 frees, 8,023,472 bytes allocated
==2684==
==2684== All heap blocks were freed -- no leaks are possible
==2684==
==2684== For counts of detected and suppressed errors, rerun with: -v
==2684== ERROR SUMMARY: 0 errors from 0 contexts (suppressed: 0 from 0)
However, when I run check50 cs50/problems/2020/x/speller --log I pass all checks except:
:( program is free of memory errors
valgrind tests failed; rerun with --log for more information.
running valgrind --show-leak-kinds=all --xml=yes --xml-file=/tmp/tmprvfe6ytc -- ./speller substring/dict substring/text...
checking for output "MISSPELLED WORDS\n\nca\ncats\ncaterpill\ncaterpillars\n\nWORDS MISSPELLED: 4\nWORDS IN DICTIONARY: 2\nWORDS IN TEXT: 6\n"...
checking that program exited with status 0...
checking for valgrind errors...
56 bytes in 1 blocks are still reachable in loss record 1 of 2: (file: dictionary.c, line: 119)
112 bytes in 2 blocks are still reachable in loss record 2 of 2: (file: dictionary.c, line: 95)
Line 95 and line 119 are the two lines where memory is allocated (node *n = malloc(sizeof(node)) and node *no_words = malloc(sizeof(node))), but I checked and ((I think)) I free the same number of nodes as I create. My code is:
#include <stdbool.h>
#include <strings.h>
#include <string.h>
#include <ctype.h>
#include <stdio.h>
#include <stdlib.h>
#include "dictionary.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 - start with 27 (letters of the alphabet plus apostrophe
// and space for storing word count)
const unsigned int N = 26 + 1;
// Hash table
node *table[N];
// Returns true if word is in dictionary else false
bool check(const char *word)
{
//Create temp node
node *current_node = table[hash(word)];
//Systematically check through list
while (current_node != NULL)
{
if (strcasecmp(current_node->word, word) == 0)
{
return true;
}
current_node = current_node->next;
}
//If not found, loop ends and we return false
return false;
}
// Hashes word to a number
unsigned int hash(const char *word)
{
//We may assume all words in dictionary are lower case or contain apostrophes
//Sort into buckets in alphabetical order, with the last one for words beginning with '
//i.e. words beginning with a are put in a linked list in table[0]
if (islower(word[0]))
{
return (unsigned int) word[0] - 97;
}
//Must include this for check function
else if (isupper(word[0]))
{
return (unsigned int) word[0] - 65;
}
//By assumption if not lower case, must be an apostrophe
else
{
return N-2;
}
//We reserve the final bucket in the hash table for the word count
}
// Loads dictionary into a data structure in memory, returning true if successful else false
bool load(const char *dictionary)
{
//Open dictionary as a file & check it has opened
FILE *dict = fopen(dictionary, "r");
if (!dict)
{
fclose(dict);
return false;
}
//For each word found, create a node
//Use hash function to determine the bucket, and then insert at the beginning of the linked list
char word[LENGTH + 1];
int word_count = 0;
int scan_value = 0;
//int created_nodes = 0;
while(fscanf(dict, "%s", word) != EOF)
{
//Create a node for the word
node *n = malloc(sizeof(node));
//created_nodes += 1;
if (n == NULL)
{
unload();
fclose(dict);
return false;
}
//Copy the current word into the node
strcpy(n->word, word);
//Determine hash number
unsigned int hash_no = hash(word);
//Insert the node at the beginning of the relevant linked list
n->next = table[hash_no];
table[hash_no] = n;
//Update word count
word_count++;
}
//Include word count in hash table
node *no_words = malloc(sizeof(node));
//created_nodes += 1;
if (no_words == NULL)
{
unload();
fclose(dict);
return false;
}
//Use sprintf to convert word count to string and store in no_words
char num_words[20];
sprintf(num_words, "%i", word_count);
strcpy(no_words->word, num_words);
//Insert the word count at the beginning of the table[N-1] list
no_words->next = table[N-1];
table[N-1] = no_words;
//printf("Created nodes: %i\n", created_nodes);
fclose(dict);
return true;
}
// Returns number of words in dictionary if loaded else 0 if not yet loaded
unsigned int size(void)
{
if (table[N-1] != NULL)
{
//Get the string giving the word count from the end of the hash table, and convert to an int
char *str_count = table[N-1]->word;
int int_count = atoi(str_count);
return int_count;
}
else
{
return 0;
}
}
// Unloads dictionary from memory, returning true if successful else false
bool unload(void)
{
//int nodes_freed = 0;
//For each bucket in table, sequentially free the space
for (int i = 0; i < N; i++)
{
//Check that a linked list exists in bucket
if (table[i] == NULL)
{
free(table[i]);
break;
}
node *current_node = table[i];
node *tmp = current_node;
current_node = current_node->next;
//Loop through to end of linked list, freeing nodes pointed at by tmp
//and using current_node to ensure we don't lose the end of the list
while (current_node != NULL)
{
free(tmp);
//nodes_freed += 1;
tmp = current_node;
current_node = current_node->next;
}
free(current_node);
free(tmp);
//nodes_freed += 1;
}
//printf("Nodes freed: %i\n", nodes_freed);
return true;
}
I was just trying to get a basic hash table working before I tried anything more interesting - if anyone can see what I've done wrong that would be hugely helpful :)
