0

My code is functional according to check50 but I'm still leaking bad memory. Based on amount of memory lost, I'm guessing something to close up in LOAD, but could be UNLOAD as well. First thoughts are adding a recursive freeing loop within the LOAD function. Reactions? Valgrind beneath code

// 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"

// 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;

//declare variables
unsigned int word_count;
unsigned int hash_value;
// Hash table
node *table[N];

// Returns true if word is in dictionary, else false
bool check(const char *word)
{
    // TODO
    hash_value = hash(word); //obtain the deterministic hash value of word
    node *cursor = table[hash_value]; //create a cursor and point it at table[hash_value]
    while (cursor !=  0) //iterate as long as the cursor has not landed on a null value
    {
        if (strcasecmp(word, cursor->word) == 0) //if string word is the same as the string pointed to by cursor at word
        {
            return true; //return boolean expected value
        }
        cursor = cursor->next; //cursor becomes what next node pointed to (remember next is defined as a node in our typedef)
    } //if this loop has iterated through the entire linked list without returning true...
    return false;
}

// Hashes word to a number
unsigned int hash(const char *word) //thanks to youtube cs50 guide by anvea for looping framework, internal total count my own
{
    unsigned long total = 0;
    for(int i = 0; i < strlen(word); i++)
    {
        total += (strlen(word) ^ i);
    }
    return total % N;
}

// Loads dictionary into memory, returning true if successful, else false
bool load(const char *dictionary)
{
    // TODO:
    //open dictionary file: use fopen, remember to check for null, return false if so
    FILE *file = fopen(dictionary, "r"); //calls a file and sets its pointer to the result of the fopen-read function
    if (file == NULL) //if the file opens is null
    {
        printf("Cannot open %s\n", dictionary); //print error message
        return false; //returns expected boolean output
    }
    //read strings from the file one at a time, fscanf(file, "%s%", word) returns EOF at end of file, loop word by word until EOF
    char word[LENGTH + 1]; //create a variable called word for program to examine
    while (fscanf(file, "%s", word) != EOF) //iterates through each word in file until EOF
    //create new node values for each word: use malloc, check for null, copy word into node with strcopy
    {
        node *n = malloc(sizeof(node)); //mallocs memory for the word being scanned
        if (n == NULL) //verify malloc did not return null
        {
            printf("Could not scan %s\n", dictionary);
            return false; //no need to actively free because malloc allocated no memory to start (NULL)
        }
        strcpy(n->word, word); //copies string word into location described by pointer n->word
        //hash word: hash tables are arrays of linked lists, use hash function, function takes a string and returns an index
        hash_value = hash(word); //creates hash value of word according to hash function
        //insert node into has table: set pointers in correct order
        n->next = table[hash_value]; //sets the pointer of next node to location[has_value] within table
        table[hash_value] = n; //resets table[hash_value] to n to prime next loop iteration
        word_count++; //increases the word count of the total array(?)
    }
    fclose(file); //close the opened file which pointed to the dictionary
    return true; //produce expected boolean output indicicated function has closed successfully
}

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

// Unloads dictionary from memory, returning true if successful, else false
bool unload(void)
{
    for (int i = 0; i < N; i++) //iterate once through each bucket
    {
        node *cursor = table[i]; //set cursor to the ith location on the linked list
        while (cursor != NULL) //continue to iterate as long as the cursor exists
        {
            node *tmp = cursor; //created a temporary cursor pointing to cursor's location
            cursor = cursor->next; //frees memory associated with cursor
            free(tmp); //sets cursor to temp
        } //reiterate
        if (cursor == NULL) //once the cursor finishes above iteration and has nothing left to point at
        {
            free(cursor);
            return true;
        }
    }
    return false;
}


==32437== Memcheck, a memory error detector
==32437== Copyright (C) 2002-2017, and GNU GPL'd, by Julian Seward et al.
==32437== Using Valgrind-3.18.1 and LibVEX; rerun with -h for copyright info
==32437== Command: ./speller texts/cat.txt
==32437== 

MISSPELLED WORDS


WORDS MISSPELLED:     0
WORDS IN DICTIONARY:  143091
WORDS IN TEXT:        6
TIME IN load:         2.11
TIME IN check:        0.05
TIME IN size:         0.00
TIME IN unload:       0.00
TIME IN TOTAL:        2.16

==32437== 
==32437== HEAP SUMMARY:
==32437==     in use at exit: 8,013,096 bytes in 143,091 blocks
==32437==   total heap usage: 143,096 allocs, 5 frees, 8,023,256 bytes allocated
==32437== 
==32437== 8,013,096 bytes in 143,091 blocks are still reachable in loss record 1 of 1
==32437==    at 0x4848899: malloc (in /usr/libexec/valgrind/vgpreload_memcheck-amd64-linux.so)
==32437==    by 0x109A73: load (dictionary.c:72)
==32437==    by 0x1092CB: main (speller.c:40)
==32437== 
==32437== LEAK SUMMARY:
==32437==    definitely lost: 0 bytes in 0 blocks
==32437==    indirectly lost: 0 bytes in 0 blocks
==32437==      possibly lost: 0 bytes in 0 blocks
==32437==    still reachable: 8,013,096 bytes in 143,091 blocks
==32437==         suppressed: 0 bytes in 0 blocks
==32437== 
==32437== For lists of detected and suppressed errors, rerun with: -s
==32437== ERROR SUMMARY: 0 errors from 0 contexts (suppressed: 0 from 0)

1 Answer 1

1

There is a problem in unload. It will only free one index, then it returns to speller. Do not return until it has processed all the buckets. There is not a condition I have ever encountered where unload should ever return false.

This may not be the only problem in the program but fixing it should help move things along.

2
  • Thank you! i'll adjust the program returns to unload is ACTUALLY unloading.
    – mcweebus
    Commented Dec 2, 2022 at 7:36
  • 1
    update: success! replaced the "false" with true in the final return statement. also removed nested return true within iteration loop. thanks again, DinoCoderSaurus!
    – mcweebus
    Commented Dec 2, 2022 at 21:23

You must log in to answer this question.

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