0

Sorry for asking about a valgrind-reported error that has been asked many times. I've read through many of the questions and responses, but I could not find an answer that applies to my problem. The code itself achieves its purpose, however valgrind continuously loads this error. Below is my code for the unload function which produced the error:

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

return true;

I understand that it has something to do with not initializing my hash table, but what perplexes me the most is that a similar piece of code in the same file works just fine (below is my code for the check function):

char s[LENGTH+1];
for(int i = 0; i < LENGTH+1; i++){
    s[i] = '\000';
}
int wordLength = strlen(word);
for(int i = 0; i < wordLength; i++){
    s[i] = (char) tolower(word[i]);
}
node *n = NULL;
n = table[hash(s)];
while(n != NULL){
    if(strcmp(n->word, s)==0){
        return true;
    }
    n = n->next;
}

return false;

If the unload function produced an error on the line:

while(n != NULL)

should the same problem not appear in the check function?

This is the code in its entirety:

// Implements a dictionary's functionality

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

#define BASE (256)

// 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 = 200;

// Hash table
node *table[N];




// Returns true if word is in dictionary else false
bool check(const char *word)
{
    // TODO
    char s[LENGTH+1];
    for(int i = 0; i < LENGTH+1; i++){
        s[i] = '\000';
    }
    int wordLength = strlen(word);
    for(int i = 0; i < wordLength; i++){
        s[i] = (char) tolower(word[i]);
    }
    node *n = NULL;
    n = table[hash(s)];
    while(n != NULL){
        if(strcmp(n->word, s)==0){
            return true;
        }
        n = n->next;
    }

    return false;
}

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

    /* cast s to unsigned const char * */
    /* this ensures that elements of s will be treated as having values >= 0 */

    us = (unsigned const char *) word;

    h = 0;
    while(*us != '\0') {
        h = (h * BASE + *us) % N;
        us++;
    }

    return h;
}
// Loads dictionary into memory, returning true if successful else false
bool load(const char *dictionary)
{

    node *n = malloc(sizeof(node));
    for(int i = 0; i < N; i++){
        table[i] = NULL;
    }
    FILE *file = fopen(dictionary, "r");
    char letters[LENGTH + 1];
    int countChar = 0;
    int hashNum = 0;
    for(int i = 0; i < (LENGTH + 1); i++){
        letters[i] = '\000';
    }
    for(char c = fgetc(file); !feof(file); c = fgetc(file)){
        if (c == '\n'){
            strcpy(n->word, letters);
            hashNum = hash(letters);
            if(table[hashNum] == NULL){
                table[hashNum] = malloc(sizeof(node));
                node *tmp = table[hashNum];
                strcpy(tmp->word, n->word);
            }else{
                node *tmp = table[hashNum];
                while(tmp->next != NULL){
                    tmp = tmp->next;
                }
                tmp->next = n;
            }
            countChar = 0;
            for(int i = 0; i < (LENGTH+1); i++){
                letters[i] = '\000';
            }
        }else{
            letters[countChar] = c;
            countChar++;
        }
    }
    free(n);
    fclose(file);
    return true;
}

// Returns number of words in dictionary if loaded else 0 if not yet loaded
unsigned int size(void)
{
    // // TODO
    unsigned int count = 0;
    node *tmpNode = NULL;
    for(int i = 0; i < N; i++){

        tmpNode = table[i];
        **while(tmpNode != NULL && tmpNode->word[0] != '\000'){**
            tmpNode = tmpNode->next;
            count++;

        }

    }
    return count;
}

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

    return true;
}

The lines that valgrind complained about are starred/bolded in the above code.

Thanks

6
  • Then why don't you try to initialize your table just loop through it then table[i] = NULL;
    – Ojou Nii
    Apr 30 '20 at 3:28
  • What is the relationship between N and the max value that hash returns? If, for instance, N is greater than max-hash value, and max-hash table elements are initialized to NULL, the error would be explained. Apr 30 '20 at 13:21
  • @Ojou Nii, I looped through the table in the load function (not shown in question). I tried to move that loop out of the function where the hash table is first defined, however that is outside of any function. Since this dictionary.c does not have a main function, I cannot include the table initialization in the main function. Apr 30 '20 at 17:15
  • @DinoCoderSaurus, N is a constant set to 200, which is the number of elements in the hash table. The result of the hash is modded by N (hash%N), so it should be within the range of N. Sorry I did not include this information in the question. Apr 30 '20 at 17:17
  • Exactly which line is valgrind complaining about? Sounds like you need to show the code where table is initialized. Apr 30 '20 at 17:37
0

table[hashNum] is allocated as a node here table[hashNum] = malloc(sizeof(node)); (instead of simply a node pointer). Therefore table[hashNum]->next needs to be initialized.

1
  • That worked! Thank you so much for the help! May 1 '20 at 14:46

You must log in to answer this question.

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