У меня проблемы с прохождением проверки Valgrind для pset5 в Гарвардском курсе CS50. Я считаю, что это проблема с моей функцией загрузки или выгрузки, которая не назначает или не освобождает оба поля в структуре узла.
#include <ctype.h>
#include <stdbool.h>
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <strings.h>
#include "dictionary.h"
// Number of buckets in hash table
#define HASH_BUCKETS 10000
// Represents a node in a hash table
typedef struct node
{
char word[LENGTH + 1];
struct node *next;
}
node;
// Declare hash table
node *hashtable[HASH_BUCKETS];
// Hashes word to a number
int hash(const char *hash_word)
{
// Hash function provided by delipity
unsigned int hash = 0;
for (int i = 0, n = strlen(hash_word); i < n; i++)
{
hash = (hash << 2) ^ hash_word[i];
}
return hash % HASH_BUCKETS;
}
// Initialize word counter for dictionary size
int word_count = 0;
// Set all hash table heads to NULL initially
void null(void)
{
for (int i = 0; i < HASH_BUCKETS; i++)
{
hashtable[i] = NULL;
}
}
// Loads dictionary into memory, returning true if successful else false
bool load(const char *dictionary)
{
// open dictionary file
const char *infile = dictionary;
FILE *inptr = fopen(infile, "r");
if (inptr == NULL)
{
return false;
}
// initialize buffer array to read into
char wordbuffer[LENGTH + 1];
// read into buffer array, 1 word at a time, until EOF is reached
while (fscanf(inptr, "%s", wordbuffer) != EOF)
{
// allocate memory and return pointer to said memory
node *n = malloc(sizeof(node));
if (n == NULL)
{
return false;
}
// copy our word from our buffer array into our word field in our node
strcpy(n -> word, wordbuffer);
// pass our word into a hash function, returning a integer corresponding to our hash table
int key = hash(n -> word);
// initialize head of linked list to point at the proper bucket
node *head = hashtable[key];
// Add n to the front of the linked list
if (head == NULL)
{
hashtable[key] = n;
word_count++;
}
else
{
n -> next = hashtable[key];
hashtable[key] = n;
word_count++;
};
}
fclose(inptr);
return true;
}
// Returns true if word is in dictionary else false
bool check(const char *word)
{
// create copy of word to check
int n = strlen(word);
char word_copy[n + 1];
// change the word to all lowercase to receive same hash_index as lowercase dictionary hash_index
for (int i = 0; i < n; i++)
{
word_copy[i] = tolower(word[i]);
}
// add null terminator to end of string
word_copy[n] = '\0';
// hash the word copy
int h = hash(word_copy);
// initialize a navigator node to compare with the loaded dictionary
node *nav = hashtable[h];
// iterate through hash_table to check for the input word
while (nav != NULL)
{
// check if strcasecmp returns 0 - exact match
if (strcasecmp(nav -> word, word_copy) == 0)
{
return true;
}
// go to the next element in the linked list
else
{
nav = nav -> next;
}
}
// if the nav makes it through the list, then the input word is not there
return false;
}
// Returns number of words in dictionary if loaded else 0 if not yet loaded
unsigned int size(void)
{
return word_count;
}
// Unloads dictionary from memory, returning true if successful else false
bool unload(void)
{
// Initialize head and track
for (int i = 0; i < HASH_BUCKETS; i++)
{
node *track = hashtable[i];
node *tmp = NULL;
// Iterate through the linked list
while (track != NULL)
{
tmp = track;
track = track -> next;
free(tmp);
}
free(track);
}
return true;
}
Мой Valgrind выплевывает это:
==1735== Conditional jump or move depends on uninitialised value(s)
==1735== at 0x4013E9: unload (dictionary.c:155)
==1735== by 0x400E59: main (speller.c:152)
==1735== Uninitialised value was created by a heap allocation
==1735== at 0x4C2FB0F: malloc (in /usr/lib/valgrind/vgpreload_memcheck-amd64-linux.so)
==1735== by 0x4011BD: load (dictionary.c:67)
==1735== by 0x4009B4: main (speller.c:40)
==1735==
==1735== Conditional jump or move depends on uninitialised value(s)
==1735== at 0x4C30CF1: free (in /usr/lib/valgrind/vgpreload_memcheck-amd64-linux.so)
==1735== by 0x40141F: unload (dictionary.c:161)
==1735== by 0x400E59: main (speller.c:152)
==1735== Uninitialised value was created by a heap allocation
==1735== at 0x4C2FB0F: malloc (in /usr/lib/valgrind/vgpreload_memcheck-amd64-linux.so)
==1735== by 0x4011BD: load (dictionary.c:67)
==1735== by 0x4009B4: main (speller.c:40)
==1735==
==1735==
==1735== HEAP SUMMARY:
==1735== in use at exit: 0 bytes in 0 blocks
==1735== total heap usage: 143,096 allocs, 143,096 frees, 8,023,416 bytes allocated
==1735==
==1735== All heap blocks were freed -- no leaks are possible
==1735==
==1735== For counts of detected and suppressed errors, rerun with: -v
==1735== ERROR SUMMARY: 20773 errors from 3 contexts (suppressed: 0 from 0)
Я попытался инициализировать хеш-таблицу так, чтобы она указывала на NULL перед загрузкой:
void null(void)
{
for (int i = 0; i < HASH_BUCKETS; i++)
{
hashtable[i] -> next = NULL
}
}
но как это является вспомогательным файлом, и мне не разрешено редактировать исполняемый файл «speller. c», я не знаю, как бы я его назвал.
speller. c:
// Implements a spell-checker
#include <ctype.h>
#include <stdio.h>
#include <sys/resource.h>
#include <sys/time.h>
#include "dictionary.h"
// Undefine any definitions
#undef calculate
#undef getrusage
// Default dictionary
#define DICTIONARY "dictionaries/large"
// Prototype
double calculate(const struct rusage *b, const struct rusage *a);
int main(int argc, char *argv[])
{
// Check for correct number of args
if (argc != 2 && argc != 3)
{
printf("Usage: ./speller [DICTIONARY] text\n");
return 1;
}
// 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
for (int c = fgetc(file); c != EOF; c = fgetc(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 ((c = fgetc(file)) != EOF && 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 ((c = fgetc(file)) != EOF && 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;
}
// Returns number of seconds between b and a
double calculate(const struct rusage *b, const struct rusage *a)
{
if (b == NULL || a == NULL)
{
return 0.0;
}
else
{
return ((((a->ru_utime.tv_sec * 1000000 + a->ru_utime.tv_usec) -
(b->ru_utime.tv_sec * 1000000 + b->ru_utime.tv_usec)) +
((a->ru_stime.tv_sec * 1000000 + a->ru_stime.tv_usec) -
(b->ru_stime.tv_sec * 1000000 + b->ru_stime.tv_usec)))
/ 1000000.0);
}
}