0
// Implements a dictionary's functionality

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





// Represents a node in a hash table
typedef struct node
{
    char word[LENGTH + 1];
    struct node *next;
}
node;
int values = 0;
// Number of buckets in hash table
const unsigned int N = 10000;

// Hash table
node *table[N];
// Returns true if word is in dictionary, else false
bool check(const char *word)
{
    // TODO

    
    int word_length = strlen(word); 
    char low_word[word_length];
    strcpy(low_word, word);
 
   
    for (int i = 0; i < word_length; i++)
    {
        low_word[i] = tolower(low_word[i]);
    }
  
    
    int hash_index = hash(low_word);

    
    node *cursor = table[hash_index];
    if (cursor == NULL)
    {
        return false;

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

}



// Hashes word to a number
unsigned int hash(const char *word)
{
    unsigned long hash = 5381;
    int c;
    while ((c = toupper(*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)
{
    // TODO
    FILE *dict = fopen(dictionary, "r");
    if (dict == NULL)
    {
        printf("Invalid Dictionary\n");
        return false;
    }
    values = 0;
    char word[LENGTH + 1];
    while (fscanf(dict, "%s", word) != EOF)
    {

        node *newNode = malloc(sizeof(node));
        if (newNode == NULL)
        {
            return false;
        }
       
        strcpy(newNode -> word, word);
        

        int hash_index = hash(word);

        if (table[hash_index] == NULL)
        {
             table[hash_index] = newNode;
        }
        else
        {
            newNode -> next = table[hash_index];
            table[hash_index] = newNode;
        }
        values++;
    }
    fclose(dict);
    return true;
}

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


// Unloads dictionary from memory, returning true if successful, else false
bool unload(void)
{
    // TODO
    for (int i = 0; i < N; i++)
    {
        
        
        node *cursor = table[i];
        
        while (cursor != NULL)
        {
            node *tmp = cursor; 
            cursor = cursor -> next;
            free(tmp);
        }    
    }
    return true;
}
==9176== 
==9176== HEAP SUMMARY:
==9176==     in use at exit: 0 bytes in 0 blocks
==9176==   total heap usage: 143,096 allocs, 143,096 frees, 8,023,256 bytes allocated
==9176== 
==9176== All heap blocks were freed -- no leaks are possible
==9176== 
==9176== For lists of detected and suppressed errors, rerun with: -s
==9176== ERROR SUMMARY: 10000 errors from 1 contexts (suppressed: 0 from 0)

Asking for help...

==9176== Conditional jump or move depends on uninitialised value(s)

Looks like you're trying to use a variable that might not have a value? Take a closer look at line 145 of dictionary.c.

line 145 is the while (cursor != NULL) condition in my unload function

2
  • What is at line 145 in dictionary.c? Without any code, the most I can tell you is that, in my experience, "still reachable" usually means that a variable or some data was not freed by the time the program was terminated. – Robert S. Pratt Apr 13 at 22:59
  • it's the " while (cursor != NULL)" condition in my unload function bool unload(void) { // TODO for (int i = 0; i < N - 1; i++) { node *cursor = table[i]; while (cursor != NULL) { node *tmp = cursor; cursor = cursor -> next; free(tmp); } } return true; } – Steven George Apr 13 at 23:08
1

It's a very subtle "possible" error that valgrind detected. When I ran it with the small dictionary, I get this:

==224== Conditional jump or move depends on uninitialised value(s)
==224==    at 0x401CB1: unload (dictionary.c:145)
==224==    by 0x40175F: main (speller.c:152)
==224==  Uninitialised value was created by a heap allocation
==224==    at 0x483B7F3: malloc (in /usr/lib/x86_64-linux-gnu/valgrind/vgpreload_memcheck-amd64-linux.so)
==224==    by 0x401BAE: load (dictionary.c:101)
==224==    by 0x4012DE: main (speller.c:40)
==224== 

Line 145 is where the problem would raise it's ugly head:

    while (cursor != NULL)

But then, valgrind tells me that it's really at line 101:

    node *newNode = malloc(sizeof(node));

Now, you have to think about what's "uninitialized". Line 145 depends on the value of cursor, but after the first pass through this loop, it's going to depend on newLine->next. Now, if you go back to line 101 and subsequent lines, it seems that newLine->next is not initialized. That could potentially lead to the loop going beyond the end of the linked list due to garbage in the last node's next field.

This can be corrected by making sure the next field in each node is initialized immediately after the malloc, or by using calloc (which will automatically initialize every field.)

It's subtle, but this is the kind of bug that'll make you think about where it lies. It's also the kind of bug that gets into a program and can lurk in hiding for a long time and then frustrate programmers trying to find it!

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

1

The uninitialised value comes from load. Are you setting both members of the node in all cases? I don't see where you set your new node's next pointer in all cases.

1
  • crap~! Beat me again while I was typing!!! ;-) – Cliff B Apr 14 at 21:36

You must log in to answer this question.

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