I am currently taking CS50x and am on Pset5: Speller. My code works as intended, however when I run the check50 function my program fails Valgrind.

This is particularly confusing to me because when I run Valgrind on my program with the help50, it passes with no memory leaks. I ran help50 Valgrind on my program after changing the default dictionary to the dictionaries/small, and it still passed.

Here is my code and the error log I get from check50. I believe the Valgrind error is from not using fclose() on the file, but if I include fclose() then my program fails when ran with a "munmap_chunk(): invalid pointer".

If anyone could help me out or had any idea where I should look I would be most grateful!

// Implements a dictionary's functionality

#include <ctype.h>
#include <stdbool.h>
#include <stdio.h>
#include <string.h>
#include <strings.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 bucket for Hash Table
const unsigned int N = 676;

// Hash table
node *table[N];

int word_counter = 0;

// Returns true if word is in dictionary, else false
bool check(const char *word)
{
    // TODO
    int index = hash(word);
    node *cursor = table[index];
    //printf("cursor: %s\n", cursor->word);

    while (cursor != NULL)
    {
        if (strcasecmp(word, cursor->word) == 0)
        {
            return true;
        }
    cursor = cursor->next;

    }

    return false;
}

// Hashes word to a number
unsigned int hash(const char *word)
{
    // TODO: Improve this hash function

    unsigned int index = 0;
    for (int i = 0; i < 26; i  )
    {
        if (word[0] == i   'a' || word[0] == i   'A')
        {
            index  = i * 26;
        }

        if (word[1] == i   'a' || word[1] == i   'A')
        {
            index  = i;
        }
    }

return index;
}

// Loads dictionary into memory, returning true if successful, else false
bool load(const char *dictionary)
{
    FILE *dict_file = fopen(dictionary, "r");
    if (dict_file == NULL)
    {
        return false;
    }

    table_clear();

    // Use fscanf() to look at each string in the dictionary and store to buffer
    char *buffer = malloc(sizeof(LENGTH   1));
    if (buffer == NULL)
    {
        return false;
    }
    while (fscanf(dict_file, "%s", buffer) != EOF)
    {
        // Create a new memory space for each dictionary word, and store it here
        node *n = malloc(sizeof(node));
        if (n == NULL)
        {
            free(buffer);
            return false;
        }
        // Copy each word from buffer to the location (*dict_entry).word
        strcpy(n->word, buffer);
        n->next = NULL;

        // Use hash function to find the hash value of the dictionary word
        int index = hash(n->word);
        if (table[index] != NULL)
        {
            n->next = table[index];
        }
        table[index] = n;
        n = NULL;
        free(n);
        word_counter  ;
    }
    //fclose(dict_file); <----- If activate, this line causes the munmap_chunk: invalid pointer error
    free(buffer);
    return true;
}

// Returns number of words in dictionary if loaded, else 0 if not yet loaded
unsigned int size(void)
{
    return word_counter;
}

// Unloads dictionary from memory, returning true if successful, else false
bool unload(void)
{
     for (int i = 0; i < N; i  )
     {
        node *cursor = table[i];
        while (cursor != NULL)
        {
            cursor = cursor->next;
            free(table[i]);
            table[i] = cursor;
        }

        free(cursor);
     }

    return true;
}

// Sets every value in table to NULL
void table_clear(void)
{
    for (int i = 0; i < N; i  )
    {
        table[i] = NULL;
    }
    return;
}

**Cause valgrind tests failed; see log for more information

LOG:
running valgrind --show-leak-kinds=all --xml=yes --xml-file=/tmp/tmpr2rknwok -- ./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...
Invalid write of size 1: (file: dictionary.c, line: 88)
Invalid read of size 1: (file: dictionary.c, line: 99)
472 bytes in 1 blocks are still reachable in loss record 1 of 1: (file: dictionary.c, line: 74)

See above for exlaination

CodePudding user response：

There are numerous problems with the program as pointed out in the comments, but the most likely culprit for the valgrind error report is this dynamic allocation:

char *buffer = malloc(sizeof(LENGTH   1));

It allocates the sizeof the expression (LENGTH 1) number of bytes, which is most likely the same as doing sizeof(int) - which is often 4 - and 4 bytes isn't going to be able to store words longer than 3 chars. I say most likely because I don't know the type of LENGTH, but I'm assuming it's an int, and in that case, you effectively do char *buffer = malloc(sizeof(int));.

It should be:

char *buffer = malloc(LENGTH   1);