0

any help would be much appreciated - I've been trawling other questions similar to this one but all the adjustments I have tried to make don't seem to fix the check50 failure.

The code seems to run fine, and when I run valgrind ./speller texts/cat.txt I get:

==2684==
==2684== HEAP SUMMARY:
==2684== in use at exit: 0 bytes in 0 blocks
==2684== total heap usage: 143,097 allocs, 143,097 frees, 8,023,472 bytes allocated
==2684==
==2684== All heap blocks were freed -- no leaks are possible
==2684==
==2684== For counts of detected and suppressed errors, rerun with: -v
==2684== ERROR SUMMARY: 0 errors from 0 contexts (suppressed: 0 from 0)

However, when I run check50 cs50/problems/2020/x/speller --log I pass all checks except:

:( program is free of memory errors
valgrind tests failed; rerun with --log for more information.
running valgrind --show-leak-kinds=all --xml=yes --xml-file=/tmp/tmprvfe6ytc -- ./speller substring/dict substring/text...
checking for output "MISSPELLED WORDS\n\nca\ncats\ncaterpill\ncaterpillars\n\nWORDS MISSPELLED: 4\nWORDS IN DICTIONARY: 2\nWORDS IN TEXT: 6\n"...
checking that program exited with status 0...
checking for valgrind errors...
56 bytes in 1 blocks are still reachable in loss record 1 of 2: (file: dictionary.c, line: 119)
112 bytes in 2 blocks are still reachable in loss record 2 of 2: (file: dictionary.c, line: 95)

Line 95 and line 119 are the two lines where memory is allocated (node *n = malloc(sizeof(node)) and node *no_words = malloc(sizeof(node))), but I checked and ((I think)) I free the same number of nodes as I create. My code is:


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

#include "dictionary.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 - start with 27 (letters of the alphabet plus apostrophe
// and space for storing word count)
const unsigned int N = 26 + 1;

// Hash table
node *table[N];

// Returns true if word is in dictionary else false
bool check(const char *word)
{
    //Create temp node
    node *current_node = table[hash(word)];

    //Systematically check through list
    while (current_node != NULL)
    {
        if (strcasecmp(current_node->word, word) == 0)
        {
            return true;
        }

        current_node = current_node->next;
    }
    //If not found, loop ends and we return false
    return false;
}

// Hashes word to a number
unsigned int hash(const char *word)
{
    //We may assume all words in dictionary are lower case or contain apostrophes
    //Sort into buckets in alphabetical order, with the last one for words beginning with '
    //i.e. words beginning with a are put in a linked list in table[0]
    if (islower(word[0]))
    {
        return (unsigned int) word[0] - 97;
    }

    //Must include this for check function
    else if (isupper(word[0]))
    {
        return (unsigned int) word[0] - 65;
    }

    //By assumption if not lower case, must be an apostrophe
    else
    {
        return N-2;
    }
    //We reserve the final bucket in the hash table for the word count
}


// Loads dictionary into a data structure in memory, returning true if successful else false
bool load(const char *dictionary)
{
    //Open dictionary as a file & check it has opened
    FILE *dict = fopen(dictionary, "r");
    if (!dict)
    {
        fclose(dict);
        return false;
    }

    //For each word found, create a node
    //Use hash function to determine the bucket, and then insert at the beginning of the linked list

    char word[LENGTH + 1];
    int word_count = 0;
    int scan_value = 0;
    //int created_nodes = 0;

    while(fscanf(dict, "%s", word) != EOF)
    {
        //Create a node for the word
        node *n = malloc(sizeof(node));
        //created_nodes += 1;
        if (n == NULL)
        {
            unload();
            fclose(dict);
            return false;
        }

        //Copy the current word into the node
        strcpy(n->word, word);

        //Determine hash number
        unsigned int hash_no = hash(word);

        //Insert the node at the beginning of the relevant linked list
        n->next = table[hash_no];
        table[hash_no] = n;

        //Update word count
        word_count++;
    }

    //Include word count in hash table
    node *no_words = malloc(sizeof(node));
    //created_nodes += 1;
    if (no_words == NULL)
    {
        unload();
        fclose(dict);
        return false;
    }

    //Use sprintf to convert word count to string and store in no_words
    char num_words[20];
    sprintf(num_words, "%i", word_count);
    strcpy(no_words->word, num_words);

    //Insert the word count at the beginning of the table[N-1] list
    no_words->next = table[N-1];
    table[N-1] = no_words;

    //printf("Created nodes: %i\n", created_nodes);

    fclose(dict);
    return true;
}


// Returns number of words in dictionary if loaded else 0 if not yet loaded
unsigned int size(void)
{
    if (table[N-1] != NULL)
    {
        //Get the string giving the word count from the end of the hash table, and convert to an int
        char *str_count = table[N-1]->word;
        int int_count = atoi(str_count);
        return int_count;
    }

    else
    {
        return 0;
    }
}


// Unloads dictionary from memory, returning true if successful else false
bool unload(void)
{
    //int nodes_freed = 0;
    //For each bucket in table, sequentially free the space
    for (int i = 0; i < N; i++)
    {
        //Check that a linked list exists in bucket
        if (table[i] == NULL)
        {
            free(table[i]);
            break;
        }

        node *current_node = table[i];
        node *tmp = current_node;
        current_node = current_node->next;

        //Loop through to end of linked list, freeing nodes pointed at by tmp
        //and using current_node to ensure we don't lose the end of the list
        while (current_node != NULL)
        {
            free(tmp);
            //nodes_freed += 1;
            tmp = current_node;
            current_node = current_node->next;
        }

        free(current_node);
        free(tmp);
        //nodes_freed += 1;
    }

    //printf("Nodes freed: %i\n", nodes_freed);
    return true;
}

I was just trying to get a basic hash table working before I tried anything more interesting - if anyone can see what I've done wrong that would be hugely helpful :)

0

Interesting. This is another example of why extensive testing with data designed to exercise all conditions, epsecially corner conditions, is necessary.

You do have memory issues. When you run the program with the full dictionary, they won't show up. But, if you run the program with valgrind and the small dictionary (which check50 uses in one memory test), the problem rears it's ugly head.

The fact that the memory leak is occurring with the small dictionary should be a big clue. I'll let you give it a shot at figuring out where it's broken before I continue digging into it. ;-D

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

| improve this answer | |
  • Thank you so much, realised I was far too concentrated on the load function and not enough on the unload function - and had forgotten the power of if / else... all fixed now! – rdauncey Jul 16 at 9:52
  • Really! All I needed to do was to remove the word break and replace it with continue. But in hindsight, I'm sure there are lots of ways to clean this up. ;-) – Cliff B Jul 16 at 15:24

You must log in to answer this question.

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