pset5 unload + valgrind

Question

I tried to solve problem with memory usage but did not figure out where is the problem.

Dictionary unloads successfully but still issue with memory access exists.

I think that problem with dictionary_list, where words are saved from dictionary before add them to table.

I tried the following:

1. free dictionary_list before each read from dictionary:

   if (dictionary_list != NULL) { free(dictionary_list); } I observed strange behaviour in table[] only the last word is saved, while all other words are deleted. For example, simple dictionary:

    aa
    a
    bb
    b
    c

when a is saved into table[0] it has correct values:

    table[0] -> word = a
    table[0] -> next -> word = aa

When bb is saved, I got the following in the table[]

  table[0] -> word = bb
  table[0] -> next -> word = bb

  table[1] -> word = bb

I don't understand why it happens, I free dictionary_list only one last read from dictionary.

For table I made link to the memory and table should save all links between the same hashes but by some reason during each reading new link is changed for all hashes.

For variable dictionary_list malloc is used - it is mandatory to free it, but

        if (table[hash_value] == NULL)
        {
            table[hash_value] = malloc(sizeof(node));

            if (table[hash_value] == NULL)
            {
                // todo
                return false;
            }
                            // todo
        }
        else
        {
                // todo
        }

check50 returns error:

A
cat
is
a
caterpillar
cATTT
IS
A
caterPillar
avv
free(): double free detected in tcache 2
Aborted

2. free the all links in dictionary_list

        if (dictionary_list != NULL)
        {
             for (node *temp = dictionary_list; temp != NULL; temp = temp -> next)
             {
                  node *n_temp = NULL;
                  if (temp != NULL)
                  {
                // todo
                  }
             }

        }

spellcheckers fails in the beginning:

free(): double free detected in tcache 2
Aborted

3. If do not free dictionary_list I got valgrind error:

    ==4963== LEAK SUMMARY:
    ==4963==    definitely lost: 0 bytes in 0 blocks
    ==4963==    indirectly lost: 0 bytes in 0 blocks
    ==4963==      possibly lost: 0 bytes in 0 blocks
    ==4963==    still reachable: 56 bytes in 1 blocks
    ==4963==         suppressed: 0 bytes in 0 blocks
    ==4963== 
    ==4963== For lists of detected and suppressed errors, rerun with: -s
    ==4963== ERROR SUMMARY: 87 errors from 6 contexts (suppressed: 0 from 0)

dictionary.c

 // Implements a dictionary's functionality
    
    #include <stdbool.h>
    
    #include "dictionary.h"
    #include "stdio.h"
    #include "stdlib.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;
    
    // Number of buckets in hash table
    const unsigned int N = 26;
    
    // Hash table
    node *table[N];
    
    // global variable dictionary - each function will have access to the values from that variable
    node *dictionary_list = NULL;
    
    // vocabulary size
    int vac_size = 0;
    
    // Returns true if word is in dictionary, else false
    bool check(const char *word)
    {
        // TODO

    free(small_case_word);
    return false;
}


// Hashes word to a number
unsigned int hash(const char *word)
{
    // TODO

    // hash value generates only for first letter
    // all  words which are started with the same letter are linked to that letter
    int hash_value = 0;
    hash_value = tolower(word[0]) - 97;
    // check hash_value generation
    // printf("hash_value: %d \n", hash_value);
    return hash_value;
}

// Loads dictionary into memory, returning true if successful, else false
bool load(const char *dictionary)
{
    // TODO

    FILE *read_dictionary = fopen(dictionary, "r");
    if (read_dictionary == NULL)
    {
        printf("Could not open file.\n");
        return false;
    }


    char *read_symbol = malloc(46 * sizeof(char));
    if (read_symbol == NULL)
    {
        return false;
    }

    unsigned int hash_value = 0;
    // node *temp_dictionary_list = NULL;

    while (fscanf(read_dictionary, "%s", read_symbol) != EOF)
    {
        // printf("read_symbol: %s \n", read_symbol);
        hash_value = hash(read_symbol);

        dictionary_list = malloc(sizeof(node));

        if (dictionary_list == NULL)
        {

            free(dictionary_list);
            fclose(read_dictionary);
            return false;
        }

        strcpy(dictionary_list -> word, read_symbol);
        dictionary_list -> next = NULL;

        if (table[hash_value] == NULL)
        {
            //TODO
         }
        vac_size++;
        // free(temp_dictionary_list);
        // free(dictionary_list);
    }

    free(read_symbol);
    fclose(read_dictionary);
    return true;


}

// Returns number of words in dictionary if loaded, else 0 if not yet loaded
unsigned int size(void)
{
    // TODO
    // vocabulary size is calculating in load funcition
    // vac_size is global variable
    // just return the value
    return vac_size;
}

// Unloads dictionary from memory, returning true if successful, else false
bool unload(void)
{
    // TODO


    // node *temp = NULL;
    // unload function should free all variables
    // but by some reason it does not work
    for (int i = 0; i <= N; i++)
    {
        if (table[i] != NULL)
        {
//todo
        }
    }
    return true;
}

valgrind summary:

    ==4963== Invalid read of size 8
    ==4963==    at 0x401E70: unload (dictionary.c:232)
    ==4963==    by 0x401768: main (speller.c:153)
    ==4963==  Address 0x4b9a740 is 48 bytes inside a block of size 56 free'd
    ==4963==    at 0x483CA3F: free (in /usr/lib/x86_64-linux-gnu/valgrind/vgpreload_memcheck-amd64-linux.so)
    ==4963==    by 0x401C1D: load (dictionary.c:155)
    ==4963==    by 0x4012CE: main (speller.c:40)
    ==4963==  Block was alloc'd at
    ==4963==    at 0x483B7F3: malloc (in /usr/lib/x86_64-linux-gnu/valgrind/vgpreload_memcheck-amd64-linux.so)
    ==4963==    by 0x401C27: load (dictionary.c:157)
    ==4963==    by 0x4012CE: main (speller.c:40)
    ==4963== 
    
    WORDS MISSPELLED:     2
    WORDS IN DICTIONARY:  14
    WORDS IN TEXT:        12
    TIME IN load:         0.03
    TIME IN check:        0.00
    TIME IN size:         0.00
    TIME IN unload:       0.00
    TIME IN TOTAL:        0.04
    
    ==4963== 
    ==4963== HEAP SUMMARY:
    ==4963==     in use at exit: 56 bytes in 1 blocks
    ==4963==   total heap usage: 40 allocs, 45 frees, 11,496 bytes allocated
    ==4963== 
    ==4963== 56 bytes in 1 blocks are still reachable in loss record 1 of 1
    ==4963==    at 0x483B7F3: malloc (in /usr/lib/x86_64-linux-gnu/valgrind/vgpreload_memcheck-amd64-linux.so)
    ==4963==    by 0x401C27: load (dictionary.c:157)
    ==4963==    by 0x4012CE: main (speller.c:40)
    ==4963== 
    ==4963== LEAK SUMMARY:
    ==4963==    definitely lost: 0 bytes in 0 blocks
    ==4963==    indirectly lost: 0 bytes in 0 blocks
    ==4963==      possibly lost: 0 bytes in 0 blocks
    ==4963==    still reachable: 56 bytes in 1 blocks
    ==4963==         suppressed: 0 bytes in 0 blocks
    ==4963== 
    ==4963== For lists of detected and suppressed errors, rerun with: -s
    ==4963== ERROR SUMMARY: 87 errors from 6 contexts (suppressed: 0 from 0)

Thank you in advance!

Answer 1

Solved all problems:

1. reachable memory - in linked list added a new item in the end:

• iterate to the last item in list (not to null, but the last which refers to
• allocate memory for new word in the list, add the word, and next -> null
• free temporary node

2. also met with some errors, like:

==1281== 
==1281== HEAP SUMMARY:
==1281==     in use at exit: 0 bytes in 0 blocks
==1281==   total heap usage: 46 allocs, 46 frees, 11,832 bytes allocated
==1281== 
==1281== All heap blocks were freed -- no leaks are possible
==1281== 
==1281== For lists of detected and suppressed errors, rerun with: -s
==1281== ERROR SUMMARY: 14 errors from 1 contexts (suppressed: 0 from 0)

in my case 14 errors are amount of words in the dictionary. to free memory I used for loop:

for (node *tmp = list; tmp != NULL; tmp = tmp->next)
{

}

by some reason valgrind treats the last iteration with NULL value as valid and "thinks" that your code is trying to access it. What is not true.

to fix this behaviour need to put iteration of tmp variable in the beginning:

for (node *tmp = list; tmp != NULL; tmp = tmp->next)
{
   tmp = tmp->next;
   // code below
}

the same is valid for while loop:

node *tmp = list
while (tmp->next)
{
   tmp = tmp->next;
   // code bellow
}

it will not work in

node *tmp = list
while (tmp->next)
{

   // code bellow
   tmp = tmp->next;
}

hope it will help you folks =)