1

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;
}
0
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!

| improve this answer | |
  • Thank you for taking the time. I do believe using 0 is the same as saying true, nonetheless I changed it to 0 just in case. Regarding the case lowering, you are right, strcasecmp doesn't need me to lowercase the word, and that's why I dont insert lower. I lower it just because of how the hash function is defined to make sure the resulting index is consistent with the time I use it in load(). – Matías Gómez Seeber Jul 30 at 15:58
  • 0 is used to represent false, and any other integer would be considered true! If you want to use an integer to represent true, I believe the standard is to use 1 instead. I hope the rest is fixed soon! – Hana Ali Jul 30 at 16:02
  • 1
    Oh, you are right, I got that the other way around, thank you! – Matías Gómez Seeber Jul 30 at 16:06
0

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

| improve this answer | |

You must log in to answer this question.

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