0

Getting a double free error with gdb and valgrind points to my unload function as the cause in particular this part cursor = cursor->next; but I am not sure what's wrong with it.

From what I can see unload starts on the last word in the dictionary (ie highest numbered word with next=null), it isolates and frees it but doesn't seem to link properly to free the next node in the list.

Valgrind gives:

 =3905== Invalid read of size 4
==3905==    at 0x804938D: unload (dictionary.c:176)
==3905==    by 0x8048D34: main (speller.c:158)
==3905==  Address 0x41f51e8 is 48 bytes inside a block of size 52 free'd
==3905==    at 0x402B3D8: free (in /usr/lib/valgrind/vgpreload_memcheck-x86-linux.so)
==3905==    by 0x804939D: unload (dictionary.c:177)
==3905==    by 0x8048D34: main (speller.c:158)
==3905== 
==3905== Invalid free() / delete / delete[] / realloc()
==3905==    at 0x402B3D8: free (in /usr/lib/valgrind/vgpreload_memcheck-x86-linux.so)
==3905==    by 0x804939D: unload (dictionary.c:177)
==3905==    by 0x8048D34: main (speller.c:158)
==3905==  Address 0x41f51b8 is 0 bytes inside a block of size 52 free'd
==3905==    at 0x402B3D8: free (in /usr/lib/valgrind/vgpreload_memcheck-x86-linux.so)
==3905==    by 0x804939D: unload (dictionary.c:177)
==3905==    by 0x8048D34: main (speller.c:158)
==3905==

Code:

bool unload(void)
{
    for (int i = 0; i < 27; i++)
        {
           node* cursor = hashtable[i];

            while (cursor != NULL)
            {
                node* temp = cursor;
                cursor = cursor->next;
                free(temp);
             }

            free(cursor);     
          }
    return true;
}

Code to my other functions for reference:

Check

// define the node structure
    typedef struct node
    {
    char word[LENGTH + 1];
    struct node* next;
    }
    node;

// initialise a word counter
int counter;

// create hash table array
node* hashtable[27];

// create a hash function to use
int hash_function(char* word)
{
   // hash first letter of string
   int hash = tolower(word[0]) - 97;
   return hash % 27;
}

    /**
     * Returns true if word is in dictionary else false.
     */
    bool check(const char* word)
    {
        // create copy of word to hash and compare
        char check_word[strlen(word) + 1];
        int length = strlen(word);
        check_word[length] = '\0';

        /* Iterate over each charachter in word and 
         * convert to lower case if required.
         **/
         for (int i = 0, n = strlen(word); i < n; i++)
            {
                if (isupper(word[i]))
                   {
                        check_word[i] = tolower(word[i]);
                   }

                // Deal with non-letter characters by copying straight
                else
                {
                    check_word[i] = word[i];
                }       
            }

        // Need to hash word to find where it goes in array
        int check_hash = hash_function(check_word);    


        // Deal with the index check_hash maps to, if empty
        if (hashtable[check_hash] == NULL)
        {
            return false;
        }

        // Traverse linked list if index not empty
        else
        {

         // make a temp node 
        node* temp_node = hashtable[check_hash];

        // insert temp node 
        while (temp_node != NULL)
            {
                 if(strcmp(check_word, temp_node->word) == 0)
                 return true; 
                 temp_node = temp_node->next;  
            }
         } 
      return false;
    }

Load

**
 * Loads dictionary into memory.  Returns true if successful else false.
 */
bool load(const char* dictionary)
{

 // open dictionary file to read and check if NULL
 FILE* dict = fopen(dictionary, "r");
    if (dict == NULL)
     {
        printf("cannot %s\n", dictionary);
        return false;
     }


    for (int i = 0; i < 27; i++)
        {

            hashtable[i] = NULL;
        }

    // create a new node
    node* new_node = malloc(sizeof(node));

    // do this next code until the end of the dictionary is reached
    while(fscanf(dict, "%s", new_node->word) != EOF)
     {

    // hash the new word to find where it goes in array
      int hash = hash_function(new_node->word);

    // If the hash table index has nothing in it, put the word in
    if (hashtable[hash] == NULL)
     {
      hashtable[hash] = new_node;
      new_node->next = NULL;
     }
  else
      {
     // make a temp node 
     node* temp_node = hashtable[hash];

    // insert temp node 
   while (temp_node->next != NULL)
        {
           temp_node = temp_node->next;
        }
           temp_node->next = new_node;  
           new_node->next = NULL; 
        }

  counter++;

  fscanf(dict, "%s", new_node->word);
  }
  fclose(dict);
  return true;
}
1
  • I have exactly same unload code with you, the Valgrind keep point to one of my line which I initial hashtable[i]->next = NULL; I am wondering, is our unload code only free the Linked list node, but how do we free the hash table? i try free(hashtable), or free(hash table[i]) in the for loop, both not fixing the valgrind problem. – Lihong Wang Nov 30 '16 at 12:49
0
  1. How many hashtable nodes are you supposed to have?
  2. You free all the nodes *temp pointed to successively as you traverse the hash table. But at the end of your for loop, after freeing the last node you came from, *cursor is still pointing to a node.
5
  • Thanks for that I added a free cursor after the loop but still get an error. I have a hash table with a size of 27. – Steve23455 Nov 11 '15 at 19:43
  • Why is it size 27? – ronga Nov 12 '15 at 1:15
  • Hey, I did that for the letters of the alphabet plus a non-alphabet character, I think I was going to start with that and get it working then make it bigger. – Steve23455 Nov 12 '15 at 11:23
  • 1. Not sure why you'd need a non-alphabetic character in there since check ignores non-alphabetical characters, except for " ' ". 2. That's not the cause of your double free error, though. What's happening is you're freeing a node twice. Looks like it's occurring in line 177 of dictionary.c. Just get a pen and paper, make a rough outline of your hash table, and try going through the steps of your unload function, see where you're freeing the same node twice. – ronga Nov 12 '15 at 13:34
  • Thanks, I figured out what was wrong, there were quite a few things wrong in the code! But freeing cursor after while loop did fix unload I think. It was other code causing it to fault. – Steve23455 Nov 12 '15 at 15:44

You must log in to answer this question.

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