I've run my program through check50 and get the following output:
:) dictionary.c, dictionary.h, and Makefile exist
:) speller compiles
:) handles most basic words properly
:) handles min length (1-char) words
:) handles max length (45-char) words
:) handles words with apostrophes properly
:) spell-checking is case-insensitive
:) handles substrings properly
:( program is free of memory errors
valgrind tests failed; rerun with --log for more information.
The log for the valgrind test shows:
running valgrind --show-leak-kinds=all --xml=yes --xml-file=/tmp/tmpud3boltd -- ./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...
Conditional jump or move depends on uninitialised value(s): (file: dictionary.c, line: 125)
The code referred to on the last line is the if statement in this function used to recursively delete the linked lists in my hashtable:
// Destroy function deletes an entire linked list recursively
void destroy(struct node* list)
{
// Initialise current node pointer to point to head of list
node* current = list;
// Recursion base case
if (current == NULL)
{
return;
}
destroy(current->next);
free(current);
}
Which is called by the following function:
// Unloads dictionary from memory, returning true if successful else false
bool unload(void)
{
for (int i = 0; i < HASHTABLE_SIZE; i++)
{
if (hashtable[i] == NULL)
{
continue;
}
destroy(hashtable[i]);
}
return true;
}
When I run valgrind myself I get the following output:
~/pset5/speller/ $ help50 valgrind ./speller texts/cat.txt
==10541== Memcheck, a memory error detector
==10541== Copyright (C) 2002-2017, and GNU GPL'd, by Julian Seward et al.
==10541== Using Valgrind-3.13.0 and LibVEX; rerun with -h for copyright info
==10541== Command: ./speller texts/cat.txt
==10541==
MISSPELLED WORDS
==10541== Conditional jump or move depends on uninitialised value(s)
==10541== at 0x401429: destroy (dictionary.c:127)
==10541== by 0x401440: destroy (dictionary.c:131)
==10541== by 0x4014A4: unload (dictionary.c:144)
==10541== by 0x400ED9: main (speller.c:152)
==10541== Uninitialised value was created by a heap allocation
==10541== at 0x4C2FB0F: malloc (in /usr/lib/valgrind/vgpreload_memcheck-amd64-linux.so)
==10541== by 0x401325: load (dictionary.c:85)
==10541== by 0x400A34: main (speller.c:40)
==10541==
==10541== Conditional jump or move depends on uninitialised value(s)
==10541== at 0x401429: destroy (dictionary.c:127)
==10541== by 0x401440: destroy (dictionary.c:131)
==10541== by 0x401440: destroy (dictionary.c:131)
==10541== by 0x4014A4: unload (dictionary.c:144)
==10541== by 0x400ED9: main (speller.c:152)
==10541== Uninitialised value was created by a heap allocation
==10541== at 0x4C2FB0F: malloc (in /usr/lib/valgrind/vgpreload_memcheck-amd64-linux.so)
==10541== by 0x401325: load (dictionary.c:85)
==10541== by 0x400A34: main (speller.c:40)
==10541==
==10541== Conditional jump or move depends on uninitialised value(s)
==10541== at 0x401429: destroy (dictionary.c:127)
==10541== by 0x401440: destroy (dictionary.c:131)
==10541== by 0x401440: destroy (dictionary.c:131)
==10541== by 0x401440: destroy (dictionary.c:131)
==10541== by 0x4014A4: unload (dictionary.c:144)
==10541== by 0x400ED9: main (speller.c:152)
==10541== Uninitialised value was created by a heap allocation
==10541== at 0x4C2FB0F: malloc (in /usr/lib/valgrind/vgpreload_memcheck-amd64-linux.so)
==10541== by 0x401325: load (dictionary.c:85)
==10541== by 0x400A34: main (speller.c:40)
==10541==
WORDS MISSPELLED: 0
WORDS IN DICTIONARY: 143091
WORDS IN TEXT: 6
TIME IN load: 1.46
TIME IN check: 0.00
TIME IN size: 0.00
TIME IN unload: 0.25
TIME IN TOTAL: 1.72
==10541==
==10541== HEAP SUMMARY:
==10541== in use at exit: 0 bytes in 0 blocks
==10541== total heap usage: 143,096 allocs, 143,096 frees, 8,023,416 bytes allocated
==10541==
==10541== All heap blocks were freed -- no leaks are possible
==10541==
==10541== For counts of detected and suppressed errors, rerun with: -v
==10541== ERROR SUMMARY: 40053 errors from 3 contexts (suppressed: 0 from 0)
Asking for help...
==10541== Conditional jump or move depends on uninitialised value(s)
Looks like you're trying to use a variable that might not have a value? Take a closer look at line 127 of dictionary.c.
Any ideas on where I've gone wrong? I thought since I initialised current to list this shouldn't be a problem. I tried initialising current to NULL before list but this hasn't made any difference.
*Edit
Added full code in since valgrind test refers to other lines:
// Implements a dictionary's functionality
#include <stdbool.h>
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <strings.h>
#include <ctype.h>
#include "dictionary.h"
// Define node in hash table
typedef struct node
{
char word[LENGTH + 1];
struct node *next;
}
node;
// Keep track of number of words in dictionary
int dict_size = 0;
// Number of buckets in hash table
const unsigned int HASHTABLE_SIZE = 65536;
// Declare Hash table
node *hashtable[HASHTABLE_SIZE];
// Returns true if word is in dictionary else false
bool check(const char *word)
{
// Make lowercase copy of word (so resulting index from hash function will match)
int n = strlen(word);
char word_copy[n+1];
for (int i = 0; i < n; i++)
{
word_copy[i] = tolower(word[i]);
}
// Add NULL terminating character to lowercase copy of word
word_copy[n] = '\0';
// Hash lowercase word to obtain index
int hash_index = hash(word_copy);
// Create pointer to node that points to the linked list at that element
node* trav = hashtable[hash_index];
// Traverse/search linked list for desired word
while (trav != NULL)
{
if (strcasecmp(trav->word, word_copy) == 0)
{
return true;
}
trav = trav->next;
}
return false;
}
// Hashes word to a number
unsigned int hash(const char *word)
{
unsigned int hash = 0;
for(int i = 0, n = strlen(word); i < n; i++)
{
hash = (hash << 2) ^ word[i];
}
return hash % HASHTABLE_SIZE;
}
// Loads dictionary into memory, returning true if successful else false
bool load(const char *dictionary)
{
//Open dictionary.h file
FILE* dict_ptr = fopen(dictionary, "r");
// Check to see if dictionary.h file pointer is NULL
if (dict_ptr == NULL)
{
fprintf(stderr, "Error: Could not open %s", dictionary);
return false;
}
// Create array of chars into which we can temporarily store each
char buffer[LENGTH + 1];
// Loop over whole to copy each string until we reach end of file (EOF)
while (fscanf(dict_ptr, "%s", buffer) != EOF)
{
// Create temporary node for current word
node* current = malloc(sizeof(node));
// Check if pointer to temporary node equals NULL
if (current == NULL)
{
return false;
}
// Copy current word into string field of node
strcpy(current->word, buffer);
// Implement hash function on current word to obtain hash table index value for current word
int index = hash(buffer);
// Add current word node to hashtable array
// If there are no nodes at that element, simply add node to that element
if (hashtable[index] == NULL)
{
hashtable[index] = current;
dict_size++;
}
// Else add current node to beginning of linked list at that element
else
{
current->next = hashtable[index];
hashtable[index] = current;
dict_size++;
}
}
fclose(dict_ptr);
return true;
}
// Returns number of words in dictionary if loaded else 0 if not yet loaded
unsigned int size(void)
{
return dict_size;
}
// Destroy function deletes an entire linked list recursively
void destroy(struct node* list)
{
// Initialise current node pointer to point to head of list
node* current_node = list;
// Recursion base case
if (current_node == NULL)
{
return;
}
destroy(current_node->next);
free(current_node);
}
// Unloads dictionary from memory, returning true if successful else false
bool unload(void)
{
for (int i = 0; i < HASHTABLE_SIZE; i++)
{
if (hashtable[i] == NULL)
{
continue;
}
destroy(hashtable[i]);
}
return true;
}
If you take a look at load:
node* current = malloc(sizeof(node));
// Check if pointer to temporary node equals NULL
if (current == NULL)
{
return false;
}
// Copy current word into string field of node
strcpy(current->word, buffer);
// Implement hash function on current word to obtain hash table index value for current word
int index = hash(buffer);
// Add current word node to hashtable array
// If there are no nodes at that element, simply add node to that element
if (hashtable[index] == NULL)
{
hashtable[index] = current;
dict_size++;
}
// Else add current node to beginning of linked list at that element
else
{
current->next = hashtable[index];
hashtable[index] = current;
dict_size++;
}
You allocate space for current, then copy a string into word. However, you only set next if the list isn't empty. When it is empty, you never set next. So when you later traverse the list, you're reading an uninitialized value.
You need to set next in that case as well:
// Add current word node to hashtable array
// If there are no nodes at that element, simply add node to that element
if (hashtable[index] == NULL)
{
current->next = NULL;
hashtable[index] = current;
dict_size++;
}
// Else add current node to beginning of linked list at that element
else
{
current->next = hashtable[index];
hashtable[index] = current;
dict_size++;
}
Note here that what you do in each case is the same, so you can consolidate them:
// Add current word node to hashtable array
current->next = hashtable[index];
hashtable[index] = current;
dict_size++;