Valgrind segfaults, programm doesn´t

Question

I got problems implementing the trie-version of pset6.
Since I even got problems to identify the problem, I´m going to ask some questions during my elaboration.
Here is what what Valgrinds put out:

BUT the programm runs completly normal without any error, and when I use a smaller dictionary, valgrind doesn´t complain at all, saying all mallocs are freed.
First I thought something is wrong with my unload-function, but it´s actually too simple and straighforward:

unload function calls recursive helperfunction
    ulhelper(root[i]);

then

for (iteration through array)
{
    if (root[i] has child)
        ulhelper(root[i]->child);
    free(root[i]->child
}

Q1 When I count the mallocs and frees I free about 27 more often than I malloc, can I omit freeing NULL-Pointers?

So I assume the problem is in the load-function respectively the way I add nodes to the trie:
To keep track of my position in the trie I use 2 temporary nodes, and these 2 nodes cause the problems since I can´t free them without destroying the triestructure, hence I just initialzed them to NULL, so I don´t need to free them, but Valgrind still complains, so:
Q2 How do you keep track of your position in the trie? Is there a better/smarter/easier way?

Q3 My root is declared as an array of nodes "node* root[27]" since I saw no other way to store one letter words, but it makes the load function a little bit more complicated, is there a workaround?

Answer 1

According to valgrind, an invalid read of size 4 was made exactly at dictionary.c, function addTrie, line 256. "If ptr is NULL, no operation is performed" Apparently, this invalid read is the same one that causes the segmentation fault. Better check that you're not trying to read from a NULL pointer or something!

A1: From the manual pages for free, "If ptr is NULL, no operation is performed".

If you have two pointers that point to the same location in memory and you called free on one of them, you'll certainly free the memory that's pointed to by both of them. I see no problem at all with initializing one of them to NULL.

A2: Using a temporary pointer. For example, here's a simple algorithm for inserting a word into a trie whose root is an array of 26 chars (since no word starts with an apostrophe) and each node of which contains an array of 27 nodes named children and a bool member that indicates the end of a word

create a node pointer named temp and set it to NULL

for each char in word
{
    create an int named index and set it to the index of the current char
    if the current char is the first char
        set temp to root[index]
    else
        set temp to temp -> children[index]

    if temp doesn't have memory allocated for it
    {
        allocate memory for it
        set all the elements of the current node's children member to NULL
    }

    the current char is the last char? set the bool member to true; else, set it to false
}

This might not be the best algorithm to do it though!

A3: I think declaring the root of the trie as an array indicates that you're on the right track. Implementing a trie and the functions associated with it isn't the easiest thing to do comparing to something like taking the hash table approach, for example.

It's more efficient in loading and checking (O(k) where k is the length of the longest word) than a hash table (O(n) where n is the length of the longest chain). Yet it's less efficient when it comes to memory usage.