0

My code seems to pass all the Check50 tests except the one for memory as valgrind returns a "still reachable" error. Not sure what needs to be done, any help will be appreciated. Thanks!

My Code


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

#include "dictionary.h"

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

//Node count
int NC = 0;

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

// Hash table
node *table[N];

// Returns true if word is in dictionary else false
bool check(const char *word) //4
{
    char* hword = malloc(46);
    strcpy(hword, word);
    //Some definitions
    for(int i = 0; hword[i]; i++)
    {
        hword[i] = tolower(hword[i]);
    }
    int hashno = hash(hword);;
    //Actual code
    for(node *temp = table[hashno]; temp != NULL; temp = temp->next)
    {
        if(strcasecmp(hword, temp->word) == 0)
        {
            free(hword);
            return true;
        }
    }

    free(hword);
    return false;
}

// Hashes word to a number
unsigned int hash(const char *word) //2
{
    unsigned int val = 0;
    for(int i = 0; i < strlen(word); i++)
    {
        val += (int) word[i];
    }

    if(val > N)
    {
        val = val%N;
    }
    return val; //returns sum of letters in words(lowercase ASCII value)
}

// Loads dictionary into memory, returning true if successful else false
bool load(const char *dictionary) //1
{
    //Some definitions
    //File
    FILE *dictf = fopen(dictionary, "r");
    if(dictf == NULL)
    {
        return false;
    }
    //Hash no.
    int hashno;
    // String to be placed in node
    char *str = malloc(46);
    if(str == NULL)
    {
        return false;
    }
    //Temperory holder for list
    node *n = NULL;
    //Actual code
    while(fscanf(dictf, "%s", str) != EOF)
    {
            //Create node
            NC++;
            n = malloc(sizeof(node));
            if(n == NULL)
            {
                return false;
            }
            //Define vars in the node
            strcpy(n->word, str);
            printf("%s\n",str);
            n->next = NULL;
            //Find hash based on word
            hashno = hash(n->word);
            //Link node to table
            if(table[hashno] == NULL)// if no collision
            {
                table[hashno] = n;
            }
            else//if collision
            {
                n->next = table[hashno]->next;
                table[hashno]->next = n;
            }
    }
    free(str);
    // free(n);
    if(fscanf(dictf, "%s", str) == EOF)
    {
        fclose(dictf);
        return true;
    }
    fclose(dictf);
    return false;
}

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

// Unloads dictionary from memory, returning true if successful else false
bool unload(void) //5
{
    int dcount = 0;
    for(int i = 0; i<1000; i++)
    {
        while(table[i] != NULL)
        {
            node *temp = table[i]->next;
            free(table[i]);
            table[i] = temp;
        }
        dcount++;
    }
    if(dcount == 1000)
    {
        return true;
    }
    return false;
}

Valgrind output

==3116== Copyright (C) 2002-2017, and GNU GPL'd, by Julian Seward et al.
==3116== Using Valgrind-3.13.0 and LibVEX; rerun with -h for copyright info
==3116== Command: ./speller texts/lalaland.txt
==3116== 
==3116== 
==3116== HEAP SUMMARY:
==3116==     in use at exit: 3,269,616 bytes in 58,386 blocks
==3116==   total heap usage: 160,853 allocs, 102,467 frees, 8,843,310 bytes allocated
==3116== 
==3116== 3,269,616 bytes in 58,386 blocks are still reachable in loss record 1 of 1
==3116==    at 0x4C2FB0F: malloc (in /usr/lib/valgrind/vgpreload_memcheck-amd64-linux.so)
==3116==    by 0x4012AD: load (dictionary.c:96)
==3116==    by 0x4009B4: main (speller.c:40)
==3116== 
==3116== LEAK SUMMARY:
==3116==    definitely lost: 0 bytes in 0 blocks
==3116==    indirectly lost: 0 bytes in 0 blocks
==3116==      possibly lost: 0 bytes in 0 blocks
==3116==    still reachable: 3,269,616 bytes in 58,386 blocks
==3116==         suppressed: 0 bytes in 0 blocks
==3116== 
==3116== For counts of detected and suppressed errors, rerun with: -v
==3116== ERROR SUMMARY: 0 errors from 0 contexts (suppressed: 0 from 0)```

1
  • @stensal Ahh okay, I did think that it could be a problem so I include a free(n) in my code but commented it out as i was not sure if the var needed to be free'd or where in my code this freeing should be done. The way I see it the allocated memory is passed on to the linked list(the table points to it) and malloc-ing n again allocates new memory to n. I don't understand why n needs to be freed and could you give me a hint as to where in my code i should free n. Thanks!
    – atr1
    May 28 '20 at 6:29
1

The problem is because of an oversight. I'm guessing that you started with 1000 buckets, but changed N to a much larger number. Unfortunately, instead of using N throughout your program, you hardcoded 1000 in unload. That's leaving the rest of the N-1000 buckets full, assuming they had anything in them.

Try using N wherever the count of buckets needs to be used.

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

2
  • Ah dammit, got tunnel visioned by the valgrind output. You're right! Thanks for helping me out. Could you check my understanding on this bit "The way I see it the allocated memory is passed on to the linked list(the table points to it) and malloc-ing n again allocates new memory to n.", is this statement correct?
    – atr1
    May 28 '20 at 6:40
  • That is exactly correct.
    – Cliff B
    May 28 '20 at 6:42
0

n = malloc(sizeof(node)); the memory allocated by this line is not freed. The error message. The line is off as I need to fix the build with an extra declaration.

 Memory access warning: memory spaces are not freed; continue execution.
  # 1 memory space is allocated at
  #    file:/dictionary.c::95, 17
  # total 52 bytes
  #

The link to reproduce this error.

2
  • This is not the problem. Valgrind is only showing this line as the place where the memory was allocated so that you know what memory is not being freed.
    – Cliff B
    May 28 '20 at 6:33
  • Thanks for pointing this out. The warning message is not precise. It should be some memory spaces allocated at that location are not freed. I have fixed it.
    – stensal
    May 28 '20 at 7:23

You must log in to answer this question.

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