Generic C for binary trees

Question

How is it possible to write generic c?

I started writing a collection of balanced trees (scapegoat, splay, aa and so on) and find many things in common. Example is destroy function found below.

Can such function and those similar be defined with void pointers without causing "dereferencing void* pointer error"?

Example destroy function

void splay_node_linked_destroy(SplayNode **this) {
 72   if(*this == NULL) {
 73     return;
 74   }
 75   SplayNode *root = (*this)->root, *previous, *next;
 76   while(root) {
 77     if(previous == root->parent) {
 78       // todo use funcs for comparisons for generic
 79       if(root->left) {
 80         next = root->left;
 81       } else if(root->right) {
 82         next = root->right;
 83       } else {
 84         next = root->parent;
 85       }
 86     } else if(previous == root->left) {
 87       if(root->right) {
 88         next = root->right;
 89       } else {
 90         next = root->parent;
 91       }
 92     } else {
 93       next = root->parent;
 94     }
 95     previous = root;
 96     if(next == root->parent) {
 97       splay_node_destroy(&root);
 98       // todo use callback here to make generic
 99     }
100     root = next;
101   }
102 }

Answer 1

Actually it's quite possible, and reasonably easy, to write C functions which handle "arbitrary" (generic) data types for a given algorithm.

One trick is to use void pointers and to design APIs in such a way that you use wrapper functions to translate the pointers to their actual types and thus benefit with as much type checking and safety as C will allow for. The only hard part is the compiler doesn't normally help you with passing type information to your implementation, though some compilers do support the typeof() extension which makes it possible to write wrapper macros that will do the job for you.

Some Examples:

This example appears to use typeof() in the way I suggested: https://github.com/troydhanson/uthash/tree/master/src

This is an interesting pre-processor macro based library inspired by the Standard Template Library: http://sglib.sourceforge.net/

This is perhaps one of the most complete examples of generic algorithms for generic types in C, though it is a bit ugly and very wordy and perhaps not as efficient: http://home.gna.org/gdsl/

This answer gives good advice, though it uses an embedded union instead of a void pointer. A union is ideal if you know ahead of time what all the possible types of data will be:
https://stackoverflow.com/a/2891570/816536

Another interesting way to build high-level structures (like lists) out of generic data structures is what might be described as the inside-out technique (I like this one too!). What I would consider the canonical implementation of that inside-out technique is found in the 4.4BSD queue(3) and tree(3) macros with some more readable explanations and examples here:

• http://unixjunkie.blogspot.ca/2006/12/lists-and-queues.html
• http://blog.jasonish.org/2006/08/19/tailq-example/
• http://hackab.it/2014/01/generic-linked-list-in-c/

This answer describes a heavily pre-processor dependent technique, though it requires that you either know in advance what all the object types will be, or force the user to write the intermediate header for their specific data type: https://stackoverflow.com/a/10430893/816536

See also these answers:

• https://stackoverflow.com/a/668567/816536
• https://stackoverflow.com/a/13225017/816536
• https://stackoverflow.com/a/28139957/816536
• https://stackoverflow.com/a/649673/816536

Answer 2

Here is an example of a generic tree destroy:

// GenericTree.h

void genericTreeDestroy(void *treeNode,  void (*fUserFree)(void *));

// GenericTree.c
typedef struct TREE_NODE {
    struct TREE_NODE *left;
    struct TREE_NODE *right;
};
void genericTreeDestroy(struct TREE_NODE *treeNode,  void (*fUserFree)(void *))
{
    if (treeNode->left)  genericTreeDestroy(treeNode->left,  fUserFree);
    if (treeNode->right) genericTreeDestroy(treeNode->right, fUserFree);
    if (fUserFree) fUserFree(treeNode);
    free(treeNode);
}

// UserStuff.c
#include "GenericTree.h"
typedef struct MY_TREE_NODE {
    struct MY_TREE_NODE *left;
    struct MY_TREE_NODE *right;
    int some_value;
    char *name;
};
void my_freedata(struct MY_TREE_NODE *node);

void main(void)
{
    struct MY_TREE_NODE *myTree= calloc(1,sizeof(struct MY_TREE_NODE));
    myTree->name= malloc(strlen("Hello world")+1);
    genericTreeDestroy(myTree, my_freedata);
}

void my_freedata(struct MY_TREE_NODE *node)
{
    free(node->name);
}

The trick is that ALL trees must start with the left and right member. The .h file defines the genericTreeDestroy with void * parameter and the .c file defines it as struct TREE_NODE *. In this way the user can pass it any tree node type.

Next the user can define any tree node type (as long as it beings with the left and right member) and call the generic function to destroy it. The generic function can be given a function to do any clean-up of the user defined node type, or null if that is not needed.

In the same way you can define other functions. Here is a search function:

// .h
void *generic_tree_search (void *tree, void *value, int (*fUserCmp)(void *value, void *node));

// .c
void *generic_tree_search (struct TREE_NODE *treeNode, void *value, int (*fUserCmp)(void *value, void *node))
{
    while (treeNode) {
        switch (fUserCmp(value,treeNode) {
        case -1: if (treeNode->left) treeNode= treeNode->left; else return(0); break;
        case  0: return(treeNode);
        case +1: if (treeNode->right) treeNode= treeNode->right; else return(0); break;
        }
    }
    return(0);
}