0

Been scratching my head at this for a while now. I use FREE() only once in the program, and don't know why I get this error. Any help is appreciated :-)

// Implements a dictionary's functionality

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

// Keep track of how many words are loaded into the dictionary
unsigned int word_count = 0;

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

// Hash table
node *table[N];
node *traveller;



// Returns true if word is in dictionary, else false
bool check(const char *word)
{

    unsigned int hashed = hash(word);
    traveller = table[hashed];
    while (traveller != NULL)
    {
      if (strcasecmp(traveller->word, word) == 0)
      {
        return true;
      }
      traveller->next = traveller->next;
    }
    return false;
}

// Hashes word to a number
unsigned int hash(const char *word) // CREDIT: Dan Berstein http://www.cse.yorku.ca/~oz/hash.html
{
    int hash = 401;
    int c;

    while (*word != '\0')
    {
        hash = ((hash << 4) + (int)(*word)) %N;
        word++;
    }

    return hash % N;
}




// Loads dictionary into memory, returning true if successful, else false
bool load(const char *dictionary)
{
 char word[LENGTH + 1];
 FILE *file = fopen(dictionary, "r");

  if (file == NULL)
 {
    printf("Couldn't open dictionary\n");
    return false;
 }
   while (fscanf(file, "%s", word) != EOF)
   {
       node *p = malloc(sizeof(node)); // Maloc a new node for our hashed linked list
       if (p == NULL) // Check that the memory allocation is not NULL
       {
           printf("Error allocating node");
           return NULL;
       }
       strcpy(p->word, word); // Copy from the char buffer the string into the char field in the node
       p->next = NULL; // This will be the last node in the list so it must point to NULL
       word_count++; // Count how many strings read from file

       int hashed = hash(word); // Call the hash function to return a deterministic int value

       table[hashed] = p; // Using the hashed value as key to index into the root array of the list to point at the (initially) first node in the linked list

       p->next = table[hashed]; // Point new node to the first (old) node in the list contained in the pointer array value
       table[hashed] = p; // Point array pointer element to address of the new node


      
    }
    fclose(file);
    return true;


}

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

// Unloads dictionary from memory, returning true if successful, else false
bool unload(void)
{
    node *temp, *cursor; // Pointers to track/traverse/delete the linked list nodes
    for (int i = 0; i <= N; i++)
    {
        cursor = table[i];
        temp = cursor;

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

    }
    if (table[N - 1] == NULL)
    {
        return true;
    }
    else
    {
        return false;
    }

}

Execution:

~/pset5/speller/ $ ./speller dictionaries/small texts/cat.txt

Error message:

MISSPELLED WORDS

A is not a free(): double free detected in tcache 2 Aborted

1

This is a great lesson that a problem in one place is caused by a bug somewhere else. While the code in unload is mostly correct (there is a small flaw), the data that it's processing is flawed.

If you run the program under debug50, you would see that as unload runs, both cursor and cursor->next contain the same address. In fact, if you search through the linked list, they all appear to contain the same address.

While the free() statement only appears once, it is called repeatedly (and correctly) by the loop. The error is triggered because the free() statement is attempting to free the same address, stored in different nodes.

This means that there's a serious flaw in the creation of the linked list, meaning that the problem almost certainly lies in the load() function. I'm guessing that you haven't had a chance to work on it, I'll let you find the issue.

Hint: Why is the address of the new node assigned to table[hashed] twice? What does this do?

Bonus:

What do you think this line of code does?

traveller->next = traveller->next;

I'm actually surprised you didn't hit an infinite loop!

This should get you going.

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

5
  • Thank you for the excellent reply, and not disclosing the answer straight out, that would have ruined the fun :-) I used Valgrind, showing that the program kept trying to free already freed memory but your reply really pointed (no pun intended) me in the right direction, and I now understand cause/solution. But using debug50 doesn't show me the value of cursor->next because a line earlier cursor shows as null, causing the program to skip the while loop altogether. I'm curious if you happen to know why this might be? Oct 9 at 21:38
  • Re: traveller->next = traveller->next; (facepalm)--Thanks for the hint about the unload function!--for loop condition needs to be N - 1 not N. Before fixing it, it caused another memory error when trying to free what was already freed. Oct 9 at 23:10
  • Well, that's another lesson. Fixing one thing can expose other errors that exist - sometimes a lot more! It isn't that you've made it worse (usually), it's that you've revealed something that was already there.
    – Cliff B
    Oct 10 at 2:53
  • RE: debug. There can be several reasons for your experience. First, there are 10k buckets. You'd need to set the breakpoint just inside the loop in unload and hit run to get to the problem, or you'll be tracing for days just to get there. Next, remember that the highlighted line has not yet executed when debug pauses execution. Values shown in the debugger are what exist up to that point. Having said that, if you get into the while loop, you can expand the tree by clicking on the little triangles recursively. Hope that's enough so you figure it out. ;-)
    – Cliff B
    Oct 10 at 2:58
  • I just wanted to say thank you. I always want to understand when a program doesn't work, why that's the case, and your answer helped me get there :-) Oct 15 at 21:46

You must log in to answer this question.

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