CS50 speller pset 5 (accessed 1 byte that does not belong to me but can't find the byte)

Question

After running my code through help50 Valgrind, I got the following error message:

==6830== Invalid read of size 1 ==6830== at 0x4C33614: strcasecmp (in /usr/lib/valgrind/vgpreload_memcheck-amd64-linux.so) ==6830== by 0x401176: check (dictionary.c:52) ==6830== by 0x400CD9: main (speller.c:112)

Looks like you're trying to access 1 byte of memory that isn't yours? Did you try to index into an array beyond its bounds? Take a closer look at line 52 of dictionary.c.

I think it has something to do with my check function but line 52 is just an if statement and I can't figure out where I'm trying to access that 1 byte from.**

My code is below:

#include <stdbool.h>
#include <string.h>
#include <stdio.h>
#include <stdlib.h>
#include <ctype.h>
#include <strings.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
const unsigned int N = 1000;

//Number of words
unsigned int noWords = 0;

//Variable to check if dictionary loaded
bool isLoaded = false;

// Hash table
node *table[N];

// Returns true if word is in dictionary else false
bool check(const char *word)
{
    //Changing letters to lower case because case insensitive
    //Copy created because word argument is a constant. copy can be edited
    int n = strlen(word) + 1;
    char copy[LENGTH + 1];

    for (int i = 0; i < n; i++)
    {
        copy[i] = tolower(word[i]);
    }

    // Add null terminator to end string
    copy[n] = '\0';

    //Hash the word to convert it to index and check if it's in any of the linked lists
    int index = hash(copy);

    if (table[index] != NULL) //Check if word is in linked list
    {
        for (node *cursor = table[index]; cursor != NULL; cursor = cursor -> next)
        {
            if (strcasecmp(cursor -> word, copy) == 0)
            {
                return true;
            }
        }
    }

    return false;
}

// Hashes word to a number
unsigned int hash(const char *word)
{
    //Taken from http://www.cse.yorku.ca/~oz/hash.html (by djb2)
    unsigned long h = 5381;
    int c;

    while ((c = *word++))
    {
        c = tolower(c);
        h = (((h << 5) + h) + c) % N; /* hash * 33 + c*/
    }
    return h;
}

// Loads dictionary into memory, returning true if successful else false
bool load(const char *dictionary)
{
    char word[LENGTH + 1];

    //Open dictionary
    FILE *f = fopen(dictionary, "r");

    //Check if file can be opened
    if (f == NULL)
    {
        printf("%s\n", "File cannot be opened!");
        return false;
    }

    //Read strings from file
    while (fscanf(f, "%s", word) != EOF)
    {
        noWords++;

        node *newNodePointer = malloc(sizeof(node));
        if (newNodePointer == NULL)
        {
            unload();
            printf("Out of memory");
            return false;
        }

        int index = hash(word);//hashtable is an array of linked list. index helps insert node into hashtable
        strcpy(newNodePointer -> word, word);//Copies word from infile into new node's word field

        if (table[index] == NULL)//Check if same word already exists in the bucket
        {
            newNodePointer -> next = NULL;
            table[index] = newNodePointer;
        }
        else
        {
            newNodePointer -> next = table[index];
            table[index] = newNodePointer;
        }

        free(newNodePointer);
    }

    fclose(f);
    isLoaded = true;
    return true;

}

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

// Unloads dictionary from memory, returning true if successful else false
bool unload(void)
{
       //Check if there's even a loaded dictionary
    if (!isLoaded)
    {
        return false;
    }

    //Iterate through hashtable
    for (int i = 0; i < N; i++)
    {
        if (table[i] != NULL)
        {
            node *cursor = table[i];
            while (cursor != NULL)
            {
                node *tmp = table[i]; //tmp pointer continues pointing at table[i] while cursor points at next item in hashtable
                cursor = cursor -> next;
                free(tmp);
            }
        }
    }
    return true;
}

DinoCoderSaurus DinoCoderSaurus · Accepted Answer · 2020-06-26T21:53:23

The problem is from here in load: free(newNodePointer);. It just released the memory where the word and the next pointer are stored!

CS50 speller pset 5 (accessed 1 byte that does not belong to me but can't find the byte)

1 Answers