0

I have successfully implemented pset5 speller using a hash table, but am facing some residual issues with the unload() function. I am unable to resolve a number of errors that are identified by running the program through valgrind.

I'm not sure whether the errors only involve with code from the unload function or other sections also. There seem to be quite a few errors and I am not sure whether it is the same issue causing all of them. How should I go about identifying the errors and then fixing them?

Thanks, and any help would be truly appreciated!

Here is the console output:

==2093== Invalid read of size 1
==2093==    at 0x4C2F1B1: strcmp (in /usr/lib/valgrind/vgpreload_memcheck-amd64-linux.so)
==2093==    by 0x4235BC: size (dictionary.c:125)
==2093==    by 0x421576: main (speller.c:145)
==2093==  Address 0x5d48440 is 0 bytes inside a block of size 56 free'd
==2093==    at 0x4C2BDEC: free (in /usr/lib/valgrind/vgpreload_memcheck-amd64-linux.so)
==2093==    by 0x423034: load (dictionary.c:93)
==2093==    by 0x4209F2: main (speller.c:40)
==2093== 
==2093== Invalid read of size 8
==2093==    at 0x423680: size (dictionary.c:123)
==2093==    by 0x421576: main (speller.c:145)
==2093==  Address 0x5d48470 is 48 bytes inside a block of size 56 free'd
==2093==    at 0x4C2BDEC: free (in /usr/lib/valgrind/vgpreload_memcheck-amd64-linux.so)
==2093==    by 0x423034: load (dictionary.c:93)
==2093==    by 0x4209F2: main (speller.c:40)
==2093== 
==2093== Invalid read of size 8
==2093==    at 0x423270: unload (dictionary.c:171)
==2093==    by 0x4215C4: main (speller.c:153)
==2093==  Address 0x6eb9bf0 is 48 bytes inside a block of size 56 free'd
==2093==    at 0x4C2BDEC: free (in /usr/lib/valgrind/vgpreload_memcheck-amd64-linux.so)
==2093==    by 0x4231B8: unload (dictionary.c:168)
==2093==    by 0x4215C4: main (speller.c:153)
==2093== 
==2093== Invalid free() / delete / delete[] / realloc()
==2093==    at 0x4C2BDEC: free (in /usr/lib/valgrind/vgpreload_memcheck-amd64-linux.so)
==2093==    by 0x423282: unload (dictionary.c:172)
==2093==    by 0x4215C4: main (speller.c:153)
==2093==  Address 0x6eb9bc0 is 0 bytes inside a block of size 56 free'd
==2093==    at 0x4C2BDEC: free (in /usr/lib/valgrind/vgpreload_memcheck-amd64-linux.so)
==2093==    by 0x4231B8: unload (dictionary.c:168)
==2093==    by 0x4215C4: main (speller.c:153)
==2093== 
==2093== Invalid free() / delete / delete[] / realloc()
==2093==    at 0x4C2BDEC: free (in /usr/lib/valgrind/vgpreload_memcheck-amd64-linux.so)
==2093==    by 0x4231B8: unload (dictionary.c:168)
==2093==    by 0x4215C4: main (speller.c:153)
==2093==  Address 0x6ebaac0 is 0 bytes inside a block of size 56 free'd
==2093==    at 0x4C2BDEC: free (in /usr/lib/valgrind/vgpreload_memcheck-amd64-linux.so)
==2093==    by 0x423028: load (dictionary.c:92)
==2093==    by 0x4209F2: main (speller.c:40)
==2093== 

WORDS MISSPELLED:     955
WORDS IN DICTIONARY:  143091
WORDS IN TEXT:        17756
TIME IN load:         3.35
TIME IN check:        43.57
TIME IN size:         0.14
TIME IN unload:       0.36
TIME IN TOTAL:        47.42

==2093== 
==2093== HEAP SUMMARY:
==2093==     in use at exit: 1,456 bytes in 26 blocks
==2093==   total heap usage: 143,119 allocs, 143,121 frees, 8,015,688 bytes allocated
==2093== 
==2093== 1,456 bytes in 26 blocks are definitely lost in loss record 1 of 1
==2093==    at 0x4C2AB80: malloc (in /usr/lib/valgrind/vgpreload_memcheck-amd64-linux.so)
==2093==    by 0x42277B: load (dictionary.c:50)
==2093==    by 0x4209F2: main (speller.c:40)
==2093== 
==2093== LEAK SUMMARY:
==2093==    definitely lost: 1,456 bytes in 26 blocks
==2093==    indirectly lost: 0 bytes in 0 blocks
==2093==      possibly lost: 0 bytes in 0 blocks
==2093==    still reachable: 0 bytes in 0 blocks
==2093==         suppressed: 0 bytes in 0 blocks
==2093== 
==2093== For counts of detected and suppressed errors, rerun with: -v
==2093== ERROR SUMMARY: 1288 errors from 9 contexts (suppressed: 0 from 0)

Helping with...                                                                                                                                                                                                    

==2093== Invalid read of size 1
==2093==    at 0x4C2F1B1: strcmp (in /usr/lib/valgrind/vgpreload_memcheck-amd64-linux.so)
==2093==    by 0x423B15: check (dictionary.c:151)
==2093==    by 0x4213C3: main (speller.c:113)

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 151 of dictionary.c.

And here is the code I currently have for dictionary.c.

// Implements a dictionary's functionality

#include <ctype.h>
#include <stdbool.h>
#include <stdio.h>
#include <stdlib.h>
#include <string.h>

#include "dictionary.h"

// Represents number of buckets in a hash table
#define N 26

// Represents a node in a hash table
typedef struct node
{
    char word[LENGTH + 1];
    struct node *next;
}
node;

// Represents a hash table
node *hashtable[N];

// Hashes word to a number between 0 and 25, inclusive, based on its first letter
unsigned int hash(const char *word)
{
    int hash = 0, n;
    for (int i = 0; word[i] != '\0'; i++) 
    {
        if (isalpha(word[i]))
        {
            n = tolower(word[i]) - 'a' + 1;
        }
        else
        {
            n = 27;
        }
        hash = ((hash << 3) + n) % N;
    }
    return hash;
}

// Loads dictionary into memory, returning true if successful else false
bool load(const char *dictionary)
{
    // Initialize hash table
    for (int i = 0; i < N; i++)
    {
        hashtable[i] = malloc(sizeof(node));
    }

    // Open dictionary
    FILE *file = fopen(dictionary, "r");
    if (file == NULL)
    {
        unload();
        return false;
    }

    // Buffer for a word
    char word[LENGTH + 1];
    int wordHash;
    fseek(file, 0, SEEK_SET);


    // Insert words into hash table
    node *tmpptr;
    node *newptr;

    while (fscanf(file, "%s\n", word) != EOF)
    {
        // generate hash of word
        wordHash = hash(word);

        // copy word to hash table
        if (hashtable[wordHash]->word[0] != '\0')
        {
            tmpptr = malloc(sizeof(node));
            strcpy(tmpptr->word, word);
            tmpptr->next = hashtable[wordHash];
            hashtable[wordHash] = tmpptr;
        }
        else
        {
            newptr = malloc(sizeof(node));
            strcpy(newptr->word, word);
            newptr->next = NULL;
            hashtable[wordHash] = newptr;
        }
    }
    free(tmpptr);
    free(newptr);

    // Close dictionary
    fclose(file);

    // Indicate success
    return true;
}

// Returns number of words in dictionary if loaded else 0 if not yet loaded
unsigned int size(void)
{
    bool loaded = false;
    for (int i = 0; i < N; i++)
    {
        if (hashtable[i] != NULL)
        {
            loaded = true;
        }
    }

    if (loaded == false)
    {
        return 0;
    }
    else
    {
        unsigned int numWords = 0;
        for (int i = 0; i < N; i++)
        {
            for (node *ptr = hashtable[i]; ptr != NULL; ptr = ptr->next)
            {
                if(strcmp(ptr->word, "") != 0)
                {
                    numWords++;
                }
            }
        }
        return numWords;
    }
}

// Returns true if word is in dictionary else false
bool check(const char *word)
{
    // convert word to lower case
    // hash the word
    // in the relevant linked list, compare each word until reaching the end of the list
    char word2[strlen(word)+1];
    for (int i = 0; i < strlen(word); i++)
    {
        word2[i] = tolower(word[i]);
    }
    word2[strlen(word)] = '\0';

    int wordHash = hash(word2);
    for (node *ptr = hashtable[wordHash]; ptr != NULL; ptr = ptr->next)
    {
        if (strcmp(ptr->word, word2) == 0)
        {
            return true;
        }
    }
    return false;
}

// Unloads dictionary from memory, returning true if successful else false
bool unload(void)
{
    node *currptr;
    node *tmpptr;

    for (int i = 0; i < N; i++)
    {
        currptr = hashtable[i];
        free(hashtable[i]);
        while(currptr != NULL)
        {
            tmpptr = currptr->next;
            free(currptr);
            currptr = tmpptr;
        }
    }
    tmpptr = currptr;
    free(tmpptr);

    return true;
}
0

malloc returns a pointer to some memory. It makes no guarantees on its content, initially probably all zeroes (so you won't find secrets of another application), but whatever was there previously. I don't get why you malloc an initial node anyway, an empty linked list can be described by just a NULL pointer.

Later in load, you free nodes you just installed in your hash table, meaning they are still in use.

BTW, there's no real difference whether the linked list is empty or not, inserting at the front is always the same steps. Set the new node's next pointer to the current list head (whether NULL or not), make new node the new list head.

In size, you could always use that second for loop. If you used NULL instead of dummy nodes for empty list, you could even avoid testing the word.

And if you want to be much faster, just count the words in load, save in a global variable, and return that number in size.

check looks correct to me.

unload is scary.

        currptr = hashtable[i];
        free(hashtable[i]);

First you keep another pointer to the node at hashtable[i]. Then you free that memory, effectively invalidating the pointer you just assigned to, and which you use inside the loop. Remove that free(hashtable[i]);.

And also remove that free at the end of unload, it makes no sense to me, this would always be a free(NULL).

You must log in to answer this question.

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