0

So valgrind has identified line 102 as the potential source of memory leak which is the following within the load function:

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

Have I missed freeing up this memory later on? I assumed that my unload function does this.

Check50 reports the following also that shows errors comparing basic words and case sensitivity. Does strcasecmp not do this?

:) dictionary.c, dictionary.h, and Makefile exist
:) speller compiles
:( handles most basic words properly
    expected "MISSPELLED WOR...", not "MISSPELLED WOR..."
:) handles min length (1-char) words
:) handles max length (45-char) words
:) handles words with apostrophes properly
:( spell-checking is case-insensitive
    expected "MISSPELLED WOR...", not "MISSPELLED WOR..."
:) handles substrings properly
:( program is free of memory errors
    valgrind tests failed; rerun with --log for more information.

My code is as follows

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

//set a word counter to keep track
int wordcount = 0;
bool loaded;

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

// Number of buckets in hash table
const unsigned int N = 10000;

// Hash table
node *table[N];

// Returns true if word is in dictionary else false
bool check(const char *word)
{
    //hash the input word
    int index = hash(word);

    // go to index location of word
    node *cursor = NULL;
    cursor = table[index];

    //set cursor to first word and check
    while (cursor != NULL)
    {
        //compare word with node word and if equal return true
        if (strcasecmp (cursor -> word, word) == 0)
        {
            return true;
        }

        //if not word, set cursor = cursor->next and check again
        else
        {
            return false;
            cursor = cursor -> next;
        }
    }
    return false;
}

// Hashes word to a number - shows which index to put your word into
// taken from Deliberate Think youtube
unsigned int hash(const char *word)
{
    int hash = 0;
    int n;
    // run through words so long as no null character
    for (int i = 0; word[i] != '\0'; i++)
    {
       // read input words if alphabetical chars inclusive of apostrophes where req'd
        if (isalpha(word[i]))
        {
            n = word[i] - 'a' + 1;
        }
        else
        {
            n = 27;
        }
        hash = ((hash << 3) + n) % N;
    }
    return hash;
}

// Loads dictionary into memory, returning true if successful else false
bool load(const char *dictionary)
{
    // open dictionary and read it
    FILE *dict = fopen(dictionary, "r");
    if (dict == NULL)
    {
        return false;
    }
    //set hash table values to NULL
    for(int i = 0; i < N; i++)
    {
        table[i] = NULL;
    }
    //array for word
    char word[LENGTH];
    //read strings from dictionary ***DOES THIS READ 1 WORD AT A TIME OR IS LOOP REQD?***
    while (fscanf(dict, "%s", word) != EOF)
    {
        //increase words found
        wordcount++;
        //allocate memory for node to store words into hash table
        node *n = malloc(sizeof(node));
        if (n == NULL)
        {
            return false;
        }
        //copy string into the word part of node the input word
        strcpy(n->word, word);
        //next pointer starts as null
        n->next = NULL;
        //use the hash function taking a string and returning index (address)
        unsigned int index = hash(n->word);
        //point to the node if the table is empty (index becomes the first node address)
        if (table[index]==NULL)
        {
            table[index]=n;
        }
        //if not empty, make new temp node to connect
        else if (table[index] != NULL)
        {
           //pointer back to the address
           n->next = table[index];
           //address becomes the index
           table[index] = n;
        }

    }
        fclose(dict);
        loaded = true;
        return true;
}


// Returns number of words in dictionary if loaded else 0 if not yet loaded
unsigned int size(void)
{
    // as the dictionary is loaded, count
    if(loaded != true)
    {
        return 0;
    }
    return wordcount;
}

// Unloads dictionary from memory, returning true if successful else false
bool unload(void)
{
    // free up any memory used temporarily
    // hash table is just an array of linked lists. Run through each linked list and free

    for (int i = 0; i < N; i++)
    {
         // place cursor on first in table
         node *cursor = table[i];
         while (cursor != NULL)
         {
             // create tmp cursor to point at first item of linked list (same as cursor)
             node *tmp = cursor;
             //move cursor to next location
             cursor = cursor -> next;
             //free up location of tmp pointer
             free(tmp);
             return true;
         }
     }
    return false;
}
0

The return true; is misplaced in the unload function. It executes after the first node is freed.

strcasecmp is case-insensitive. Alas, the hash function is not, so hashing the word in check will give a different index than load did if the word is not all lower case.

| improve this answer | |
  • Thanks! That sorted the valgrind out and I now understand the need to convert to lower case before hashing the word. It's still reporting a large number of upper and lowercase words that are spelled correctly as being incorrectly spelled so I will continue reviewing and tweaking my check function until I'm there. – pizzastory Jul 2 at 7:39
  • I realised the first return false function within check meant that my program was looking at only the first item of the linked list. It therefore didn't look through the rest of the linked list and instead stated it was misspelled. Thanks @DinoCoderSaurus for your help on this! – pizzastory Jul 3 at 7:20

You must log in to answer this question.

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