0

I think I have my speller working except for the below issue. I can't see any variable's I have not initialized properly. Valgrind points to my check function (the offending line is marked below):

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

// Hash table
node *table[N];

//counter variable to count number of words in dictionary loaded in hash table
int counter = 0;

// Returns true if word is in dictionary else false
bool check(const char *word)
{
    //ensure word is converted to lower case to produce the correct hash key
    char lowercase[LENGTH + 1];

    for (int i = 0; i < LENGTH + 1; i++)
    {
        lowercase[i] = tolower(word[i]);
    }


    int index = hash(lowercase);

    node *cursor = table[index];

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

    return false;
}

// Hashes word to a number - using djb2 hash function from http://www.cse.yorku.ca/~oz/hash.html
unsigned int hash(const char *word)
{
    unsigned long hash = 5381;
    int c;

    while ((c = *word++))
        hash = ((hash << 5) + hash) + c; /* hash * 33 + c */

    return hash % N;
}

// Loads dictionary into memory, returning true if successful else false
bool load(const char *dictionary)
{
    //open dictionary file using fopen
    FILE *inptr = fopen(dictionary, "r");
    if (inptr == NULL)
    {
        return false;
    }

    //read strings from file using fscanf
    char word[LENGTH + 1];

    while (fscanf(inptr, "%s", word) != EOF)
    {


        //hash word using hash function
        int index = hash(word);

       //create new node using malloc
        node *n = malloc(sizeof(node));

        //copy word into new node
        strcpy (n->word, word);
        n->next = NULL;

        //insert into the hash table
        if (n != NULL)
        {

            n->next = table[index];
            table[index] = n;
            counter++;

        }
        else return false;
    }

    fclose (inptr);
    return true;
}

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

    return counter;
}

// Unloads dictionary from memory, returning true if successful else false
bool unload(void)
{
    for (int i = 0; i < N; i++)
    {

    node *cursor = table[i];
    node *tmp;

        while (cursor != NULL)
        {
            tmp = cursor;
            cursor = cursor->next;
            free(tmp);
        }

    }
    return true;
}

I've been trying everything I can think of and studying similar questions all day but it's just not clicking. Any advice would be much appreciated. :)

2
  • can you please post the whole dictionary.c file? – stensal May 26 '20 at 14:27
  • Yea no problem, thanks. – GFitzP May 26 '20 at 14:47
0

Your char word[LENGTH+1]; is not FULLY uninitialized, it is read at lowercase[i] = tolower(word[i]);. The following is the diagnostic message. Here is the link to reproduce this error. You just need to click "Run" button to see it yourself.

  Memory access warning: reading uninitialized memory; continue execution.
  # Reading 1 bytes from 0xffc3fbff will read undefined data.
  #
  # The memory-space-to-be-read (start:0xffc3fbfc, size:46 bytes) is bound to 'word' at
  #    file:/speller.c::68, 10
  # It is not initialized.
  #
  #  0xffc3fbfc               0xffc3fc29
  #  +------------------------------+
  #  | the memory-space-to-be-read  |
  #  +------------------------------+
  #                  ^~~~~~~~~~
  #      the read starts at 3 bytes offset of the memory-space.
  #
  # Stack trace (most recent call first) of the read.
  # [0]  file:/dictionary.c::38, 24
  # [1]  file:/speller.c::112, 32
  # [2]  [libc-start-main]
  # This detection can be configured with DTS_MEMORY_UNINIT_CHECK=<error|warning|disabled>.
6
  • Sorry still a little confused, is that word array not initialized in speller.c to contain the words of the document to be spell checked? Struggling to follow the logic of this at the moment, possible blonde moment! – GFitzP May 26 '20 at 15:26
  • You terminated it at line 105. But when you convert the array to lower cases, you didn't stop at the null termination char '\0'. – stensal May 26 '20 at 15:36
  • Thank you for your help. I changed the i < LENGTH + 1 to < strlen(word)+1 and now it's fine. I initially tried adding the condition While (word[i] != '\0' but that seemed to break the whole program! – GFitzP May 26 '20 at 23:05
  • If you can think of any resources I could use to further improve my understanding? I'd be very grateful – GFitzP May 26 '20 at 23:06
  • You have followed the right track. If I can recommend something, I would say reading a C programming book and writing more code. – stensal May 28 '20 at 0:43

You must log in to answer this question.

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