0

I have basically finished the code, no memory leaking and tests work out fine. However, Valgrind is not happy: Conditional jump or move depends on uninitialised value(s): line 141

This is one of the two issues. I don't even have an idea on what to try, logically:

if (table[i] != NULL)
        {
            node *tmp = table[i];
line 141|   while (tmp != NULL)
            {
                node *freer = tmp;
                tmp = tmp->next;
                free(freer);
            }
        }

A few lines under that, at free(freer); Valgrind says it's an Invalid free() but I dont't know how else to solve the problem.

Although everything is working in the loading function Valgrind says something similar there: Conditional jump or move depends on uninitialised value(s): line 36:

node *cursor = table[hash_num];
line 36|while (cursor->next != NULL)
        {
            if (strcasecmp(word, cursor->word) == 0)
            {
                return true;
            }
            cursor = cursor->next;
        }

Thanks in advance for any help! Here is the entire code for context, if necessary:

// Implements a dictionary's functionality

#include <stdbool.h>
#include <stdlib.h>
#include <stdio.h>
#include <string.h>
#include <strings.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;

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

int dict_size = 0;

// Hash table
node *table[N];

// Returns true if word is in dictionary else false
bool check(const char *word)
{
    //printf("%s\n", word);
    //node *cursor = malloc(sizeof(node));
    int hash_num = hash(word);
    if (hash_num >= 0 && hash_num < 676)
    {
        node *cursor = table[hash_num];
        while (cursor->next != NULL)
        {
            if (strcasecmp(word, cursor->word) == 0)
            {
                return true;
            }
            cursor = cursor->next;
        }
    }
    else
    {
        return false;
    }
    return false;
}

// Hashes word to a number
unsigned int hash(const char *word)
{
    int hnum = 0;
    if (strlen(word) > 1)
    {
        if (word[0] >= 65 && word[0] <= 90)
        {
            hnum += (word[0] - 65) * 26;
        }
        else
        {
            hnum += (word[0] - 97) * 26;
        }
        if (word[1] >= 65 && word[1] <= 90)
        {
            hnum += (word[1] - 65);
        }
        else
        {
            hnum += (word[1] - 97);
        }
    }
    else
    {
        if (word[0] >= 65 && word[0] <= 90)
        {
            hnum += (word[0] - 65);
        }
        else
        {
            hnum += (word[0] - 97);
        }
    }
    return hnum;
}

// Loads dictionary into memory, returning true if successful else false
bool load(const char *dictionary)
{
    char input[LENGTH];
    FILE *dict = fopen(dictionary, "r");
    if (dict == NULL)
    {
        printf("Unable to load.\n");
        return false;
    }
    while (fscanf(dict, "%s", input) != EOF)
    {
        node *n = malloc(sizeof(node));
        if (n == NULL)
        {
            return false;
        }
        strcpy(n->word, input);
        if (table[hash(input)] == NULL)
        {
            table[hash(input)] = malloc(sizeof(node));
        }
        n->next = table[hash(input)];
        table[hash(input)] = n;
        dict_size++;
        //free(n);
    }
    fclose(dict);
    return true;
}

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

// Unloads dictionary from memory, returning true if successful else false
bool unload(void)
{
    for (int i = 0; i < N; i++)
    {
        if (table[i] != NULL)
        {
            node *tmp = table[i];
            while (tmp != NULL)
            {

                node *freer = tmp;
                tmp = tmp->next;
                free(freer);
            }
        }
    }
    for (int i = 0; i < N; i++)
    {
        if (table[i] != NULL)
        {
            free(table[i]);
        }
    }
    return true;
}
0

Let's start with the invalid free. The first for loop will actually free table[i] as the first node to be freed on each linked list. Then the second for loop is trying to free all of those nodes again. That's why it's an invalid free. It's already been done. You should be able to delete the entire second for loop.

The conditional jump issue is more complicated. It goes back to how table is initialized. The compiler looks at whether there is potentially any way that something is not initialized, and it found one. In this case, it traces all the way back to table[]. There's also a potential memory leak here too, but it's being masked by the same issue.

The central problem is that table[] is never initialized. It's created, but when pointers are created, they are not set to any value by default. They will just contain whatever garbage data is in that physical memory location. The code should initialize table[] at the start of load(). A simple for loop that sets all the array elements to NULL will work nicely.

Here's the memory leak that's being masked:

    if (table[hash(input)] == NULL)
    {
        table[hash(input)] = malloc(sizeof(node));
    }

This is allocating memory to table[], but a few lines later, the array pointer is being set to the address in n. The result is that the newly malloc'd memory is lost/leaked. But since table[...] is never set to NULL, it's not showing up in valgrind.

Bottom line, add the for loop initialization and delete the if code above.

There may be other issues, but that would be for a new question. Happy coding! ;-)

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

1
  • I have deleted the for loop at the end now and the invalid free issue is gone. However, deleting the given if condition made the code completely lose its function; it does not pass any tests anymore. Adding the said for loop for initialization seemed logical but it looks like it did not have the expected effect. The rest of the code is as it is and the two conditional jump issues are still there :/ any ideas? – MO_TM Jun 14 '20 at 9:11
0

Okay, I figured it out. First of all, everything Cliff B said is right. Additionally I had to change the condition in the while loop in the "check" function: while (cursor->next != NULL) checks wether the pointer points to another node, but in the last iteration it iterates to NULL which means that looking for another pointer to another node is a Segfault. After changing that to while (cursor != NULL) and changing everything Cliff B said, it worked.

You must log in to answer this question.

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