0

Trying to figure out a bug in my dictionary.c code. Please bear with me as I try to explain the bug.

I've been using the debugger, and it seems that anytime there is a collision in my hash table, check returns true. Running this through the debugger, I found that point-word will always be the word passed to the check function, so when strcasecmp is called, it will always return 0, and not iterate through the rest of the linked list.

I have added the rest of the code - I know there is still some to-do's left (like my unload function), but the check thing is confusing me.

bool check(const char *word)
{
    char *tocheck = malloc(sizeof(char[LENGTH + 1]));
    for (int i = 0; i < LENGTH + 1; i++)
    {
        tocheck[i] = tolower(word[i]);
    }


    node* bucket = hashtable[hash(tocheck)]; //find the right bucket

    //if it exists check the first node and see if it is there
    //if it is, great return true. if not, go to the next node in the list.

    for (node* point = bucket; point != NULL; point = point->next)
    {
        if (strcasecmp(point->word, word) == 0)
        {
            free(tocheck);
            return true;
        }
    }
    free(tocheck);
    return false;
}

// Loads dictionary into memory, returning true if successful else false
bool load(const char *dictionary)
{
    //open the  dictonary file and checks for an error
    FILE *inptr = fopen(dictionary, "r");
    if (inptr == NULL)
    {
        return false;
    }
    //Clears the hashtable
    for (int i = 0; i < MAX_HASH; i++)
    {
        hashtable[i] = NULL;
    }
    //go through the whole file
    char *buffer = malloc(sizeof(char) * (LENGTH + 1));
    long temphash;
    while (fscanf(inptr, "%s", buffer) != EOF)
    {
        wordcount++;
        //hash the word to find the right bucket
        temphash = hash(buffer);
        //put the word into a node
        node* nodenew = malloc(sizeof(node));
        if (nodenew == NULL)
        {
            printf("Could not malloc node.\n");
            return false;
        }
        //nodenew->word = buffer;
        strcpy(nodenew->word, buffer);
        nodenew->next = NULL;

        //check to see if there is a collision
        if (hashtable[temphash] == NULL)
        {
            hashtable[temphash] = nodenew;
        }
        else //collision, insert node at start of list
        {
            nodenew->next = hashtable[temphash];
            hashtable[temphash] = nodenew;
        }
        free(nodenew);
    }
    fclose(inptr);
    free(buffer);
    return true;
}

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

// Unloads dictionary from memory, returning true if successful else false
bool unload(void)
{
    /*for (unsigned long i = 0; i < MAX_HASH; i++)
    {
        node *pointer = hashtable[i];
        while (pointer != NULL)
        {
            node *next = pointer->next;
            free(pointer);
            pointer = next;
        }
    }*/
    return true;
}

//hash function
// djb2 hash function taken from cse.yorku.ca/~oz/hash.html and altered by me for a smaller hash table.
unsigned long hash(char *str)
{
    unsigned long hash = 0;
    int c = 0;
    while ((c = *str++) != 0)
    {
        //hash = ((hash << 5) + hash) + c; /* hash * 33 + c */
        hash = (((hash << 5) + hash) + c) % 100000;
    }
        return hash;
}
  • I didn't see any issues in the code. That usually means that there's an issue elsewhere. When check seems to be correct but still failing, it usually means that there's a problem in load, or possibly in the hash function. Without seeing them, there's no way to know what the cause of your issue might be. – Cliff B Nov 11 '18 at 3:01
  • Let me see if I can add them to the original post for you to take a look at. – stygarfield Nov 12 '18 at 4:56
1

As I thought, the problem lies in load. The last line in the while loop in load is this:

    free(nodenew);

nodenew contains the address of the node that was just created. What do you think happens to that node when this call to free is executed?

I'm going to guess that you're trying to make nodenew available for the next pass through the loop. Since nodenew is a pointer, you could just set it to null. The address of the node that was just created has now been added into the tree, so it won't be lost. If you free it though, the memory space will be released back to the operating system and the node will definitely be lost! Since you'll reset the address in nodenew when the malloc is executed on the next pass, you really don't need to even set it to null. ;-)

Nothing should be freed in load. That's the job of unload!

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

| improve this answer | |
  • Yeah! That was it it seems like, although it did take some odd turns to get there - started to look at it this evening, and it wouldn't find any words wrong - just get in some infinite loop :shrug: Thank you very much!! Now to find a 56byte memory leak! – stygarfield Nov 12 '18 at 6:57
  • 56 bytes? What file did you leave open? ;-) – Cliff B Nov 12 '18 at 7:10
  • I don't think I've left any files open (I closed the dictionary file) - it seems to have an issue with the malloc'd space for nodenew in the load function - I'll create another question so I can post the code/what valgrind says – stygarfield Nov 12 '18 at 7:14
  • Or, you could work on it for a day first. ;-) BTW, does the amount of memory change if you use a different text file as input? – Cliff B Nov 12 '18 at 7:15
  • Yeah, it does! I posted the question already - I probably should have waited to figure it out myself, but have been working on pset5 for the past week and have been pulling my hair out hah. cs50.stackexchange.com/questions/30560/… – stygarfield Nov 12 '18 at 8:01

You must log in to answer this question.

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