0

This is my solution for pset5's speller problem, which uploads a dictionary with a hash table and checks an inputed text to find misspelled words. My code works fine when I run, but valgrind says "conditional jump or move depends on uninitialized values." It says this for two scenarios, one involving adding to a linked list with no values in it and the other involving the hash function djb2. For both of these, the error is "Conditional jump or move depends on uninitialised values." There is no leaked memory, though. I included my code and the valgrind errors below.

Here is the code: (Valgrind focuses on lines 61 and 96)

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

void freeRow(node *trav);

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

// Hash table
node *table[N];

// Number to keep track of # of words
int numNodes = 0;

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

    bool present = false;

    node *trav = table[h];

    //checks through the row with the word until found or ends
    while (trav != NULL && present == false)
    {
        if(strcasecmp(word, trav->word) == 0)
        {
            present = true;
        }
        trav = trav->next;
    }

    return present;
}

// Hashes word to a number
//CODE FROM HASH FUNCTION djb2 MADE BY DANNY BERNSTEIN (modified a little MattR47 stackoverflow)
unsigned int hash(const char *word)
{
    unsigned long hash = 5381;
    int c = 0;

    while ((c = *word++))
    {
        hash = ((hash << 5) + hash) + tolower(c);
    }

    return (int) hash % N;
}

// Loads dictionary into memory, returning true if successful else false
bool load(const char *dictionary)
{
    FILE *file = fopen(dictionary, "r");
    if (file == NULL){
        printf("File could not be loaded\n");
        return false;
    }

    //until end of file takes words from file and adds to hash table 
    while (!feof(file))
    {
        char *word = malloc(sizeof(char) * (LENGTH + 1));
        fscanf(file, "%s", word);

        int h = hash(word);

        //adds first node to linked list if currently empty
        if (table[h] == NULL)
        {
            table[h] = malloc(sizeof(node));

            if (table[h] == NULL){
                printf("File could not be loaded\n");
                return false;
            }

            strcpy(table[h]->word, word);
            table[h]->next = NULL;
        }

        //adds additional nodes to link list if not empy
        else
        {
            node *n = malloc(sizeof(node));

            if (table[h] == NULL){
                printf("File could not be loaded\n");
                return false;
            }

            strcpy(n->word, word);
            n->next = table[h];
            table[h] = n;
        }
        numNodes++;

        free(word);
    }

    fclose(file);
    return true;
}

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

//recursive function to free all the nodes in a linked list
void freeRow(node *trav)
{
    if (trav == NULL)
    {
        return;
    }

    freeRow(trav->next);

    free(trav);
}

// Unloads dictionary from memory, returning true if successful else false
bool unload(void)
{
    //frees each linked list
    for (int i = 0; i < N; i ++)
    {
        freeRow(table[i]);
    }
    return true;
}

Here are the valgrind errors :

==1042== Conditional jump or move depends on uninitialised value(s)
==1042==    at 0x401173: hash (dictionary.c:61)
==1042==    by 0x401262: load (dictionary.c:84)
==1042==    by 0x4009B4: main (speller.c:40)
==1042==  Uninitialised value was created by a heap allocation
==1042==    at 0x4C2FB0F: malloc (in /usr/lib/valgrind/vgpreload_memcheck-amd64-linux.so)
==1042==    by 0x401239: load (dictionary.c:81)
==1042==    by 0x4009B4: main (speller.c:40)
==1042== 
==1042== Conditional jump or move depends on uninitialised value(s)
==1042==    at 0x4C32DEC: strcpy (in /usr/lib/valgrind/vgpreload_memcheck-amd64-linux.so)
==1042==    by 0x40133B: load (dictionary.c:110)
==1042==    by 0x4009B4: main (speller.c:40)
==1042==  Uninitialised value was created by a heap allocation
==1042==    at 0x4C2FB0F: malloc (in /usr/lib/valgrind/vgpreload_memcheck-amd64-linux.so)
==1042==    by 0x401239: load (dictionary.c:81)
==1042==    by 0x4009B4: main (speller.c:40)
2
  • can you post the whole dictionary.c file so someone can compile/run/debug for you? – stensal May 27 '20 at 20:59
  • I added some header files and can compile your code. – stensal May 27 '20 at 21:05
0

The memory pointed by word is completely not initialized, and it is used in the condition of while ((c = *word++)). You can initialize word with zero. The reported line is off, because I have to add header files to build. Here is the link to build and run your code, you just click "Run" to see the error.

  Memory access warning: reading uninitialized memory; continue execution.
  # Reading 1 bytes from 0x91bfdc0 will read undefined data.
  #
  # The memory-space-to-be-read (start:0x91bfdc0, size:46 bytes) is allocated at
  #    file:/dictionary.c::80, 22
  # It is not initialized.
  #
  #  0x91bfdc0               0x91bfded
  #  +------------------------------+
  #  | the memory-space-to-be-read  |
  #  +------------------------------+
  #  ^~~~~~~~~~
  #      the read starts at the begin of the memory-space.
  #
  # Stack trace (most recent call first) of the read.
  # [0]  file:/dictionary.c::60, 5
  # [1]  file:/dictionary.c::83, 17
  # [2]  file:/speller.c::40, 19
  # [3]  [libc-start-main]
  # This detection can be configured with DTS_MEMORY_UNINIT_CHECK=<error|warning|disabled>.
5
  • Isn't word initialized when you input the value when calling the function hash, though? – reillyderrick May 27 '20 at 21:47
  • char *word = malloc(sizeof(char) * (LENGTH + 1)); fscanf(file, "%s", word); int h = hash(word); – reillyderrick May 27 '20 at 22:26
  • This is the context in which I use hash, so isn't word initialized by fscanf? – reillyderrick May 27 '20 at 22:27
  • the memory pointed by word is not COMPLETELY initialized if the string loaded by fscanf is not longer enough. You can add memset(word, 0, sizeof(char) * (LENGTH+1)); after malloc and try it again. – stensal May 28 '20 at 0:26
  • I looked at your code again, it could be possible that fscanf didn't read anything. But resetting the memory to zero is still worth to try. – stensal May 28 '20 at 0:50

You must log in to answer this question.

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