Generic datastructures in C

Question

I'm looking into creating a generic BST. Nothing fancy no COTS, but I'm trying to decide the best way to keep track of the type of the void*. Here's the interface for the nodes:

typedef struct
{
   void *data;
   struct TreeNode *left;
   struct TreeNode *right;  
} TreeNode;

However, when I write add/remove, I'll need to do comparisons, hence I'll need to keep track of the type of data that "data" is pointing to, right?

Basic idea is to have an enum Node_Type and a function compareTreeNodes that receives the two TreeNodes and the enum as a 3rd arg. This would allow the function to determine what to cast the void* to.

Any other/better thoughts?

Answer 1

I assume a single BST will have only one type of data in it. In that case I would make a encapsulating struct that contains a pointer to the root node and a pointer to a comparison function. The user of your BST would have to provide a suitable function at initialisation.

typedef struct {
    TreeNode *root;
    int (*compar)(const void *, const void *);
} Tree;

Btw, your first line should probably be typedef struct TreeNode {. You have a typdef'd anonymous struct, but refer to a non-existent tagged struct inside. These two versions would work:

typedef struct TreeNode {
    void *data;
    struct TreeNode *left, *right;
} TreeNode;

typedef struct TreeNode TreeNode;
struct TreeNode {
    void *data;
    TreeNode *left, *right;
};

You cannot make self-referential anonymous structs.

Answer 2

However, when I write add/remove, I'll need to do comparisons, hence I'll need to keep track of the type of data that "data" is pointing to, right?

Look at how qsort() solves this issue. It, too, needs to work on arbitrary data types. Basically, you delegate comparison to users, through a function pointer.