0

My program loads and checks correctly with small texts and the large dictionary. Although when I load large texts, for some reason calls misspelled for the letters "a" and 'I'.

I'm struggling with this pset for so many hours, I cannot figure out what is the problem:

bool check(const char* word)
{
    // TODO
    // converting the word to lower letters
    char lowerLetterWord[LENGTH + 1];
    for (int i = 0, n = strlen(word); i < n; i++)
    {
        lowerLetterWord[i] = tolower(word[i]);
    }
    lowerLetterWord[strlen(word)] = '\0';

    int ind = hashFunction(lowerLetterWord[0]);

    // checking through the hashtable
    if (hashtable[ind] == NULL)
    {
        return false;
    }
    else
    {
        node *tableindex = malloc(sizeof(node));
        tableindex = hashtable[ind];

        do 
        {

            if (strcmp(lowerLetterWord, tableindex->word) == 0)
            {
                return true;
            }
            else
            {
                tableindex = tableindex->next;
            }
        } while (tableindex->next != NULL);

        //checking the last node too
        if (strcmp(lowerLetterWord, tableindex->word) == 0)
        {
                return true;
        }

        free(tableindex);
    }

    return false;
}

/**
 * Loads dictionary into memory.  Returns true if successful else false.
 */
bool load(const char* dictionary)
{
    // TODO
    // opening the file
    FILE *fp = fopen(dictionary,"r");

    // checking if the file is valid
    if (fp == NULL)
    {
        printf("Couldn`t open the dictionary file\n");
        return false;
    }


    while (fscanf(fp, "%s", word) == 1)
    {
        node *newWordNode = malloc(sizeof(node));

        strcpy(newWordNode->word, word);
        newWordNode->next = NULL;
        int hash = hashFunction(word[0]); //finding the index of the word
        if (hashtable[hash] == 0x0)
        {
            hashtable[hash] = newWordNode;
            wordCount++;

        }
        else
        {
            newWordNode->next = hashtable[hash];
            hashtable[hash] = newWordNode;
            wordCount++;
        }
    } 
    fclose(fp);
    return true;
}
2

TL; DR:
This looks like a memory leak.

Remove:

node *tableindex = malloc(sizeof(node));   
tableindex = hashtable[ind];
...
free(tableindex);

Add:

node *tableindex = hashtable[ind];

comparison of the original and updated code (I took some guesses at your hash function etc..)

Why:

It seems the main problem is how the node pointer tableindex is declared in the check function.

node *tableindex = malloc(sizeof(node));

The value in tableindex is the address of some chunk of accessible memory big enough to put a node into. The next line, however overwrites that address with a new address, making tableindex now point to an element of hashtable, instead of that big chunk of memory it was just allocated.

 tableindex = hashtable[ind];

Now here is the part that was causing the issues. Later in the code, free is called on tableindex.

free(tableindex);

Because of your control logic and previous return statements, the code will only reach this point when the lowerLetterWord is not in the dictionary. By this point, tableindex points to the last node of your list, which is the first word that was inserted into the list. So, when free is called, the last element of the list is lost.

This was most noticeable with "a" and "i", because the hash function you implemented hashed by the first letter of the word and "a" and "i" were much more common in the texts than "baa", "ca", ... and "zaandam".

It was difficult to replicate with smaller texts, because of the inconsistent placement of free. If free had been called prior to each return statement in check, every instance of "a", "baa", "ca", .., "i", .., and "zaandam" would have been flagged as misspelled, but instead, the bug only occurred after check had been called on a misspelled word beginning with the same letter of the alphabet. A carefully crafted short text will replicate the issue:

jharvard@appliance (~/Dropbox/pset5): head text0.txt  
i a isntaword aintaword i a  
jharvard@appliance (~/Dropbox/pset5): ./speller text0.txt

MISSPELLED WORDS

isntaword    
aintaword   
i   
a 

WORDS MISSPELLED:     4   
WORDS IN DICTIONARY:  143091   
WORDS IN TEXT:        6

Anyway, to make the problem go away, simply declare and initialize tableindex like so:

    node *tableindex = hashtable[ind];

and do away with the call to free(tableindex) as it now it lives on the stack.

Here's more information in the form of a similar question on Stack Overflow.

Hope this helps.

PS- The code for load can be simplified by running the else block for all nodes, since you've initialized newWordNode->next to NULL, I don't think there's any reason the first node inserted into an element of the hashtable needs to run the if block.

| improve this answer | |
  • Whoow man, you are awesome! That was the point! I'd never make it alone. Thx!! – Manases Istvan Oct 25 '15 at 21:47

You must log in to answer this question.

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