0

After many trials, I am currently stuck in this Pset. The full code that I have is as follows:

// Implements a dictionary's functionality

#include <ctype.h>
#include <stdbool.h>
#include <stdlib.h>
#include <stdio.h>
#include <string.h>
#include <strings.h>
#include "dictionary.h"

int count = 0;
// Represents a node in a hash table
typedef struct node
{
    char word[LENGTH + 1];
    struct node *next;
}
node;

// TODO: Choose number of buckets in hash table
const unsigned int N = 26;

// Hash table
node *table[N];

// Returns true if word is in dictionary, else false
bool check(const char *word)
{
    // TODO
    int index = hash(word);
    node *cursor = NULL;
    cursor = table[index];
    if (cursor == NULL){
        return false;
    }
    while(cursor != NULL){
        //printf("%s\n", cursor->word);
        //printf("%s\n", word);
        if (strcasecmp(cursor->word, word) == 0){
            return true;
        }
        table[index] = table[index]->next;
        cursor = table[index];
    }
    return false;
}

// Hashes word to a number
unsigned int hash(const char *word)
{
    char word_check[LENGTH + 1]; 
    int len = strlen(word);
    for (int i = 0; i < len; i++){
        word_check[i] = tolower(word[i]);
    }
    if (word_check[0] == 39){ 
        int index = 26; 
        return index;
    }
    int index = (word_check[0] - 97) % 26; 
    return index;

}

// Loads dictionary into memory, returning true if successful, else false
bool load(const char *dictionary)
{
    // TODO
    for (int i = 0; i < N; i++){
        table[i] = NULL;
    }
    FILE *file = fopen(dictionary, "r");
    if (file == NULL){
        return false;
    }
    char buffer[LENGTH + 1]; 
    while (fscanf(file, "%s", buffer) != EOF){ 
        node *n = malloc(sizeof(node));

        if (n == NULL){ 
            fclose(file);
            return false; 
        }
        strcpy(n->word, buffer); 
        n->next = NULL;
        int index = hash(n->word); 
        if (table[index] == NULL){
            table[index] = n;
            table[index]->next = NULL;
        }
        else{
            n->next = table[index];
            //table[index]->next = n; 
            table[index] = n;
        }
        count++;
    }
    fclose(file);
    size();
    return true;
}

// Returns number of words in dictionary if loaded, else 0 if not yet loaded
unsigned int size(void)
{
    printf("%i", count);
    return 0;
}

// Unloads dictionary from memory, returning true if successful, else false
bool unload(void)
{
    // TODO
    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;
}

After running check50 with valgrind, this is what I get:

> ==13853== LEAK SUMMARY:
> ==13853==    definitely lost: 224 bytes in 4 blocks
> ==13853==    indirectly lost: 1,294,384 bytes in 23,114 blocks
> ==13853==      possibly lost: 0 bytes in 0 blocks
> ==13853==    still reachable: 0 bytes in 0 blocks
> ==13853==         suppressed: 0 bytes in 0 blocks
> ==13853== 
> ==13853== For lists of detected and suppressed errors, rerun with: -s
> ==13853== ERROR SUMMARY: 1 errors from 1 contexts (suppressed: 0 from 0)
> 
> Asking for help...
> 
> ==13853== 1,294,608 (224 direct, 1,294,384 indirect) bytes in 4 blocks are definitely lost in loss record 2 of 2
> ==13853==    at 0x4848899: malloc (in /usr/libexec/valgrind/vgpreload_memcheck-amd64-linux.so)
> ==13853==    by 0x109B63: load (dictionary.c:91)
> ==13853==    by 0x1092DB: main (speller.c:40)
> 
> Looks like your program leaked 1,294,608 bytes of memory. Did you
> forget to free memory that you allocated via malloc? Take a closer
> look at line 91 of dictionary.c.

Apparently, my unload function did not unload all the nodes that I malloc'd in the load function, since I shouldn't free anything that is not inside the unload function.

Additionally, my check function doesn't seem to be able to return the right output from strcasecmp, which I was able to see printing words inside the loop. Is the logic in my check function right? Or I am doing something wrong?

1 Answer 1

1

Your assessment is on target. You just needed to go further. Look at the while loop in the check function:

while(cursor != NULL){
        //printf("%s\n", cursor->word);
        //printf("%s\n", word);
        if (strcasecmp(cursor->word, word) == 0){
            return true;
        }
        table[index] = table[index]->next;    //  line 42
        cursor = table[index];                // line 43
    }

What happens at the end of the loop at line 42 (see added comment) where the code needs to move to the next node in the linked list? The code updates table[index]. This changes the starting point of the linked list to the node that was just checked, cutting every previous node out of the linked list!!!! All those nodes become lost memory and it breaks the dictionary!

Once the dictionary has been built in load, the table[] array should absolutely never be changed, reassigned, updated, or altered in any way!!!

Instead, just set the cursor to the next node: cursor = cursor->next;

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

3
  • Thanks for the support, Cliff! I ended up doing exactly what I was trying not to do (whoops!). I just followed the same logic that I used in other functions and valgrind returns 0 errors now! However, I just used something = something->next. Should I use a tmp variable for this, as a good practice? Commented Nov 24, 2022 at 11:29
  • It all depends on the circumstances. In the check function the temp var isn't needed because the code isn't freeing anything. In unload, it definitely is needed. I'll edit my answer accordingly.
    – Cliff B
    Commented Nov 24, 2022 at 22:05
  • I see! Thankfully I was able to finally finish this Pset. Thanks a lot for the answers! Commented Nov 24, 2022 at 22:41

You must log in to answer this question.

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