cs50 pset 5 speller (updated)

dictionary.c

// Implements a dictionary's functionality

#include <ctype.h>
#include <stdbool.h>
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <strings.h>

#include "dictionary.h"

#define HASHTABLE_SIZE 10000

// Defines struct for a node
typedef struct node
{
    char word[LENGTH + 1];
    struct node *next;
}
node;

node *hashtable[HASHTABLE_SIZE];

// Hashes the word (hash function posted on reddit by delipity)
// The word you want to hash is contained within new node, arrow, word.
// Hashing that will give you the index. Then you insert word into linked list.
int hash_index(char *hash_this)
{
    unsigned int hash = 0;
    for (int i = 0, n = strlen(hash_this); i < n; i++)
    {
        hash = (hash << 2) ^ hash_this[i];
    }
    return hash % HASHTABLE_SIZE;
}

// Initializes counter for words in dictionary
int word_count = 0;

// Loads dictionary into memory, returning true if successful else false
bool load(const char *dictionary)
{
    // Opens dictionary
    FILE *file = fopen(dictionary, "r");
    if (file == NULL)
    {
        return false;
    }
    // Scans dictionary word by word (populating hash table with nodes containing words found in dictionary)
    char word[LENGTH + 1];
    while (fscanf(file, "%s", word) != EOF)
    {
        // Mallocs a node for each new word (i.e., creates node pointers)
        node *new_node = malloc(sizeof(node));
        // Checks if malloc succeeded, returns false if not
        if (new_node == NULL)
        {
            unload();
            return false;
        }
        // Copies word into node if malloc succeeds
        strcpy(new_node->word, word);

        // Initializes & calculates index of word for insertion into hashtable
        int h = hash_index(new_node->word);

        // Initializes head to point to hashtable index/bucket
        node *head = hashtable[h];

        // Inserts new nodes at beginning of lists
        if (head == NULL)
        {
            hashtable[h] = new_node;
            word_count++;
        }
        else
        {
            new_node->next = hashtable[h];
            hashtable[h] = new_node;
            word_count++;
        }
    }
    fclose(file);
    return true;
}

// Returns true if word is in dictionary else false
bool check(const char *word)
{
    // Creates copy of word on which hash function can be performed
    int n = strlen(word);
    char word_copy[LENGTH + 1];
    for (int i = 0; i < n; i++)
    {
        word_copy[i] = tolower(word[i]);
    }
    // Adds null terminator to end string
    word_copy[n] = '\0';
    // Initializes index for hashed word
    int h = hash_index(word_copy);
    // Sets cursor to point to same address as hashtable index/bucket
    node *cursor = hashtable[h];
    // Sets cursor to point to same location as head

    // If the word exists, you should be able to find in dictionary data structure.
    // Check for word by asking, which bucket would word be in? hashtable[hash(word)]
    // While cursor does not point to NULL, search dictionary for word.
    while (cursor != NULL)
    {
        // If strcasecmp returns true, then word has been found
        if (strcasecmp(cursor->word, word_copy) == 0)
        {
            return true;
        }
        // Else word has not yet been found, advance cursor
        else
        {
            cursor = cursor->next;
        }
    }
    // Cursor has reached end of list and word has not been found in dictionary so it must be misspelled
    return false;
}

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

// Unloads dictionary from memory, returning true if successful else false
bool unload(void)
{
    node *head = NULL;
    node *cursor = head;
    // freeing linked lists
    while (cursor != NULL)
    {
        node *temp = cursor;
        cursor = cursor->next;
        free(temp);
    }
    return true;
}

Unload does not work considering you forgot to malloc the node

I have the same problem as @doganguneserdemm but my error is at line 54

This code is real help full when I compare it to mine.

how to unload

This helped me immensely while troubleshooting

Doesnt the unload function 'unload' every linked list? if yes, then shouldnt there be another loop[to iterate over hash table ]?

please explain the hash function logic

I don't understand the hash function too. Thats the only thing that i have problem with. I solved this problem set with another complex hash function, But still I don't understand what it is doing.

Hi, thank you for sharing your solution. In the "check" function, why do you need tolower function if strcasecmp compares words case-insensitively?

is a memory error for dont run unload func.

can you help ?

8,013,096 bytes in 143,091 blocks are still reachable in loss record 1 of 1

8,013,096 bytes in 143,091 blocks are still reachable in loss record 1 of 1
==11929== at 0x4C31B0F: malloc (in /usr/lib/valgrind/vgpreload_memcheck-amd64-linux.so)
==11929== by 0x401127: load (dictionary.c:54)
==11929== by 0x40099E: main (speller.c:40)

The code has got valgrind error. Can you help me? please

bool unload(void)
{
for (int i = 0; i < HASHTABLE_SIZE; i++)
{
node *head = hashtable[i];
node *cursor = head;
// freeing linked lists
while (cursor != NULL)
{
node *temp = cursor;
cursor = cursor->next;
free(temp);
}
}
return true;
}

And may be you really can delete part with word_copy

Thanks this guy!
Only remains to agree with my conscience...

running valgrind --show-leak-kinds=all --xml=yes --xml-file=/tmp/tmpn51fyx2z -- ./speller substring/dict substring/text...
checking for output "MISSPELLED WORDS\n\nca\ncats\ncaterpill\ncaterpillars\n\nWORDS MISSPELLED: 4\nWORDS IN DICTIONARY: 2\nWORDS IN TEXT: 6\n"...
checking that program exited with status 0...
checking for valgrind errors...
112 bytes in 2 blocks are still reachable in loss record 1 of 1: (file: dictionary.c, line: 43)

PLEASE help me

Guys, if you have problem with memory leackage probably you forgot to fclose the file that you opened in load function, and make sure that you close it before returning true

For the valgrind error, add this line "new_node->next = NULL;" after the line "strcpy(new_node->word, word);" (line 62) in the load() function.

For valgrind error use the below code

bool unload(void)
{
    for (int i = 0; i < N ; i ++)
    {
        node *head = table[i];
        node *cursor = head;
        node *tmp = head;

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

    }
    return true;
}

Hi, thank you for sharing your solution. In the "check" function, why do you need tolower function if strcasecmp compares words case-insensitively?

strcasecmp works not for every .. machince, I guess. Returns me error when I try to call it.

I had a similar problem while writing my solution. The valgrind problems are coming from not initialising pointers during malloc() so unload() doesn't know when to stop.
Just use calloc() that auto initialises pointers to NULL and valgrind should be happy

@onyx-storm what is N in this code ? Cuz when i tried it ,it give's me an mistake.

can you elaborate? I am having some issues with using this

i just dont understand why valgrind tell me there is 1 leak of memory

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

// Represents a node in a hash table
int size_dic = 0;
typedef struct node
{
char word[LENGTH + 1];
struct node *next;
}
node;

// TODO: Choose number of buckets in hash table
const unsigned int N = LENGTH;
const unsigned int ABC = 26;

// Hash table
node *table[N][ABC];

// Returns true if word is in dictionary, else false
bool check(const char *word)
{
// TODO
int x = hash(word);
int y = hash_ABC(word);
node *curser = table[x][y];
string tmp = curser->word;
while(curser != NULL)
{
if(strcasecmp(word,tmp) == 0)
{
return true;
break;
}
else
{
curser = curser->next;
tmp = curser->word;
}
}
return false;
}

// Hashes word to a number,deapnds on the length of the word.
unsigned int hash(const char *word)
{
// TODO: Improve this hash function
return strlen(word);
}

// Hashes word to a number,depands the first char in the word.
unsigned int hash_ABC(const char *word)
{
// TODO: Improve this hash function
return toupper(word[0]) - 'A';
}

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

char word[LENGTH + 1];
while(fscanf(dic,"%s",word) != EOF)
{
    //malloc for a new memory for each node
    node *w = malloc(sizeof(node));
    //check if malloc succeeded
    if(w == NULL)
    {
        unload();
        return false;
    }
    //copy string from file to new node
    strcpy(w -> word,word);
    //creating a hash code for node *table[N][ABC];
    int n = hash(w -> word);
    int abc = hash_ABC(w -> word);

    node *header = table[n][abc];
    if(header == NULL)
    {
        table[n][abc] = w;
        size_dic++;
    }
    else
    {
        w -> next = table[n][abc];
        table[n][abc] = w;
        size_dic++;
    }
}
fclose(dic);
return true;

}

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

// Unloads dictionary from memory, returning true if successful, else false
bool unload(void)
{
for (int i = 0; i < N ; i ++)
{
for(int x = 0; x < ABC; x++)
{
node *head = table[i][x];
node *cursor = head;
node *tmp = head;
while (cursor != NULL)
{
cursor = cursor -> next;
free(tmp);
tmp = cursor;
}
}
}
return true;
}

Thank you sir [KV721], this fixed the problem !

thankyou this works

thank you so much for this! I still don't understand it completely, but it helped a lot

still dont get it no error but fails valgrind how can i free up that remaining memory

Sir, my code is a question

:( program is free of memory errors
expected "MISSPELLED WOR...", not "### unhandled ..."

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

#define N 26
#define LENGTH 45
#define TABLE_SIZE 1000

typedef struct node
{
char word[LENGTH + 1];
struct node *left;
struct node *right;
}
node;

// Hash table declaration
node *hash_table[TABLE_SIZE];

// Define a function to compute the hash index of a word
unsigned int hash_index(const char *str)
{
unsigned int hash = 0;
int c;

while ((c = *str++) != '\0')
{
    hash = hash << 1;
    hash = hash + c;
}

return hash % TABLE_SIZE;

}

// Define a function to compare two strings in a case-insensitive manner
int strcasecmp(const char *s1, const char *s2)
{
char c1, c2;

while (*s1 && *s2)
{
    c1 = toupper(*s1);
    c2 = toupper(*s2);

    if (c1 != c2)
    {
        return c1 - c2;
    }

    s1++;
    s2++;
}

return *s1 - *s2;

}

node *insert(node *root, const char *word)
{
// Base case: empty tree
if (root == NULL)
{
// Allocate memory for new node
node *new_node = malloc(sizeof(node));
if (new_node == NULL)
{
return NULL;
}
// Copy word into node
strcpy(new_node->word, word);
// Set left and right children to NULL
new_node->left = new_node->right = NULL;
// Return the new node
return new_node;
}

// Compare word with node word
int cmp = strcasecmp(word, root->word);

// Insert node in left subtree if word is smaller than node word
if (cmp < 0)
{
    root->left = insert(root->left, word);
}
// Insert node in right subtree if word is greater than node word
else if (cmp > 0)
{
    root->right = insert(root->right, word);
}
// Return the root of the tree
return root;

}

// Calculate the hash index of the word
bool check(const char *word, node *hash_table_arr[])
{
// Calculate the hash index of the word
int h = hash_index(word);

// Find the correct entry in the hash table
for (node *entry = hash_table[h]; entry != NULL; entry = entry->right)
{
    // If the word is found, return true
    if (strcasecmp(word, entry->word) == 0)
    {
        return true;
    }
}

// Return false if the word is not found
return false;

}

int main()
{
// ... (rest of the code remains the same)
}

Thank you so much! This code was very useful, but I just have one question. Why do you need to make a copy of the word in the check function? I just want to know how it works. Thank you.