0

after working on pset 5 speller for awhile, I've finally managed to make it run without any errors! However, the code's still incorrect when I check with check50 and valgrind. When I run valgrind through help50 the output says this

==411405== Invalid read of size 8
==411405==    at 0x423054: unload (dictionary.c:152)
==411405==    by 0x420BC0: main (speller.c:59)

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

From the lecture, David Malan went through this problem as well, and I understood that. However after going to line 152 (In my Unload function this line "cursor = cursor->next;" , I couldn't really identify where the problem is. I've looked at the other problems on this forum where others had the same problems as me, however I'm still lost..

Any help would be amazing, and this is my code

// Implements a dictionary's functionality

#include <stdbool.h>
#include <stdlib.h>
#include <stdio.h>
#include <cs50.h>
#include <ctype.h>
#include <string.h>
#include "dictionary.h"

//define node
typedef struct node
{
    char word[LENGTH + 1]; // LENGTH from disctionary.h
    struct node *next;

}
node;

//GLOBAL VARIABLES~~

 node *hashtable[TABLESIZE]; // TABLESIZE = 4294967296
long wordcount = 0; //To keep track of the sized of the dictionary
bool loaded = false; //Refer to speller.c for loaded

//Hash function by Reddit user "delpipity" cs50staff
//https://www.reddit.com/r/cs50/comments/1x6vc8/pset6_trie_vs_hashtable/cf9nlkn/

int hash_it(char* needs_hashing)
{
    unsigned int hash = 0;
    for (int i=0, n=strlen(needs_hashing); i<n; i++)
    {
         hash = (hash << 2) ^ needs_hashing[i];

    }
return hash % TABLESIZE;
}

// Loads dictionary into memory, returning true if successful else false
     bool load(const char *dictionary)
{
    // TODO
    FILE *file = fopen(dictionary, "r");
    node *newnode;

    //Check if file/dictionary could be opened
    if (file == NULL)
    {
        fprintf(stderr, "Could not open dictionary.\n");
        return false;

    }

     //read from dictionary and store it to pointer newnode->word
    do
    {
        //Malloc a new node of size node
        newnode = malloc(sizeof(node));
        if (newnode == NULL)
        {
            fprintf(stderr, "Could not malloc newnode\n");
            free (newnode);
            return false;

        }

        int hash = hash_it(newnode->word);
        node *head = hashtable[hash];

        if (head == NULL)
        {
            //insert newnode into hashtable
            hashtable[hash] = newnode;

        }
        else
        {
            //Correct way to stitch linked list thing. (Zamayla)
            newnode->next = hashtable[hash];
            hashtable[hash] = newnode;
        }

        wordcount++;

    }
    while(fscanf(file, "%s", newnode->word)!=EOF);

    if (feof(file))
    {
        free(newnode);
    }
    fclose(file);
    return true;

}

// Returns true if word is in dictionary else false
bool check(const char *word)
{
    // TODO
    int end = strlen(word); //end of word, to demarcate where where null pointer should go.
    char wordtmp[LENGTH + 1];

    wordtmp[end] = '\0';
    int hash = hash_it(wordtmp);
    node *cursor = hashtable[hash];

    while (cursor != NULL)
    {
        //do something
        if (strcmp(cursor->word, wordtmp) == 0)
        {
            //Word found in dictionary. strcmp returns 0 if both variables are the same
            return true;

        }
        else
        {
            //left arm thing
            cursor = cursor->next;
        }
    }

    return false;
}

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

    }
}
// Unloads dictionary from memory, returning true if successful else false
bool unload(void)
{
    // TODO
    for (long x = 0; x < TABLESIZE; x++)
    {
        node *cursor = hashtable[x];    // x = 0, so = head of the linked list. Hashtables are an array of linked list
                                       // so hashtable[0] is the head of the linked lists
        while (cursor != NULL)
        {
            node *temp = cursor;
            cursor = cursor->next; //<---VALGRIND PROBLEM 
            free(temp);

        }
    }
    return false;
}
2

I see two issues with unload. First, when it finishes, it returns false instead of true.

Now on to the main issue. Look at this code at the end of load.

if (feof(file))
{
    free(newnode);
}

This will free the last node created. Unfortunately, it contains the last word processed. When free() is called, it releases the memory but it does NOT reset the pointer to null.

The result is this. Since the last node created will be inserted as the first node in one of the linked lists in hashtable[], that node will be left pointing at invalid memory. When unload hits that entry, it will generate a seg fault.

Further, there are other issues. The hashtable[] array is not initialized, so every element contains random garbage data. The entire table should be initialized to NULL. Similarly to the previous issue, this should generate a seg fault or, by chance, might access valid memory elsewhere and not generate a seg fault, but will corrupt that memory instead.

When nodes are created, they are not initialized. They too contain garbage data. The word is never copied into the node. Obviously, all words are misspelled. There's probably more, but this looks like a work in progress.

There's a lot of work left here, but this will get you going. You should work on getting everything working correctly before worrying about fixing memory leaks.

If this answers your question, please click on the check mark to accept. Let's keep up on forum maintenance. ;-)

1
  • Thank you! Really helped! – Lim Lyn-Yang Mar 6 '18 at 17:00

You must log in to answer this question.

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