Difference between using a structure member and cast a structure pointer when "emulate" polymorphism in C

Question

I'm not sure if my wording is technically correct, so please correct me in both title and the main body of this question.

So basically my question is regarding emulating polymorphism in C. For example, suppose I have a tree, and there is a struct tree_node type. And I have some functions to help me insert nodes, delete nodes etc like this as an example:

void tree_insert(tree_node **root, tree_node *new_node);

Then I start to build other stuff for my app, and and need to use this tree to maintain, say, family members. But for human, I have another struct, let's call it "struct human_node" which is defined like this, for example:

typedef struct human_node_ {
    tree_node t_node;
    char *name;
} human_node;

Now apparently I want to use those tree utility functions I build for the generic tree. But they take tree_node pointers. Now time for the polymorphism emulation. So here are the two options I have, one is to cast my human_node, one is to use the t_node member in the human_node:

human_node *myfamily_tree_root, *new_family_guy;
//some initialization code and other code later...
tree_insert((tree_node **)&myfamily_tree_root, &(new_family_guy->t_node));

For concise I put both ways in one function call above.

And this is exactly where I have my confusion. So which one should I use and more importantly, why?

Answer 1

Both are standard, but in general if you can avoid type casts then you should pick the solution that avoids the type casts.

A common thing for such inline data structure implementations is to not even require that the tree node (or equivalent) is the first element in the struct since you might want to enter your nodes into multiple trees. Then you definitely want to use the second approach. To convert between the tree_node element and the struct containing you'll have to have some black magic macros, but it's worth it. For example in an implementation of avl trees I have these macros:

#ifndef offsetof
#define offsetof(s, e) ((size_t)&((s *)0)->e)
#endif

/* the bit at the end is to prevent mistakes where n is not an avl_node */
#define avl_data(n, type, field) ((type *)(void*)((char *)n - offsetof(type, field) - (n - (struct avl_node *)n)))

So I can have something like:

struct foo {
    int data;
    struct avl_node tree_node_1;
    struct avl_node tree_node_2;
};

int
tree_node_1_to_data(struct avl_node *x)
{
     return avl_data(x, struct foo, tree_node_1)->data;
}

If you choose to make your code this generic you definitely want to take references to your tree_node members and not typecast the pointer to the struct.

Answer 2

This question is probably too broad for any specific answers, but you could for instance see how CPython does it.

Basically, all Python structs have the same header, and to define your own types you must be sure to start your struct with the PyObject_HEAD macro (or PyObject_VAR_HEAD for variably sized objects like strings). This adds stuff like a type tag, reference counts, and so on.

After instantiating objects, you pass them around as PyObject*s, and the functions will infer what type the object actually is (e.g. a string, a list, etc.) and be able to dispatch based on that. Yes, you have to type cast at some point to get to your actual object contents.

For instance, this is how Python's character strings are defined:

typedef struct {
    PyObject_VAR_HEAD
    Py_hash_t ob_shash;
    char ob_sval[1];

    /* Invariants:
     *     ob_sval contains space for 'ob_size+1' elements.
     *     ob_sval[ob_size] == 0.
     *     ob_shash is the hash of the string or -1 if not computed yet.
     */
} PyBytesObject;

You can read more about the CPython's type object inheritance model. Extract:

Objects are always accessed through pointers of the type 'PyObject *'. The type 'PyObject' is a structure that only contains the reference count and the type pointer. The actual memory allocated for an object contains other data that can only be accessed after casting the pointer to a pointer to a longer structure type.

Note that this angle of attack may be more suited for interpreted code. There are probably other open source projects you may look at that are more directly relevant to your needs.