Comparison function as argument to use later on

Question

I am working on generic binary search trees and I have troubles to understand how passing function as parameter/argument works in C. I want to tell to my generic BST that it must use the compare_doubles() when a comparison is needed.

How it possible to instantiate a function pointer somewhere in my code when I am creating my empty BST in createBST() ?

Given this BST.h :

#include <stddef.h>
#include <stdbool.h>

typedef struct tree_t BinarySearchTree;

/* ------------------------------------------------------------------------- *
 * Creates an empty BST.
 * ARGUMENT
 * comparison_fn_t      A comparison function
 * BinarySearchTree bst = newBST(&compare_doubles);
 * ------------------------------------------------------------------------- */

BinarySearchTree* createBST(int comparison_fn_t(const void *, const void *));
bool insertInBST(BinarySearchTree* bst, const void* key, const void* value);

BST.c :

#include <stddef.h>
#include <stdlib.h>
#include "BinarySearchTree.h"

struct tree_t {
    const void *key;
    const void *value;
    const void *leftChild;
    const void *rightChild;
    //const void *comparison_fn_t; //try to have it as an argument 1st try
};

//int (*compare) (const void *, const void *); //try to save it for later 2nd try

BinarySearchTree* newBST(int comparison_fn_t(const void*, const void*)) {
    BinarySearchTree *binarySearchTree = malloc(sizeof(BinarySearchTree));
    if (!binarySearchTree)
        return NULL;
    binarySearchTree->value = NULL;
    binarySearchTree->key = NULL;
    binarySearchTree->leftChild = NULL;
    binarySearchTree->rightChild = NULL;
    compare = &comparison_fn_t; //1st try
    //binarySearchTree->comparison_fn_t = comparison_fn_t //2nd try
    return binarySearchTree;
}
bool insertInBST(BinarySearchTree* bst, const void* key, const void* value) {
    //other code
    int val = (*compare) (key, bst->key); //1st try
    int val = bst->comparison_fn_t... //2nd try
}

In my Main.c :

int compare_doubles(const void *a, const void *b) {
    const double *a_ = (const double*) a;
    const double *b_ = (const double*) b;
    return (*a_ > *b_) - (*a_ < *b_);
}

BinarySearchTree *searchTree= createBST(&compare_doubles);
insertInBST(searchTree, key, value);

Answer 1

Just use the same function pointer definition in the struct:

struct tree_t {
    const void *key;
    const void *value;
    const void *leftChild;
    const void *rightChild;
    int (*comparison_fn)(const void*, const void*);
};

BinarySearchTree* newBST(int (*comparison_fn)(const void*, const void*)) {
    
    ...
    // assign the fn pointer here
    binarySearchTree->comparison_fn = comparison_fn;
    return binarySearchTree;
}

To make the syntax simpler, you can use a typedef:

typedef int (*BinaryComparison)(const void*, const void*); 

struct tree_t {
    const void *key;
    const void *value;
    const void *leftChild;
    const void *rightChild;
    BinaryComparison comparison_fn;
};

BinarySearchTree* newBST(BinaryComparison comparison_fn) {
    BinarySearchTree* binarySearchTree = malloc(sizeof *binarySearchTree);
    binarySearchTree->comparison_fn = comparison_fn;
    return binarySearchTree;
}

Answer 2

For starters it is unclear why data members leftChild and rightChild have the type const void * instead of the type struct tree_t *.

struct tree_t {
    const void *key;
    const void *value;
    const void *leftChild;
    const void *rightChild;
    //const void *comparison_fn_t; //try to have it as an argument 1st try
};

Also there is no great sense to store the pointer to the function as a data member of this structure because in this case this data member will be duplicated in each node of the binary tree.

You could declare one more structure as for example

struct node_t {
    const void *key;
    void *value;
    struct node_t *leftChild;
    struct Node_t *rightChild;
};

and

struct tree_t {
    struct node_t *head;
    int ( *comparison )( const void *, const void * );
};

typedef struct tree_t BinarySearchTree;

In this case you could create an object of the type struct tree_t the following way

BinarySearchTree * createBST( int comparison( const void *, const void * ) )    
{
    BinarySearchTree *tree = malloc( sizeof( *tree ) );

    if ( tree != NULL )
    {
        tree->head = NULL;
        tree->comparison = comparison;
    }

    return tree;
}

int compare_doubles(const void *a, const void *b) {
    const double *a_ = (const double*) a;
    const double *b_ = (const double*) b;
    return (*a_ > *b_) - (*a_ < *b_);
}


int main( void )
{
    BinarySearchTree *tree = createBST( compare_doubles );
    //...
}