0

so I've been working on that speller code recently. It's actually working good, but valgrind returns memory leaks.. I do "understand" the problem of the first leak, but can't find a solution. Same goes for the second one.

So first of all: This is the code:

// 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 word[LENGTH + 1];
    struct node *next;
}
node;

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

// Hash table
node *table[N];

// Returns true if word is in dictionary else false
bool check(const char *word)
{
    int indexHashed;
    int wordLength = strlen(word);
    char *lowerWord;
    lowerWord = malloc(sizeof(word) + 1);
    for (int n = 0; n < wordLength; n++)
    {
        lowerWord[n] = tolower(word[n]);
    }
    indexHashed = hash(lowerWord);
    if (table[indexHashed] == NULL)
    {
        free(lowerWord);
        return false;
    }
    else
    {
        char *newLow = lowerWord;
        for (node *nodeptr = table[indexHashed]; nodeptr != NULL; nodeptr = nodeptr -> next)
        {
            if (strcasecmp(nodeptr -> word, newLow) == 0)
            {
                return true;
                free(lowerWord);
            }
        }
        free(lowerWord);
    }
    free(lowerWord);
    return false;
}

// Hashes word to a number
unsigned int hash(const char *word)
{
    int isHashed;
    isHashed = 0;
    int length = strlen(word);
    if (length < 2)
    {
        isHashed = word[0] * 26;
    }
    if (length >= 3)
    {
        isHashed = isHashed + word[0] * 26 + word [1] * 26 + word [2] * 26;
    }
    if (length >= 5)
    {
        isHashed = isHashed + word[0] * 26 + word [1] * 26 + word [2] * 26 + word [4] * 26;
    }
    isHashed = isHashed + word[length - 1];
    return isHashed;
}

// Loads dictionary into memory, returning true if successful else false
bool load(const char *dictionary)
{
    FILE *f = fopen(dictionary, "r");   //dictionary wird geladen und in f gespeichert
    if (f == NULL)                      //wenn nicht erfolgreich - false
    {
        printf("File not found.\n");
        return false;
    }
    char *word;
    int hashed;
    word = malloc(sizeof(word + 1));
    int c = 0;
    while (fscanf(f, "%s", word) != EOF)//!= EOF
    {
        c++;
        dicSize++;
        node *n = malloc(sizeof(node)); //memory für Node wird gesichert.
        if (n == NULL)                  //errorcheck ob n wirklich existiert.
        {
            return false;
        }
        strcpy(n->word, word);          //die node hat eine variable mit dem namen word. durch den pfeil wird in die node n der string word gepackt
        hashed = hash(word);            //das wort wird für den index gehashed
        if (table[hashed] == NULL)      //falls dieser index noch nicht existiert
        {
            n->next = NULL;             //ist die nächste Node natürlich noch nicht vorhanden, dementsprechend Null.
            table[hashed] = n;          //im array wird die Node hinterlegt

        }
        else                            //Index ist anscheinend schon vorhanden
        {
            n->next = table[hashed];    //in der nächsten Node wird
            table[hashed] = n;          //Indexierung
        }
    }
    free(word);
    return true;
}

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

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

I know that I haven't "cleaned it up" yet.

So valgrind returns this:

running valgrind --show-leak-kinds=all --xml=yes --xml-file=/tmp/tmpjvs6smdf -- ./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...
Invalid write of size 1: (file: dictionary.c, line: 96)
Invalid read of size 1: (file: dictionary.c, line: 105)
Invalid read of size 1: (file: dictionary.c, line: 66)
Invalid read of size 1: (file: dictionary.c, line: 79)
Conditional jump or move depends on uninitialised value(s): (file: dictionary.c, line: 66)
Conditional jump or move depends on uninitialised value(s): (file: dictionary.c, line: 49)
Use of uninitialised value of size 8: (file: dictionary.c, line: 49)
Invalid write of size 1: (file: dictionary.c, line: 36)
Invalid read of size 1: (file: dictionary.c, line: 49)
18 bytes in 2 blocks are definitely lost in loss record 1 of 2: (file: dictionary.c, line: 33)
552 bytes in 1 blocks are still reachable in loss record 2 of 2: (file: dictionary.c, line: 86)

So for the first loss record, I get that I have to free lowerWord in the check function. I do that for the case "table[indexHashed] == NULL", but for the else case I don't do it. I tried plugging it in before return true, but that bricks the whole program. Now I plugged it in, which -obviously- doesn't work.. Any thoughts?

The second problem is that I open a file using fopen in the load function. Again, I have to close that file f at some point. But if I unload it at the end of the function (before, or after free(word)), it bricks my program again!

Any thoughts about the problems? Cheers and thanks!

1

One big problem is here: word = malloc(sizeof(word + 1));. word is a char*, sizeof(char*) is 8 (on the IDE). According to the spec "No word is longer than 45 characters"; make sure word can accomomdate that many bytes (plus 1 for the null-terminator!). Make sure all the mallocs can accommodate the expected data.

Speaking of null-terminator, make sure any variable that will be used as a string (eg lowerWord) is properly null terminated.

Remember: no code after a return statement will be executed.

The file pointer must be closed with fclose().

6
  • Hey there, thank you for the quick response! You are absolutely right! I changed that. But it ended up, not changing anything in the valgrind log. Do you have any other ideas? The thing is, as I said in my first post; I think, I know the two problems, I just don't know how to solve them. :(
    – Nik.clgn
    Jun 17 '20 at 13:42
  • What'dja change it to? It would be helpful to annotate the code to indicate where the valgrind errors are reported. Jun 17 '20 at 15:21
  • Hey there! Sure, this is the link to the code. link I pasted the valgrind output in the file at the bottom. I implemented @DinoCoderSaurus 's suggestion, but I'm still encountering problems.
    – Nik.clgn
    Jun 17 '20 at 16:28
  • info added to answer. Jun 18 '20 at 13:55
  • Thank you very much! I tried implementing the various suggestions: The char * was actually a very good one! I didn't think of that. I know that I have to close my file using fclose(f). If I add that line link that causes another error (munmap_chunk(): invalid pointer Aborted). So I'm pretty much clueless at that point.. For lowerWord I decided, to already declare it in the top of my program. If I don't do that and try to free the memory later, I'm getting errors again.. The main problem is the fclose affair..
    – Nik.clgn
    Jun 18 '20 at 18:02

You must log in to answer this question.

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