1

sorry that this is a repost of a deleted question. I made a mistake in reading the specifications and didn't realise I wasn't able to alter the function declarations in dictionary.c & .h. The response I got in the initial question was a bit disheartening for a beginner, but I made the fixes and am posting the adjusted code. The issue I am having is related to my memory management. I have passed all other criteria on check50, but I can't seem to fix my memory leaks. There is one change I am aware I need, which is to use fclose on the dictionary file. When I do however, it actually causes further issues on check50. I'm having trouble acting on the information Valgrind offers, though I will paste it below.

I'm really not claiming to be incredible at this, so please forgive any mistakes. I had to adjust the code a little after the mistake with the declarations, so apologies if anything of that is left over.

EDIT: I've also just pasted my valgrind report after including fclose(dict); at the very end of the load function (right before return true;).

// Implements a dictionary's functionality

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


#include "dictionary.h"

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

// Number of buckets in hash table
const unsigned int N = 20000;
int dictsize;
node *memory;
unsigned int code;

// Hash table
node *table[N];

// Returns true if word is in dictionary else false
bool check(const char *word)
{

    //obtains hash
    code = hash(word);

    if (table[code] == NULL)
    {
        return false;
    }

    // goes to requested address in hash table
    node *tmp = table[code];
    
    // checks for null and iterates along linked list for match
    while (tmp != NULL)
    {
        if (strcasecmp(tmp->input, word) == 0)
        {
            return true;
        }

        tmp = tmp->next;

    }
    return false;
}

// Hashes word to a number
unsigned int hash(const char *word)
{

    unsigned int h = 0;
    unsigned int high = 0;
    
    // copying const char in order to edit local variable only. *temp is delcared to allow program to free memory at end of function, wasn't running without it.
    char *hword = malloc(LENGTH + 1);
    char *temp = hword;
    strcpy(hword, word);

    while ( *hword )
    {
        if(isupper(hword[0]) != 0)
        {
            hword[0] = tolower(hword[0]);
        }

    h = ( h << 4 ) + *hword++;
    if ( high == (h & 0xF0000000) )
    h ^= high >> 24;
    h &= ~high;
    }

    while ( h > 19999 )
    {
        h = h % 20000;
    }
    free(temp);
    return h;

}

// loads dictionary into memory, returning true if successful else false
bool load(const char *dictionary)
{

    // open dictionary
    FILE *dict = fopen(dictionary, "r");
    if (dictionary == NULL)
    {
        return false;
    }

    // allocates all needed memory in one go so I can unload quickly
    memory = malloc(sizeof(node) * 143093);

    // using node n to copy dictionary contents and keeping malloc address to free memory in unload
    node *n = memory; 

    char *word = malloc(sizeof(LENGTH + 1));
    
    // scans dictionary for string
    for (int a = 1; fscanf(dict, "%s", word) != EOF; a++)
    {

        // function to hash and load
        if (word != NULL)
        {
            ++n;
            code = hash(word);

            if (n != NULL)
            {
                strcpy(n->input, word);

                n->next = table[code];
                table[code] = n;
                dictsize = a;
            }
        }

    }
    free(word);
    return true;
}

// returns number of words in dictionary if loaded else 0 if not yet loaded
unsigned int size(void)
{
    // returns counter value in load
    return dictsize;
}

// unloads dictionary from memory, returning true if successful else false
bool unload(void)
{
    free(memory); // free all memory used for nodes at once
    return true;
}

Valgrind

==22217== Memcheck, a memory error detector
==22217== Copyright (C) 2002-2017, and GNU GPL'd, by Julian Seward et al.
==22217== Using Valgrind-3.13.0 and LibVEX; rerun with -h for copyright info
==22217== Command: ./speller dictionaries/large texts/austen.txt
==22217== 
==22217== Invalid write of size 1
==22217==    at 0x5248942: _IO_vfscanf (vfscanf.c:1188)
==22217==    by 0x52562E5: __isoc99_fscanf (isoc99_fscanf.c:34)
==22217==    by 0x4012D2: load (dictionary.c:115)
==22217==    by 0x400964: main (speller.c:40)
==22217==  Address 0x55cb2b4 is 0 bytes after a block of size 4 alloc'd
==22217==    at 0x4C2FB0F: malloc (in /usr/lib/valgrind/vgpreload_memcheck-amd64-linux.so)
==22217==    by 0x4012AE: load (dictionary.c:112)
==22217==    by 0x400964: main (speller.c:40)
==22217== 
==22217== Invalid read of size 1
==22217==    at 0x4C32E03: strcpy (in /usr/lib/valgrind/vgpreload_memcheck-amd64-linux.so)
==22217==    by 0x40113C: hash (dictionary.c:69)
==22217==    by 0x4012FB: load (dictionary.c:122)
==22217==    by 0x400964: main (speller.c:40)
==22217==  Address 0x55cb2b4 is 0 bytes after a block of size 4 alloc'd
==22217==    at 0x4C2FB0F: malloc (in /usr/lib/valgrind/vgpreload_memcheck-amd64-linux.so)
==22217==    by 0x4012AE: load (dictionary.c:112)
==22217==    by 0x400964: main (speller.c:40)
==22217== 
==22217== Invalid read of size 1
==22217==    at 0x4C32E03: strcpy (in /usr/lib/valgrind/vgpreload_memcheck-amd64-linux.so)
==22217==    by 0x40131F: load (dictionary.c:126)
==22217==    by 0x400964: main (speller.c:40)
==22217==  Address 0x55cb2b4 is 0 bytes after a block of size 4 alloc'd
==22217==    at 0x4C2FB0F: malloc (in /usr/lib/valgrind/vgpreload_memcheck-amd64-linux.so)
==22217==    by 0x4012AE: load (dictionary.c:112)
==22217==    by 0x400964: main (speller.c:40)
==22217== 
==22217== Invalid write of size 1
==22217==    at 0x5246FDD: _IO_vfscanf (vfscanf.c:1103)
==22217==    by 0x52562E5: __isoc99_fscanf (isoc99_fscanf.c:34)
==22217==    by 0x4012D2: load (dictionary.c:115)
==22217==    by 0x400964: main (speller.c:40)
==22217==  Address 0x55cb2b4 is 0 bytes after a block of size 4 alloc'd
==22217==    at 0x4C2FB0F: malloc (in /usr/lib/valgrind/vgpreload_memcheck-amd64-linux.so)
==22217==    by 0x4012AE: load (dictionary.c:112)
==22217==    by 0x400964: main (speller.c:40)
==22217== 
==21347== 

==21347== HEAP SUMMARY:
==21347==   in use at exit: 552 bytes in 1 blocks
==21347==   total heap usage: 268,301 allocs, 268,300 frees, 20,365,056 bytes allocated
==21347== 
==21347== 552 bytes in 1 blocks are still reachable in loss record 1 of 1
==21347==    at 0x4C2FB0F: malloc (in /usr/lib/valgrind/vgpreload_memcheck-amd64-linux.so)
==21347==    by 0x5258E49: __fopen_internal (iofopen.c:65)
==21347==    by 0x5258E49: fopen@@GLIBC_2.2.5 (iofopen.c:89)
==21347==    by 0x40126E: load (dictionary.c:100)
==21347==    by 0x400964: main (speller.c:40)
==21347== 
==21347== LEAK SUMMARY:
==21347==    definitely lost: 0 bytes in 0 blocks
==21347==    indirectly lost: 0 bytes in 0 blocks
==21347==      possibly lost: 0 bytes in 0 blocks
==21347==    still reachable: 552 bytes in 1 blocks
==21347==         suppressed: 0 bytes in 0 blocks
==21347== 
==21347== For counts of detected and suppressed errors, rerun with: -v
==21347== ERROR SUMMARY: 2601087 errors from 4 contexts (suppressed: 0 from 0)

Valgrind with fclose(dict);

==22217== Memcheck, a memory error detector
==22217== Copyright (C) 2002-2017, and GNU GPL'd, by Julian Seward et al.
==22217== Using Valgrind-3.13.0 and LibVEX; rerun with -h for copyright info
==22217== Command: ./speller dictionaries/large texts/austen.txt
==22217== Invalid write of size 1
==21960==    at 0x5248942: _IO_vfscanf (vfscanf.c:1188)
==21960==    by 0x52562E5: __isoc99_fscanf (isoc99_fscanf.c:34)
==21960==    by 0x4012D2: load (dictionary.c:115)
==21960==    by 0x400964: main (speller.c:40)
==21960==  Address 0x55cb2b4 is 0 bytes after a block of size 4 alloc'd
==21960==    at 0x4C2FB0F: malloc (in /usr/lib/valgrind/vgpreload_memcheck-amd64-linux.so)
==21960==    by 0x4012AE: load (dictionary.c:112)
==21960==    by 0x400964: main (speller.c:40)
==21960== 
==21960== Invalid read of size 1
==21960==    at 0x4C32E03: strcpy (in /usr/lib/valgrind/vgpreload_memcheck-amd64-linux.so)
==21960==    by 0x40113C: hash (dictionary.c:69)
==21960==    by 0x4012FB: load (dictionary.c:122)
==21960==    by 0x400964: main (speller.c:40)
==21960==  Address 0x55cb2b4 is 0 bytes after a block of size 4 alloc'd
==21960==    at 0x4C2FB0F: malloc (in /usr/lib/valgrind/vgpreload_memcheck-amd64-linux.so)
==21960==    by 0x4012AE: load (dictionary.c:112)
==21960==    by 0x400964: main (speller.c:40)
==21960== 
==21960== Invalid read of size 1
==21960==    at 0x4C32E03: strcpy (in /usr/lib/valgrind/vgpreload_memcheck-amd64-linux.so)
==21960==    by 0x40131F: load (dictionary.c:126)
==21960==    by 0x400964: main (speller.c:40)
==21960==  Address 0x55cb2b4 is 0 bytes after a block of size 4 alloc'd
==21960==    at 0x4C2FB0F: malloc (in /usr/lib/valgrind/vgpreload_memcheck-amd64-linux.so)
==21960==    by 0x4012AE: load (dictionary.c:112)
==21960==    by 0x400964: main (speller.c:40)
==21960== 
==21960== Invalid write of size 1
==21960==    at 0x5246FDD: _IO_vfscanf (vfscanf.c:1103)
==21960==    by 0x52562E5: __isoc99_fscanf (isoc99_fscanf.c:34)
==21960==    by 0x4012D2: load (dictionary.c:115)
==21960==    by 0x400964: main (speller.c:40)
==21960==  Address 0x55cb2b4 is 0 bytes after a block of size 4 alloc'd
==21960==    at 0x4C2FB0F: malloc (in /usr/lib/valgrind/vgpreload_memcheck-amd64-linux.so)
==21960==    by 0x4012AE: load (dictionary.c:112)
==21960==    by 0x400964: main (speller.c:40)
==21960== 

==21884== HEAP SUMMARY:
==21884==     in use at exit: 0 bytes in 0 blocks
==21884==   total heap usage: 268,301 allocs, 268,301 frees, 20,365,056 bytes allocated
==21884== 
==21884== All heap blocks were freed -- no leaks are possible
==21884== 
==21884== For counts of detected and suppressed errors, rerun with: -v
==21884== ERROR SUMMARY: 2601087 errors from 4 contexts (suppressed: 0 from 0)
Improve this question

2 Answers 2

Reset to default
1

Couple of bugs I noted in your code (ignore if this works)

You need to fclose the dictionary before you return true because it results in memory leakage

Also you are not returning false if no space left to allocate enough memory for both node and word

You don't need to indirectly assign memory allocation to memory and then pass it to node *n

Simply you can do this like

node *n = malloc(size of(node);

Also you are allocating memory to read and store strings from the dictionary and again not returning false

Instead to simplify your code you can say something like

char buffer[LENGTH + 1];

You can use it to store strings and strcpy it

If I helped you be sure to tick the answer to keep other smiling too 😃

Improve this answer
7
  • Hi there, thanks for your reply. I noted the issue with fclose in my post. While generally my code runs, closing the file causes issues with smaller dictionaries (you'll see the valgrind report for that at the bottom of my post). Regarding the error check for malloc on node and word, thanks for the heads up, didn't notice it!
    – Disierd
    Jul 19, 2020 at 17:03
  • With regard to using node *n and memory, the idea was that I would allocate all memory needed (since I know the large dictionary size), cycle through it using node *n to assign memory to new hash table entries, and then keep the pointer at memory so I could free all memory used for nodes in one go in the unload function. Is that not possible?
    – Disierd
    Jul 19, 2020 at 17:06
  • You can't free the pointer but you can free the malloc
    – Shehroz Ali
    Jul 19, 2020 at 17:39
  • Pointer itself isn't a malloc unless you used to malloc it node *n = malloc() here *n is a pointer which is used to point to malloc in the memory
    – Shehroz Ali
    Jul 19, 2020 at 17:43
  • Okay, I just turned word into an array that takes from the stack rather than the heap, and now everything is just working perfectly. I've kept my memory pointer so I can free all heap memory used at the end in one go, but all other changes you've recommended have worked perfectly. Thank you so much for your help. I'm just having a bit of trouble understanding exactly how it worked, but I think I need to read up on memory allocation/management. Thanks again
    – Disierd
    Jul 19, 2020 at 18:53
1

You should write a complete unload function on your own by going through the walkthrough as you were supposed to write it down.

You should traverse through the linked lists and free(node) one at a time until it reaches NULL and then moves to next hash index and again traversing the linked list.

Following this method will hopefully makes valgrind happy

But again it depends on you how you think and your code too :)

Improve this answer

You must log in to answer this question.

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