0

I can compile pset5 but when I run the program, it treats all words misspelled. Also, Valgrind reports 15 errors and help50 hints that I am trying to access 1 byte of memory that isn't mine. I have no idea about it. Appreciate for any help. Thanks in advance.

Here is my code:

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

#define SIZE 50

// structure for linked lists
typedef struct node
{
    // word to be stored in the node with 1 string terminator
    char word[LENGTH + 1];
    // pointer to the next node in the list
    struct node *next;
}
node;

// declare hash function and its key is the word in dictionary
unsigned int hash(const char *key)
{
    // hash on first letter of string
    int index = toupper(key[0]) - 'A';
    return index % SIZE;
}

// declare hash table which is an array of node pointers and default to NULL
node *hashtable[SIZE];

// declare word from dictionary
char word[LENGTH + 1];

char *wordcopy = NULL;

node *cursor = NULL;

node *new_node = NULL;

// declare word counter
int counter = 0;

/**
 * Returns true if word is in dictionary else false.
 */
bool check(const char *word)
{
    // store copy of word in lowercase
    int wordlength = strlen(word);
    wordcopy = malloc(wordlength * sizeof(char));

    // copy word from dictionary
    for(int i = 0; i < wordlength; i++)
    {
        wordcopy[i] = tolower(word[i]);
    }

    // create a cursor node pointer
    cursor = malloc(sizeof(node));

    // hash word from dictionary
    int hashkey = hash(word);

    // point to where head node points to
    cursor = hashtable[hashkey];

    // check until end of the list
    while(cursor != NULL)
    {
        // check if two strings are case-insensitively equal
        if(strcmp(cursor->word, wordcopy) == 0)
        {
            return true;
        }
        // move cursor to next node
        cursor = cursor->next; 
    }

    free(wordcopy);
    free(cursor);

    return false;
}

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

    // open dictionary file
    FILE *dict = fopen(dictionary, "r");

    // check if opened dictionary
    if(dict == NULL)
    {
        printf("Could not open %s.\n", dictionary);
        return false;
    }

    // scan dictionary word by word until end of file
    while(fscanf(dict, "%s", dictword) != EOF)
    {
        // get hashkey for the word from dictionary
        int hashkey = hash(dictword);

        // create memory for new node
        new_node = malloc(sizeof(node));

        // check if no memory for new node
        if(new_node == NULL)
        {
            printf("No memory allocated to the new node. Program ended.");
            return false;
        }

        // insert word into hash table
        if(hashtable[hashkey] == NULL)
        {
            // make hashtable[hash] point to new_node
            hashtable[hashkey] = new_node;

            // new_node is the last node in the linked list
            new_node->next = NULL;
        }
        else
        {
            // point temporary node to where hashtable[hash] is pointing
            new_node->next = hashtable[hashkey];

            // point hashkey to new_node
            hashtable[hashkey] = new_node;
        }

        // copy word into new node
        strcpy(new_node->word, dictword);

        // count word number
        counter++;
        free(new_node);
    }

    fclose(dict);
    return true;
}

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

/**
 * Unloads dictionary from memory. Returns true if successful else false.
 */
bool unload(void)
{
    return false;
}

And here is Valgrind summary with help50:

==6596== 
==6596== HEAP SUMMARY:
==6596==     in use at exit: 1,131 bytes in 21 blocks
==6596==   total heap usage: 44 allocs, 23 frees, 2,447 bytes allocated
==6596== 
==6596== 11 bytes in 1 blocks are definitely lost in loss record 1 of 2
==6596==    at 0x4C2AB80: malloc (in /usr/lib/valgrind/vgpreload_memcheck-amd64-linux.so)
==6596==    by 0x401219: check (dictionary.c:54)
==6596==    by 0x400DE7: main (speller.c:112)
==6596== 
==6596== 1,120 bytes in 20 blocks are definitely lost in loss record 2 of 2
==6596==    at 0x4C2AB80: malloc (in /usr/lib/valgrind/vgpreload_memcheck-amd64-linux.so)
==6596==    by 0x401272: check (dictionary.c:63)
==6596==    by 0x400DE7: main (speller.c:112)
==6596== 
==6596== LEAK SUMMARY:
==6596==    definitely lost: 1,131 bytes in 21 blocks
==6596==    indirectly lost: 0 bytes in 0 blocks
==6596==      possibly lost: 0 bytes in 0 blocks
==6596==    still reachable: 0 bytes in 0 blocks
==6596==         suppressed: 0 bytes in 0 blocks
==6596== 
==6596== For counts of detected and suppressed errors, rerun with: -v
==6596== ERROR SUMMARY: 15 errors from 5 contexts (suppressed: 0 from 0)

Helping with...                                                                    

==6596== Invalid read of size 1
==6596==    at 0x4C2F1B1: strcmp (in 
/usr/lib/valgrind/vgpreload_memcheck-amd64-linux.so)
==6596==    by 0x4012C1: check (dictionary.c:75)
==6596==    by 0x400DE7: 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 75 of 
dictionary.c.
1

In check:

  • wordcopy = malloc(wordlength * sizeof(char)); allocates too little space, should be malloc((wordlength+1) * sizeof(char));, and don't forget the wordcopy[wordlength] = '\0'; null terminator, cause of the invalid read
  • you create a new node in cursor = malloc(sizeof(node));, but throw away the pointer using cursor = hashtable[hashkey]; (remove that malloc and the free(cursor)). That's the 1120 bytes in 20 blocks
  • shouldn't int hashkey = hash(word); use the lowercased wordcopy, and not word?
  • free wordcopy before returning true on match, that's the 11 bytes in 1 block

In load:

  • You don't have to check if(hashtable[hashkey] == NULL), just use the code from the else path, it already covers the other.
  • You just installed new_node in a linked list, so don't free it immediately, but later in unload (as part of the linked lists)
1
  • Thanks a lot! It works now!
    – dreammoon
    Feb 23 '17 at 15:04

You must log in to answer this question.

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