5

Need help again.

I've got my linked list working. It copies a list of words from a file into a linked list.

Now I want to make a hash table so that all words starting with the letter 'A' go into a bucket [0] of linked list.

The code I've written; it seems to work for small and large lists but Valgrind shows points to errors.

-----CODE-----
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <ctype.h>

typedef struct node     //struct for linked list
{
    char* word;
    struct node* next;
}
node;

int findhash(char firstletter)      //this function returns a hash value for first alphabet of every word
{
    int hash = 0;

    if(isupper(firstletter))
        hash = firstletter-'A';
    else hash = firstletter-'a';

    return hash;       
}

int main (void)
{            
    char* dictfile = "small";

    FILE* dict = fopen(dictfile, "r");

    if (dict == NULL)
        return 1;

    char oneword[47];      //to store the word from fscanf()

    node* hashtable [30];       //creates a hashtable        

    for (int i = 0; i < 30; i++)        //gives an index to every element in the hash table
    {
        node* temp = (node*)malloc(sizeof(node));
        temp->next = NULL;           
        hashtable[i] = temp;
    } 

    while ((fscanf (dict, "%s", oneword)) > 0)
    {                                        
        node* temp = (node*)malloc(sizeof(node));            
        char* tempword = (char*)malloc(strlen(oneword)+1); //gives me a new pointer to store the string (as pointed out by Antione)            
        strcpy(tempword, oneword);

        char firstletter = tempword[0];

        int hash = 0;
        hash = findhash(firstletter);      //returns an index for the first alphabet of the word                  
        temp->word = tempword;

        //printf("%s\n", temp->word);     //prints the value (just for debug)

        temp->next = hashtable[hash];            
        hashtable[hash] = temp;             
    }

    for (int i = 0; i < 30; i++)
    {           
        node* temp = (node*)malloc(sizeof(node));
        temp = hashtable[i];
        while (temp != NULL)    //loop to print the linked list 
        {           
            if (temp->word != NULL)    //**THIS IS WHERE VALGRIND IS POINTING THE ERROR TO BE**
            {
                printf("%s\n", temp->word);
                temp = temp->next;
            }
            else break;
        }   
    }

    printf("\n");
    fclose(dict);

    printf("SUCCESS!!\n");      

}    

Where am I going wrong?? Please help

    -----VALGRIND ERROR-----
    jharvard@appliance (~/Dropbox/pset5): valgrind ./tempeol
==11035== Memcheck, a memory error detector
==11035== Copyright (C) 2002-2013, and GNU GPL'd, by Julian Seward et al.
==11035== Using Valgrind-3.10.0.SVN and LibVEX; rerun with -h for copyright info
==11035== Command: ./tempeol
==11035== 
antione
==11035== Conditional jump or move depends on uninitialised value(s)
==11035==    at 0x80488CA: main (tempeol.c:68)
==11035== 
beer
bear
caterpillar
cat
google
root

SUCCESS!!
==11035== 
==11035== HEAP SUMMARY:
==11035==     in use at exit: 582 bytes in 74 blocks
==11035==   total heap usage: 75 allocs, 1 frees, 934 bytes allocated
==11035== 
==11035== LEAK SUMMARY:
==11035==    definitely lost: 480 bytes in 60 blocks
==11035==    indirectly lost: 102 bytes in 14 blocks
==11035==      possibly lost: 0 bytes in 0 blocks
==11035==    still reachable: 0 bytes in 0 blocks
==11035==         suppressed: 0 bytes in 0 blocks
==11035== Rerun with --leak-check=full to see details of leaked memory
==11035== 
==11035== For counts of detected and suppressed errors, rerun with: -v
==11035== Use --track-origins=yes to see where uninitialised values come from
==11035== ERROR SUMMARY: 30 errors from 1 contexts (suppressed: 0 from 0)

Valgrind shows 30 errors. My hashtable is size 30. So feel the problem should be somewhere there. But I can't figure out why?

12

The problem is mainly caused by the if statement on line 69

if (temp->word != NULL)
{
    // some code 
}

valgrind is angry because you never really initialized the member word of your struct pointed to by temp, yet you're trying to check whether it has NULL as a value. While the latter might be true, technically there's no guarantee that word will be equal to NULL because it was never initialized.

To fix that, you may initialize word with NULL as you create a new node.

Aside from that, there are some points that I wanna emphasize

  • your hash function may return a negative value in case the argument is not an uppercase character and has an ASCII value that is less than 97 (e.g., an apostrophe).
  • assuming only alphabetical characters and apostrophes, the highest value that you hash function can return is 25. That means that you only need only 26 buckets (not 30) in your array (assuming there are no words that start with an apostrophe).
  • you don't really need to allocate memory for all the buckets initially.
  • you could declare word as char [] and avoid manually allocating memory on the heap for each word and manually freeing it.

  • you could read into word directly instead of reading into oneword then copying back into tempword.

  • the assignment operator (i.e., =) basically takes the value of the right expression and assigns it to the variable on the left. That means that when you do something like

    node *temp = (node *) malloc(sizeof node);
    temp = hashtable[i];
    

    you lose reference to the memory that you have "unnecessarily" allocated at the first place and you'll never be able to free it.


Edit: the fix that I suggested above was just a way to satisfy valgrind.

The word members that valgrind complains about are those of the 30 nodes that you unnecessarily allocate memory for on line 39. You never initialize the word members of these nodes. Each of these nodes eventually becomes the last node of a chain. As you print the contents of the hash table, temp eventually becomes pointing to one of these nodes and that is the moment that valgrind thinks that you're checking a value of a variable that was never initialized.

To fix that you could do that on line 40

temp->word = NULL;

However, as the bullet points show, you could actually do way better. Here are some steps. Feel free to look at them for more hints. (these steps assume that word is a char [])

1. create an array of 26 node pointers named hashtable and init them all to NULL

// loading       
2. while true
3.     create a node pointer named temp and allocate memory for it
4.     read the next word into temp->word
5.     if there were no words in the file
6.         free temp
7.         break    
8.     hash temp->word and store the hash value into a variable named hash   
9.     set temp->next to hashtable[hash]
10.    set hashtable[hash] to temp
11.    go to 2

// printing
12. for each node in hashtable
13.     create a node pointer named cursor and set it to the current node
14.     while cursor is not a NULL pointer
15.         print out cursor->word
16.         set cursor to cursor->next
17.         go to 14
| improve this answer | |
  • @ Kareem Thanks. 1. If I initialize temp->word to NULL, I lose my linked list 2. I cannot initialise word. I want word to be equal to hittable[i]->word and check for null. If hashtable[i] is null, it means the bucket is empty. So I don't want to print it. 3. Yes thats true I don't need 30 buckets 4. I will try declaring word as char [] 5. I don't see any other way it can be done temp = hashtable[i] is necessary to print the linked list, right? – jzz Mar 21 '15 at 23:08
  • @jzz please look at the Edit section of the answer! – Kareem Mar 22 '15 at 10:29
  • @jzz I haven't really tested the pseudocode above with real code, so pardon me if there are any logical flaws! – Kareem Mar 22 '15 at 10:36
  • its okay, I'll test it out. Thanks for the pseudocode and not giving the solution directly. It's better that way otherwise it's just too easy :) – jzz Mar 22 '15 at 10:40
  • I got it working. The initialize did the trick. Here's the link: pastebin.com/zVj579Wz Thanks :). I have another question: Right now, the small dictionary takes up 454 bytes. Is there any way to improve that?? – jzz Mar 24 '15 at 16:34

You must log in to answer this question.

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