Speller Unload Trie with Recursion

Question

node* root; 

bool unload(void)
{
    freenodes(root);
    return true;
}

freenodes function(node* path)
{  
    loop over all nodes 
    {
        if node is not null (path -> children[i]) 
        {
            freenodes (pass in new path (path -> children[i]));
        }
    }
    escapes loop if all nodes are NULL 

    free(path);
}

this returns a segfault.

1. Should I declare freenodes in the header file?

   1. When I do this I have to move my struct definition to the header file too as node is not defined there. This throws up errors for the definition of node, claiming I "redefine" it in the .c file. What is the syntax to define my struct node across all files?

2. I wrote this as an experiment, my understanding is that it will only free the one node i have formed a path down to, is this correct?

3. One error valgrind spits out is "conditional jump dependent on uninitialised value(s)" at the recursion call. Path is not initialised. Is this an inherent issue with the code or is there a way I can initialise root before it is input into freenodes?

4. Another error "Access not within mapped region at address 0x4", at the call to check if the node's value is NULL. (For this I initialised root to NULL in unload() before calling it into freenodes.

Answer 1

Should I declare freenodes in the header file?

It is not necessary to declare freenodes in the header file. However because freenodes is written after the function which calls it, it should be declared at the top of the .c file, like so:

void freenodes(node* path);

This is the same as the function signature used to define the function itself, with the difference that it also includes a semi-colon, and does not include the function body. This definition can appear anywhere in the code, as long as it appears before the point where the function is called. By convention, and for visibility, forward declarations like this are usually written near the top of the .c file.

What is the syntax to define my struct node across all files?

This is answered on StackOverflow. That said, for speller this is probably not necessary (nor desirable). The struct should only be declared in the .h file if it needs to be used by other code besides the corresponding .c code.

The code in dictionary.c should be self contained, and there should be no need to make additions in the .h file.

I wrote this as an experiment, my understanding is that it will only free the one node i have formed a path down to, is this correct?

Possibly. The pseudo code for escapes loop if all nodes are NULL introduces some uncertainty. What is the reasoning or intention behind this?

The code also makes the assumption that the first node passed in (the root node) is never NULL. What would occur in the situation where it is NULL?

The function should always check the initial conditions are correct before proceeding. In this case, it should check that path is not a NULL value. The rest of the program is responsible for ensuring that freenodes is passed a value that is either a valid pointer or NULL.

One error valgrind spits out is "conditional jump dependent on uninitialised value(s)" at the recursion call. Path is not initialised.

This means that the code is reading a value from a pointer (in this case path), but the pointer has never been set. This is a dangerous situation for the program to be in, because the pointer contains some memory address, but it's just some random address that the variable happened to contain when it was created. the program has no way of knowing that this pointer is not valid, and so it will try to access this random location, most likely resulting in a segfault as you saw.

Is this an inherent issue with the code or is there a way I can initialise root before it is input into freenodes?

This depends on how literal the pseudo code is. The code shows this:

node* root; 

This means that root is defined, but a value is never assigned to it, so it contains some random data.

A good coding practice is to ensure that pointers are always set to either the value NULL, or to a valid block of memory obtained using malloc, or & (the address-of operator). What this means in practice is that you assign a value (or NULL) to the variable when it is declared:

node* root = NULL;

Or

node* root = malloc(sizeof(node));

When the variable is deallocated using free, it should also be set to NULL, so that other code can check if the pointer is valid or not. If this is not done, then other code has no way of knowing whether pointer is valid, or whether it has been freed. A pointer which is freed but not set to NULL is referred to as a dangling pointer.

This also applies for the pointers in the children array. When the children array is allocated, each item will be referring to some random location. The program should set each value to NULL before proceeding.

A quick way to initialize an entire struct or array, is to use the memset function:

memset(new_node, 0, sizeof(node));

This will set the entire contents of new_node, including any variables and pointers, to the value 0. As you may know, 0 is equivalent to NULL, so any pointers will be initialized with NULL using this method.

Another error "Access not within mapped region at address 0x4", at the call to check if the node's value is NULL. (For this I initialised root to NULL in unload() before calling it into freenodes.

Again, this is probably due to root not being initialized, and hence containing some random data when it was defined. To correct this, assign NULL to root when it is defined, and after it is freed.