0
// Implements a dictionary's functionality

#include <strings.h>
#include <stdlib.h>
#include <ctype.h>
#include <stdio.h>
#include <stdbool.h>
#include <string.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 hash table = 26 raised to 4.
const unsigned int N = 456976;

//keep track of number of nodes in hash table.
int nodes = 0;

// Hash table
node *table[N];

// Returns true if word is in dictionary, else false
bool check(const char *word)
{
    int list = hash(word);

    if (table[list] != NULL)
    {
        node *cursor = table[list];
        while(cursor != NULL)
        {
            if (strcasecmp(word,cursor->word) == 0)
            {
                return true;
            }
            cursor = cursor->next;
        }
    }

    return false;
}

// Hashes word to a number
unsigned int hash(const char *word)
{
    unsigned int hash_code = 0;
    unsigned int count;

    //case insensitive.
    char buffer[LENGTH + 1];
    strcpy(buffer,word);

    for (int i = 0, s = strlen(word); i < s; i++)
    {
        buffer[i] = tolower(buffer[i]);
    }

     //hash function.
     for(count = 0; word[count] != '\0'; count++)
     {
         hash_code = word[count] + (hash_code << 6) + (hash_code << 16) - hash_code;
     }
     return (hash_code % N);
}

// Loads dictionary into memory, returning true if successful, else false
bool load(const char *dictionary)
{
    //open dictionary file.
    FILE *file = fopen(dictionary, "r");
    if (file == NULL)
    {
        return false;
    }

    char word[LENGTH + 1];
    while(fscanf(file,"%s", word) != EOF)
    {
        //creating a new node.
        node *n = malloc(sizeof(node));
        if (n == NULL)
        {
            return false;
        }
        strcpy(n->word, word);

        //obtain hash code.
        int index = hash(word);

        //insert into hash table.
        if (table[index] == NULL)
        {
            table[index] = n;
            n->next = NULL;
        }
        else
        {
            n->next = table[index];
            table[index] = n;
        }

        nodes++;
    }
    fclose(file);
    return true;
}

// Returns number of words in dictionary if loaded, else 0 if not yet loaded
unsigned int size(void)
{
    printf("%i\n",nodes);
    return nodes;
}

// Unloads dictionary from memory, returning true if successful, else false
bool unload(void)
{
    node *tmp = NULL;
    node *cursor = NULL;

    //iterating over each linked list in the hash table.
    for(int i = 0; i < N; i++)
    {
        cursor = table[i];
        //freeing all node in that linked list.
        while(cursor != NULL)
        {
           tmp = cursor;
           cursor = cursor->next;
           free (tmp);
        }
        if (table[i] != NULL)
        {
            return false;
        }

    }
    return true;
}

on running valgrind:

==259== Memcheck, a memory error detector

==259== Copyright (C) 2002-2017, and GNU GPL'd, by Julian Seward et al.

==259== Using Valgrind-3.15.0 and LibVEX; rerun with -h for copyright info

==259== Command: ./speller texts/cat.txt

==259==

MISSPELLED WORDS

A

143091

Could not unload dictionaries/large.

==259==

==259== HEAP SUMMARY:

==259== in use at exit: 8,013,040 bytes in 143,090 blocks

==259== total heap usage: 143,096 allocs, 6 frees, 8,023,256 bytes allocated

==259==

==259== 8,013,040 bytes in 143,090 blocks are still reachable in loss record 1 of 1

==259== at 0x483B7F3: malloc (in /usr/lib/x86_64-linux-gnu/valgrind/vgpreload_memcheck-amd64-linux.so)

==259== by 0x401B67: load (dictionary.c:86)

==259== by 0x4012CE: main (speller.c:40)

==259==

==259== LEAK SUMMARY:

==259== definitely lost: 0 bytes in 0 blocks

==259== indirectly lost: 0 bytes in 0 blocks

==259== possibly lost: 0 bytes in 0 blocks

==259== still reachable: 8,013,040 bytes in 143,090 blocks

==259== suppressed: 0 bytes in 0 blocks

==259==

==259== For lists of detected and suppressed errors, rerun with: -s

==259== ERROR SUMMARY: 0 errors from 0 contexts (suppressed: 0 from 0)

when I tried to debug the code using debug50, I found that the nodes in the hash table are null, hence when I try to copy the node in cursor(check function), the function returns false. I am still unsure where exactly is the error in load.

0

on observing the check 50 and debug50 results, I realized that the problem was in the unload function. solution:

   // Unloads dictionary from memory, returning true if successful, else false
   bool unload(void)
   {
      node *tmp = NULL;
      node *cursor = NULL;

      //iterating over each linked list in the hash table.
      for(int i = 0; i < N; i++)
      {
          cursor = table[i];
          //freeing all node in that linked list.
          while(cursor != NULL)
          {
             tmp = cursor;
             cursor = cursor->next;
             free (tmp);
          }
     }
     return true;
 
3
  • does this mean you've resolved your problem?
    – Cliff B
    Jul 17 at 10:00
  • only the unload function. still struggling in making the code case- insensitive. strcasecmp doesn't seem to work at all. Jul 17 at 10:50
  • thank you for your help. I've completed speller. there a few mistakes in the hash and check function but I've solved them now. Jul 17 at 12:42

You must log in to answer this question.

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