0

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.

}
1

In check, you forgot to set lowercaseword[wordlength] = '\0';. malloced memory is not initialised by default, and is not erased after freeing either. If that byte is not '\0', you might read outside of where you are allowed to read.

As it is after a return, free(lowercaseword); is never executed (memory leak). You would have to place it in front of any return inside check. You could completely avoid it by making lowercaseword an array instead of pointer, so the characters are placed on stack. Stack variables automatically cease to exist on exiting the block they were declared in.

Same for the fclose, which cannot be executed since it's behind a return. And hitting a return insta-leaves the current function (after evaluating the return value, of course).

| improve this answer | |
  • all seems obvious when you explain it so clearly. Thanks again ! – James Jun 3 '19 at 22:02

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .