0

I get double free or corruption (fasttop)\n Aborted when I run my code. Somehow, only small dictionary can handle up to around 50 words perfectly but sometimes it can only handle 10 words; other than that, my program gets double free... or free(): double free detected in tcache 2 error message.

(list of misspelled words)
double free or corruption (fasttop)
Aborted

Code:

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

//I can set up double the number of alphabet
// (214,091 + 1) 50% more than entry avoids collisions
const unsigned int N = 1000;

// when declared globally all the values in array are initiated to 0
node *table[N];

//set up a counter for size function
unsigned int counter = 0;

// Returns true if word is in dictionary, else false
bool check(const char *word)
{
    //run hash function on the word input
    // convert word from text file to lower case
    char copy[strlen(word)];
    strcpy(copy, word);
    //create a copy of the word
    for ( int i = 0; copy[i] != '\0'; i ++)
    {
        copy[i] = tolower(word[i]); // not copy[i]?
    }

    int value = hash(copy);

    if (table[value] != NULL)
    {
        node *trv = table[value];
        // traverse linked list looking for the word (strcasecmp)
        while (trv != NULL) // do I put trv->next instead of trv?
        {
            //check node one by one
            if ( strcasecmp(word, trv->word) == 0)
            {
                return true;
            }
            // if not found move to the next node until it is NULL
            else
                trv = trv->next;
        }
    }
    return false;
}

//https://github.com/engineer-man/youtube/commit/31299f04b0a6fff3169dca33ca1ce5076151d2a8
//https://www.youtube.com/watch?v=wg8hZxMRwcw
unsigned int hash(const char *word)
{
    //read a string and spit out number for an index
    unsigned long int value = 0;
    unsigned int i = 0;
    unsigned int str_len = strlen(word);

    // do rounds of multiplication
    for (; i < str_len; ++i)
    {
        value = value * 37 + word[i];
    }
    //if hash value is greater than N, you can use % to get them in an appropriate range
    value = value % N;

    //google hash function mamth function
    return value;
}

// Loads dictionary into memory, returning true if successful, else false
bool load(const char *dictionary)
{
    //open dictionary file at speller.c *dictionary should be either argv[1] or default dictionary
    FILE *file = fopen(dictionary, "r");

    //check a = NULL or not
    if (file == NULL)
    {
        //return an error message
        //fclose(file);
        printf("Could not open dictionary");
        return false;
    }
    //read strings from file one at a time (one line)
    //do I just need an array? char[Length] str? space to hold a line from dict
    char line[LENGTH + 1]; // 1 for \n

    while(fscanf(file, "%s", line) != EOF)
    {
        // allocate memory to a new node to add a word
        node *newWord = malloc(sizeof(node));
        if (newWord == NULL)
        {
            fclose(file);
            printf("Not enough memory\n");
            return false;
        }

        //run the hashfunction and get an index
        unsigned int value = hash(line);

        //read from dictionary file or text file and copy the word to the newnode
        strcpy(newWord->word, line);
        //newword next pointer should be NULL
        newWord->next = NULL;

        //if there was is no nodes attached
        if (table[value] == NULL)
        {
            table[value] = newWord;
        }
        //if there are nodes linked already
        else
        {
            table[value] = newWord;
            newWord->next = table[value];
        }
        counter++;
    }
    fclose(file);
    return true;
}

// Returns number of words in dictionary using global variable
unsigned int size(void)
{
    return counter;
}

// Unloads dictionary from memory, returning true if successful, else false
bool unload(void)
{
    // for loop each pointer in the hash table array
    for ( int i = 0; i < N; i++)
    {
        node *list = table[i];
        while(list != NULL) 
        {
            node *trv = list->next;
            free(list);
            list = trv;
            counter--;
        }
    }
    if (counter == 0)
    {
        return true;
    }
    return false;
}    
0

1 Answer 1

1

The size, and distribution, of the dictionary is important. If any list has more that one word it's curtains. Every node, except a singleton, will point to itself because of this else clause in load:

 //if there are nodes linked already
 else
 {
     table[value] = newWord;
     newWord->next = table[value];
 }

[Full disclosure: my repro did not produce errors, it hung]

You must log in to answer this question.

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