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.