0

I am working on the speller problem, I got every test except for valgrind to pass. Here is the valgrind error:

running valgrind --show-leak-kinds=all --xml=yes --xml-file=/tmp/tmpbhs1m7v4 -- ./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...
Conditional jump or move depends on uninitialised value(s): (file: dictionary.c, line: 45)
Conditional jump or move depends on uninitialised value(s): (file: dictionary.c, line: 46)
Use of uninitialised value of size 8: (file: dictionary.c, line: 46)
Conditional jump or move depends on uninitialised value(s): (file: dictionary.c, line: 145)

And here is my code:

// Implements a dictionary's functionality

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

#include "dictionary.h"

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

void free_list(node *ptr);
bool set_in_table(const int index, const char *word);

int word_count = 0;


// TODO: Choose number of buckets in hash table
const unsigned int N = 676;

// Hash table
node *table[N];

void free_list(node *ptr);
bool set_in_table(const int index, const char *word);

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

    if(table[index] == NULL) { //line 45
        return false;
    }
    node *ptr = table[index];

    while(ptr != NULL) {
        if(strcasecmp(word, ptr->word) == 0) {
            return true;
        }
        ptr = ptr->next;
    }
    
    return false;
}

// Hashes word to a number
unsigned int hash(const char *word)
{
    // TODO: Improve this hash function
    if(word[1] == '\0') {
        return ((toupper(word[0]) - 'A') * 26);
    }
    return ((toupper(word[0]) - 'A') * 26) + (toupper(word[1]) - 'A');
}

// Loads dictionary into memory, returning true if successful, else false
bool load(const char *dictionary)
{
    // TODO
    FILE *fp;
    fp = fopen(dictionary, "r");
    if (fp == NULL) {
        return false;
    }
    char c;
    int i = 0;
    char word[LENGTH + 1];
    while (fread(&c, sizeof(char), 1, fp)) {
        if (c == '\n') {
            word_count++;
            word[i] = '\0';
            int index = hash(word);
            bool success = set_in_table(index, word);
            if (!success) {
                fclose(fp);
                return false;
            }
            i = 0;
            for (int j = 0; j < i; j++) {
                word[j] = 0;
            }
        } else {
            word[i] = c;
            i++;
        }
    }
    fclose(fp);
    return true;
}

bool set_in_table(const int index, const char *word) {
    node *n =  malloc(sizeof(node));
    if (n == NULL) {
        return false;
    }
    int i = 0;
    while(word[i] != '\0') {
        n->word[i] = word[i];
        i++;
    }
    // n->next = table[index];
    // table[index] = n;
    if (table[index] == NULL) {
        table[index] = n;
    }
    else {
        n->next = table[index];
        table[index] = n;
    }
    return true;
}

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

void free_list(node *ptr) {
    if(!ptr) {  //line 145
        return;
    } else {
        free_list(ptr->next);
    }
    free(ptr);

}

So the problem seems to be when I check for NULL, but I have seen others solutions and it works just fine for them, but when I copy it into my code it doesn't.

So the question is, why is mine failing?

2
  • please format your code with style50 before posting in future... and consider style50 and updating this code...
    – UpAndAdam
    Commented May 10 at 19:53
  • is this the new 2024 version of the problem? it looks different from before used to be 'unload` instead of free_list i can only assume set_in_table was something you came up with
    – UpAndAdam
    Commented May 10 at 20:11

1 Answer 1

0

first:
this bunch of code in your load function does nothing because the preceeding line you set i=0

            for (int j = 0; j < i; j++) {
                word[j] = 0;
            }

second: you duplicate yourself, you define functions multiple times
this appears twice:

void free_list(node *ptr);
bool set_in_table(const int index, const char *word);

Third THIS IS YOUR MAIN PROBLEM:
You never initialize table properly. You need to initialize table to NULL initially. Probably want to do this at the beginning of load before you start the read loop.

for (int i = 0; i < N; i++ )
{
    table[i] = NULL;
}

Also, you need to initially set n->next = NULL in the positive if branch where it becomes table[index] = n; as currently stands the value for n->next on first insertion is undefined.

that whole body as written is duplicative, you miss the only thing you need to do different properly in the if and duplicate an action you take unconditionally.

consider insted of

if (table[index] == NULL) {
    /* you are missing: `n->next = NULL` here */
    table[index] = n;
}
else {
    n->next = table[index];
    table[index] = n;
}

using

if (table[index] == NULL) {
    n->next = NULL;
}
else {
    n->next = table[index];
}
table[index] = n;

See how that's clearer and avoids duplicate code?

You must log in to answer this question.

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