Pset5: strcasecmp doesn't return 0 when given the same string input

Question

// Implements a dictionary's functionality

#include <stdbool.h>
#include <strings.h>
#include <string.h>
#include <stdio.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;

unsigned int word_count = 0;

// Number of buckets in hash table
const unsigned int N = 65536;

// Hash table
node *table[N];

// Returns true if word is in dictionary else false
/* 


BUG IS WITH STRCASECMP TAKING CHARACTER ARRAYS AND NOT CONST CHAR*


*/
bool check(const char *word)
{   
    int len = strlen(word);
    char *lc_word = malloc( sizeof(char) * (len + 1) );
    lc_word[len + 1] = '\0';

    // change all letters to lowercase
    for (int i = 0; i < len; i++)
    {
        lc_word[i] = tolower(word[i]);
    }
    unsigned int hash_index = hash(lc_word);
    node *trav = table[hash_index];

    while (trav != NULL)
    {
        if (strcasecmp(lc_word, trav->word) == 0) // strcasecmp does not work with character arrays
        {
            return true;
        }
        trav = trav->next;
    }
    return false;
}

// Hashes word to a number // hash function is fine
unsigned int hash(const char* word)
{
        unsigned int hash_value = 0;
        for (int i = 0, n = strlen(word); i < n; i++)
        {
             hash_value = (hash_value << 2) ^ word[i];
        }
        return hash_value % N; //N is size of hashtable
    // hash taken from https://cs50.stackexchange.com/questions/37209/pset5-speller-hash-function
}
// Loads dictionary into memory, returning true if successful else false
bool load(const char *dictionary)
{
    // initialze all values of the table to NULL
    for (int i = 0; i < N; i++)
    {
        table[i] = NULL;
    }
    // define word buffer;
    char word[LENGTH + 1];

    // Open dictionary file
    FILE *dict = fopen(dictionary, "r");
    if (dict == NULL)
    {
        printf("Could not open dictionary file\n");
        fclose(dict);
        return false;
    }

    unsigned int hash_index;

    while (fscanf(dict, "%s", word)  != EOF)
    {
        // creates a node for the word and inserts word into node
        node *n = malloc(sizeof(node));
        if (n == NULL)
        {   
            fclose(dict);
            unload();
            return false;
        }
        else
        // inserts node into linked list in that location
        strcpy(n->word, word);
        // every word in dictionary is lowercase
        hash_index = hash(n->word);
        // since table is initialized to NULL, next will point to NULL if there is nothing
        // otherwse, next will point to the old head of the linked list
        n->next = table[hash_index];
        table[hash_index] = n;
        word_count++;
    }
    fclose(dict);
    return true;
}

// 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)
{
    // instead of directly working with the table, created new pointers to the same memory to clear these stuff
    for (int i = 0; i < N; i++)
    {
        node *trav = table[i];
        while (trav != NULL)
        {
            node *tmp = trav;
            trav = trav->next;
            free(tmp);
        }
        free(trav);
    }
    return true;

}

I have tried taking the hash function to it's own file and passed in a word, but I get a different hash index when the check function converts the same word to lowercase and then hashes it. Shouldn't they give the same hash index?

strcasecmp takes two const char* as input, and check takes a const char* as its argument too, but the word property in the node struct is a char array, not a const char*. Even added a null terminating character at the end of the converted word in the check function.

I'm really confused with this, any help would be greatly appreciated.

EDIT: I changed the hash function and it's case insensitive now. strcmpcase takes char* as input, but the trav->word is a char array. Needed to convert that to a char* and spellchecking works.

bool check(const char *word)
{   
    unsigned int hash_index = hash(word);
    node *trav = table[hash_index];

    while (trav != NULL)
    {   
        int len = strlen(trav->word);
        char *dict_word = malloc(sizeof(char) * len);
        strcpy(dict_word, trav->word);
        if (strcasecmp(word, dict_word) == 0) // strcasecmp does not work with character arrays
        {   
            free(dict_word);
            return true;
        }
        free(dict_word);
        trav = trav->next;
    }
    return false;
}

// Hashes word to a number // hash function is fine
unsigned int hash(const char *word)
{
    unsigned long hash = 5381;
    int c = *word;
    c = tolower(c);

    while (*word != 0)
    {
        hash = ((hash << 5) + hash) + c;
        c = *word++;
        c = tolower(c);
    }
    return hash % N;
    // hash taken from https://www.reddit.com/r/cs50/comments/eo4zro/good_hash_function_for_speller/
}

Answer 1

Perhaps there's a slight oversight in your code. Look at the following:

   lc_word[len + 1] = '\0';

Now, say that the word is "Cat". Length is 3 so len = 3. Remember that arrays start at 0, not 1. So, "Cat" or "cat" would occupy 0, 1 and 2. The line of code above would put the end of string marker at lc_word[3+1], or lc_word[4]. So, it's actually hashing a word with 4 characters, not 3.

Easy fix.

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