Pset5: check unable to find words

Question

Thankfully, I don't get any seg faults so I'm guessing unload() is working properly. Also, load() seems to run correctly when debugging, so I'm guessing the problem isn't on loading either. I don't see how I could have made a mistake in size(). Therefore, I'm guessing I'm making an error either on check() or hash(). When debugging, I'm seeing check go through the tree properly but not finding the words, even though it is correctly being lowercased earlier. If anyone is willing to help me find the mistake, I'd highly appreciate it.

// Implements a dictionary's functionality

#include <stdbool.h>

#include "dictionary.h"

#include <stdio.h>

#include <string.h>

#include <stdlib.h>

#include <ctype.h>

#include <strings.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
const unsigned int N = 500000;

// Hash table
node *table[N];

// Returns true if word is in dictionary else false
bool check(const char *word)
{
    int len = strlen(word);
    char lower[LENGTH + 1];
    
    for (int i = 0; i < len; i++)
    {
            lower[i] = tolower(word[i]);
    }
    
    int n = hash(lower);
    
    for(node *tmp = table[n] ; tmp != NULL; tmp = tmp -> next)
    {
        if (strcasecmp(tmp -> word, word) == true)
        {
            return true;
        }
    }
    
    return false;
}

// Hashes word to a number
// Using djb2 by Dan Berstein as specified in http://www.cse.yorku.ca/~oz/hash.html
unsigned int hash(const char *word)
{
    unsigned int h = 5381;
    int c;

    while ((c = *word++))
    {
        h = ((h << 5) + h) + c; /* h * 33 + c */
    }
    return h % N;
}

int *dict_size;

// Loads dictionary into memory, returning true if successful else false
bool load(const char *dictionary)
{
    // Open dictionary
    FILE *file = fopen(dictionary, "r");
    
    // check if readable
    if (file == NULL)
    {
        return false;
    }
    
    // Create counter variable for function size
    dict_size = malloc(sizeof(int));
    *dict_size = 0;
    
    // Check if correctly allocated
    if (dict_size == NULL)
    {
        return false;
    }
    
    // create variable to store words in
    char words[LENGTH + 1];
    
    // read strings from file
    while (fscanf(file, "%s", words) != EOF)
    {
        // allocate memory for new node
        node *n = malloc(sizeof(node));
        
        // check that it was correctly allocated
        if (n == NULL)
        {
            return false;
        }
        
        // setting n's word to the word read from file
        strcpy(n -> word, words);
        
        // getting the index for words
        int index = hash(words);
        
        // inserting words into table
        n -> next = table[index];
        table[index] = n;
        
        // adding to the size of the dictionary for size()
        *dict_size += 1;
    }
    
    // open dictionary file 
    // read strings from file one at a time
    // create a new node for each word
    // hash word to obtain a hash value
    // insert node into hash table at that location
    return true;
}

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

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

Answer 1

if (strcasecmp(tmp -> word, word) == true)

strcasecmp returns an integer I believe, not a boolean, so that if they're the same string you get a 0. I changed that line and got significantly less misspellings when I compiled your code (from 17682 to 5440), but that's still greater than what it should be. I'm not sure where the exact error is, but I do want to note that you dont need the tolower() loop as strcasecmp is case-insensitive. I hope someone with a clearer view answers this soon!

Answer 2

Okay, so I ran a test with dictionaries/small with debug50 and noticed one "small" issue with my code: I wasn't reseting the string lower inside check(). This lead to carrying the last word checked *(I give an example at the end of this answer if you don't quite understand), therefore creating different hash values and the program not finding any words except for the first one (unless the next one was larger). To make it right, I changed

char lower[LENGTH + 1];

to

char lower[LENGTH + 1] = "";

That solved the checking issue. I had another small mistake: I never closed file in load(). I simply closed it at the end the the function and now it all works just fine.

• I used dictionaries/small, which has "cat" and "caterpillar" in it. I created a text file which had "Cat", "caterpiLlar" and "hello". I debugged the check function and noticed that after it checked for "cat" and check() was called again, even before the for-loop to lowercase "caterpiLlar" was run, lower was still set to "cat". It was then turned into caterpillar, which didn't yield an error because it was a longer word. When check() was called for a last time to check hello, after the loop, lower was set to "hellopillar". This is what I meant by:

carrying the last word checked