1
// Implements a dictionary's functionality

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

// Hash table
node *table[N];

/*this variable will keep track of how many words are there in the dictionary.
The size will eventually return word_counter as the Size function is supposed to
tell how many words are there in the dictionary.*/
int word_counter = 0;

// Returns true if the word is in the dictionary, else false
bool check(const char *word)
{
    // TODO


    //gets the index for the head of the Linked List in the Hash Table
    int hash_number = hash(word);

    //traverses Linked List to check for the word
    for(node* cursor = table[hash_number]; cursor != NULL; cursor = cursor->next)
    {
        if(strcasecmp(cursor->word, word) == 0)
        {
            //if the word is found, then the function will return true
            return true;
        }
    }

    /*after traversing the linked list, if the word is not found,
    then the function will return false */
    return false;
}

// Hashes word to a number
unsigned int hash(const char *word)
{
    // TODO
    /*Found this Hash function in Hash Table tutorial in HackerEarth
    URL of the tutorial - https://www.hackerearth.com/practice/data-structures/hash-tables/basics-of-hash-tables/tutorial/ */

    //calculates the length of the word
    int word_length = strlen(word);

    int sum = 0;
    for(int i = 0; i < word_length; i++)
    {
        sum = sum +((10*word[i]) + i + 1);
    }
    //using the modulo operator to make sure that the index of the Hashtable is within the bounds
    int hash_number = sum % N;
    return hash_number;
}

// Loads dictionary into memory, returning true if successful, else false
bool load(const char *dictionary)
{
    // TODO

    //Initializes all the buckets of the hash table to NULL pointer
    for(int i = 0; i < N; i++)
    {
        table[i] = NULL;
    }

    //Opening dictionary in read mode
    FILE* input_dictionary = fopen(dictionary, "r");

    //checking for NULL pointer
    if(input_dictionary == NULL)
    {
        printf("Invalid Input\n");
        return false;
    }

    //character array to store word
    char word_buffer[LENGTH + 1];

    /*This loop will go over the words & it will
    end when fscanf scans the last word indicating End Of File(EOF)*/
    while(fscanf(input_dictionary, "%s", word_buffer) != EOF)
    {
        //creating a new node by calling Malloc
        node* new_node = malloc(sizeof(node));
        //checking for NULL pointer
        if(new_node == NULL)
        {
            printf("Not enough memory for creating new node. Currently in Load function\n");
            return false;
        }

        /*copying the word into the word field of the node created
        & initilising the next field of the node to NULL*/
        strcpy(new_node->word, word_buffer);
        new_node->next = NULL;

        //calling hash function to get an index to the hash function
        int hash_number = hash(new_node->word);

        //this condition means that the list is empty
        if(table[hash_number] == NULL)
        {
            table[hash_number] = new_node->next;
        }

        /*We are inserting the node at the beginning of the linked list of the hash table.
        So we will make sure that new_node first points to the existing 1st element of the Linked list
        & the point the head node i.e. the table[hash_number] to the new_node.*/
        else
        {
            new_node->next = table[hash_number];
            table[hash_number] = new_node;
        }

        //incrementing number words counted by one.
        word_counter++;
    }
    return true;
}

// Returns the number of words in the dictionary if loaded, else 0 if not yet loaded
unsigned int size(void)
{
    // TODO

    /*returns the total number of words counted.
    Incrementation took place while Loading the words in the Load function. */
    return word_counter;
}

// Unloads dictionary from memory, returning true if successful, else false
bool unload(void)
{
    // TODO
    for(int i = 0; i < N; i++)
    {
        /*if the bucket of the Hash Table is not filled,
        it is empty. So the continue statement is used to go to the next iteration*/
        if(table[i] == NULL)
        {
            continue;
        }

        else
        {
            node* cursor = table[i];
            node* tmp = cursor;

            while(cursor != NULL)
            {
                cursor = cursor->next;
                free(tmp);
                tmp = cursor;
            }
        }
    }
    return true;
}

So I ran check50, Valgrind & compared it with the staff's solution. Here's the list of errors -

1.) Check50 is all red(except for the compilation & the exists part).

2.) Valgrind- In leak summary - "definitely lost: 8,013,096 bytes in 143,091 blocks" is written.

In Heap summary - 1.) 472 bytes in 1 blocks are still reachable in loss record 1 of 2

2.) 8,013,096 bytes in 143,091 blocks are definitely lost in loss record 2 of 2

3.) when I compared with the staff's solution, I got 2 columns. In left column there were words(lots of it) & on the right, there was mostly < symbol printed along with some occasional words.

I really don't know where the problem lies(my best guess is a problem in Load or Check). So It'd be a great help if someone points the error in the code.

0
1

There are 3 problems with this code.

  1. There's a logic error in load.
  2. The code doesn't handle letter case.
  3. Valgrind detects memory left at exit (after resolving #1).

Let's start in load. There's an issue with the way the tree is being built. Look at the following code:

    if(table[hash_number] == NULL)
    {
        table[hash_number] = new_node->next;
    }
    else
    {
        new_node->next = table[hash_number];
        table[hash_number] = new_node;
    }

The second condition inserts the address of the new node in table[hash], but the first condition inserts the address stored in new_node->next into table[hash]. Doesn't new_node->next contain NULL at that point??? Shouldn't the line in the IF code block be the same as in the ELSE block?

Next, the code doesn't handle words with different case letters. "The" and "the" will generate different hash values. Since I think you simply overlooked this, I'll let you have a first shot at it.

Finally, the valgrind result shows this (line numbers may be different for your run):

472 bytes in 1 blocks are still reachable in loss record 1 of 1
==819==    at 0x483B7F3: malloc (in /usr/lib/x86_64-linux-gnu/valgrind/vgpreload_memcheck-amd64-linux.so)
==819==    by 0x4A29AAD: __fopen_internal (iofopen.c:65)
==819==    by 0x4A29AAD: fopen@@GLIBC_2.2.5 (iofopen.c:86)
==819==    by 0x401AC0: load (dictionary.c:86)
==819==    by 0x4012BE: main (speller.c:45)

The important reference here is "load (dictionary.c:86)" That line is:

FILE* input_dictionary = fopen(dictionary, "r");

Anytime valgrind refers to a line of code with an fopen() call, the first question is this: "Was the file closed later?"

Sorry about the previous (deleted) answer. Somehow, when I tried to load your code into my IDE, it didn't take, so I solved a different issue. My bad.

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

1
  • Yeah, I found these errors last night & fixed them. Anyway, thanks for your time. Sep 13 at 1:37

You must log in to answer this question.

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