0

My speller "seems" to work well as compared to the staff's solution: find the correct number of WORDS MISSPELLED (644 of austinpower.txt), correct number of WORDS IN DICTIONARY (143091 of dictionaries/large) and correct number of WORDS IN TEXT (19190 of austinpower.txt), and it also passes the valgrind test (0 errors).

However, it failed the check50 and the error message showed "valgrind tests failed" in every check points. I'm confused. Could anyone point out where the problem is?

My code:

/**
 * Implements a dictionary's functionality.
 */
#include <stdio.h>
#include <stdbool.h>
#include <stdlib.h>
#include <string.h>
#include <ctype.h>
#include "dictionary.h"

typedef struct node       //define the struct of hash table
{
    char word[LENGTH+1];  // +1 is for the \0, indicating end of the word
    struct node *next;
}
    node;

node *hashtable[27]; //  create a hash table. 26 buckets of this hashtable (to store entire dictionary) + 1 bucket for apostrophe
// each element of array is a node * (node pointer)



/**
 * Loads dictionary into memory. Returns true if successful else false.
 */
int hash_function(char);           // implement the hash function
int dic_count = 0; // dictionary count

bool load(const char *dictionary)
{
    FILE *dic_ptr = fopen(dictionary, "r"); // open the dictionary
    if (dic_ptr == NULL)
    {
        fprintf(stderr, "Cannot open that dictionary.\n");
        return false;
    }

char dic_word[LENGTH+1]; // define word for dictionary

while (fscanf(dic_ptr, "%s", dic_word) != EOF) // scan inside the dictionary word by word       ?? word in dict??
{
    dic_count++;
    node *new_node = malloc(sizeof(node)); // create a new node (called new_node) to store the scanned word from dictionary.
    if (new_node == NULL) // whenever make a new node, always check that the pointer to that node doesn't return NULL.
    {
        unload();
        return false;
    }

    strcpy(new_node->word, dic_word); // string strcpy(string destination, string source) --> (new_node, dictionary)

    // finish storing the dic_word in the new_node
    // start to put it into the hashtable-> linked list

    char first_letter = dic_word[0]; // assign the 1st letter of dic_word as a char
    int index = hash_function(first_letter); // hash the word: output index (hash_code) from 1st letter via hash_function

    // populate the hashtable
    // if this bucket's node pointer is not yet assigned, make a head for this bucket
    if (hashtable[index] == NULL) // hashtable[index] is the head pointer (if it points to NULL, then:
    {
        hashtable[index] = new_node;
        new_node->next = NULL;
    }
    else // already have previous node, just link to it
    {
        new_node->next = hashtable[index];  // new_node point to the pointee of head (both head and new_node point to the same node, aka previous node/word
        hashtable[index] = new_node;  // then the head point to the new_node
    }
}
return true;
}

int hash_function(char c)
{
    int x;
    if (isalpha(c))
    {
        char l = tolower(c);
        int x = l - 97;                   // a is 0, b is 1, c is 2... so on
        return x;                         // x = index (hash_code)
    }
    else if (c == '\'')                  // apostrophe
    {
        x = 26;                         // put in the hashtable[26]
        return x;
    }
    else
    {
        x = 30;           // not fit in the hashtable with 27 buckets
        return x;
    }
}


/**
 * Returns true if word is in dictionary else false.
 */
bool check(const char *word)    // this "word" is from text
{
    // transform to lowercase
    char buffer[LENGTH+1];
    strcpy(buffer, word);

    for (int i = 0; word[i] != '\0'; i++)
    {
        if (isalpha(word[i]))
        {
            buffer[i] = tolower(word[i]);
        }
        else if (word[i] == 39)  // ASCII for the apostrophe
        {
            buffer[i] = '\'';
        }
    }

    int index = hash_function(word[0]); // 1st letter
    node *cursor = hashtable[index];  // create the cursor, then go to the 
correct bucket
    while (cursor != NULL)
    {
        int x = strcmp(buffer, cursor->word);
        if (x == 0)
        {
            return true; // the same!
        }
        else // x != 0
        {
            cursor = cursor->next; // go to the next node
        }
    }
    return false;
}


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



/**
 * Unloads dictionary from memory. Returns true if successful else false.
 */
bool unload(void)
{
    for (int i = 0; i < 26; i++)
    {
        node *cursor = hashtable[i];
        while (cursor != NULL)
        {
            node *temp = cursor;
            cursor = cursor->next;
            free(temp);
        }
    }
    return true;
}

Thank you in advance!

2

As always, it's most helpful to post actual results in the question. I ran the code and found the following result in valgrind:

==1350== 
==1350== HEAP SUMMARY:
==1350==     in use at exit: 568 bytes in 1 blocks
==1350==   total heap usage: 13 allocs, 12 frees, 1,752 bytes allocated
==1350== 

This means that there was 1 block of 568 bytes still in use in memory that hadn't been released by the program when it ended. It should be 0 bytes in 0 blocks.

I know the cause, but I don't think you have had a chance to chase it down. What could still be out there? Was something overlooked? ;-)

I'll let you work on it first, but if you can't figure it out, leave a comment and I'll spill the beans so that you can close this question out. ;-D

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

8
  • Thank you for the hint! I indeed did not look into the valgrind results line by line. Let me figure it out first. Thank you again! – EdWSY Sep 20 '17 at 7:28
  • I found that I missed the fclose()! After adding fclose() in the end of load(), valgrind says 0 bytes in 0 blocks in use, but instead 14 errors generated: invalid read and invalid write. I guess I may too early fclose the dictionary so that the following functions can not reach that chunks of memory? Is this the right direction? – EdWSY Sep 20 '17 at 7:46
  • That's interesting. I added the fclose and it worked fine. WHERE did you add the fclose? – Cliff B Sep 20 '17 at 7:48
  • right after the while loop of fscanf – EdWSY Sep 20 '17 at 7:51
  • At the point where you placed the fclose, is the code done with the file? Doesn't sound like it. – Cliff B Sep 20 '17 at 7:52

You must log in to answer this question.

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