Is this pointer to pointer redundant?

Question

Code is like this:

void insertNode(TreeNode **root, COMPARE compare, void* data) {
    TreeNode *node = (TreeNode *)malloc(sizeof(TreeNode));

    node->data = data;
    node->left = NULL;
    node->right = NULL;

    if(*root == NULL) {
        *root = node;
        return;
    }

    while(1){
        if(compare((*root)->data, data) > 0) {
            if((*root)->left != NULL) {
                *root = (*root)->left;
            } else {
                (*root)->left = node;
                break;
            }
        } else {
            if ((*root)->right != NULL) {
                *root = (*root)-> right;
            } else {
                (*root) -> right = node;
                break;
            }
        }
    }
}

Pointer is never used like root and is always used as (*root). Isn't it being TreeNode **root redundant? Can it be reduced in the argument to TreeNode *root and parts in the function body changed to just root from (*root). If not why?

Answer 1

No, it's not redundant. C is a strict pass-by-value language and, if you want to change a parameter passed in (and you do, trust me), C emulates pass-by-reference with pointers.

In your case, you want to change a variable of type TreeNode *, so you need to pass a pointer to that variable, which is why you have double indirection.

Don't be fooled by the fact you seem to already have a pointer, in your case, it's conceptually the same as:

void changeInt (int *pXyzzy) { *pXyzzy = 42; }

except that's for changing an int. If you wanted to change an int *, you would need:

int some_int = 42;
void changeIntPtr (int **ppXyzzy) { *ppXyzzy = &some_int; }

noting the added level of indirection. This is more akin to what you need since you're changing a pointer to something (so you need a double-pointer to it).

Without passing in &some_treenode_pointer_variable and setting it via *some_treenode_pointer_variable = something, the changed value never finds its way back to the caller (the variable, being pass-by-value, is a local copy only).

It may help to examine the following code and its output. Method 1 tries to change the pointer by simply setting it, method 2 uses a pointer-to-pointer method to try and change it:

#include <stdio.h>

static int someInt;

static void method1 (int *pXyzzy) {
    printf ("Pointer on calling method1    = %p\n", pXyzzy);
    pXyzzy = &someInt;
    printf ("Pointer on exiting method1    = %p\n", pXyzzy);
}

static void method2 (int **ppXyzzy) {
    printf ("Pointer on calling method2    = %p\n", *ppXyzzy);
    *ppXyzzy = &someInt;
    printf ("Pointer on exiting method2    = %p\n", *ppXyzzy);
}

int main (void) {
    int *plugh = NULL;

    printf ("Pointer in main on start      = %p\n", plugh);
    method1 (plugh);
    printf ("Pointer in main after method1 = %p\n", plugh);
    method2 (&plugh);
    printf ("Pointer in main after method2 = %p\n", plugh);

    return 0;
}

The output is:

Pointer in main on start      = 0x0

Pointer on calling method1    = 0x0
Pointer on exiting method1    = 0x404018
Pointer in main after method1 = 0x0

Pointer on calling method2    = 0x0
Pointer on exiting method2    = 0x404018
Pointer in main after method2 = 0x404018

You can see that, although the value of the local variable is changed in method 1, that doesn't get reflected back to the caller main. Method 2 does reflect the change back to the caller.

---

As an aside, you shouldn't cast the return value of malloc in C:

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

It can hide certain subtle errors and it's totally unnecessary since C explicitly casts void * to other pointer types. Better to use:

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

You should also check the return value of malloc to ensure you haven't gotten NULL back, lest the following line:

node->data = data;

will cause you no end of grief.