# Implementation of tree with different node types and faux-polymorphism in C

I'm currently learning C by working on my first project. It's a calculator with a parser that transforms input into an operator tree. These trees consist of nodes of different types: Operators (inner nodes), constants and variables. My first attempt was to create a single struct node and just put everything a Node might have in it -- which wastes a lot of memory because not all of the fields are used, depending on the actual type a Node has.

My solution: I implemented three different structs for the three different Node types.

typedef enum
{
NTYPE_OPERATOR,
NTYPE_CONSTANT,
NTYPE_VARIABLE
} NodeType;

typedef NodeType* Node;

struct VariableNode_
{
NodeType type;
char var_name[];
};

struct ConstantNode_
{
NodeType type;
double const_value;
};

struct OperatorNode_
{
NodeType type;
Operator *op;
size_t num_children;
Node children[];
};


They all have a type as their first field -- a header to let me know which type a Node actually has. A Node is always a pointer to the heap, so I typedef'ed it to hide its pointer type. A node may be created and used by the following "constructors" and accessors:

Node malloc_variable_node(char *var_name)
{
VariableNode res = malloc(sizeof(struct VariableNode_) + (strlen(var_name) + 1) * sizeof(char));
if (res == NULL) return NULL;
res->type = NTYPE_VARIABLE;
strcpy(res->var_name, var_name);
return (Node)res;
}

Node malloc_constant_node(ConstantType value)
{
ConstantNode res = malloc(sizeof(struct ConstantNode_));
if (res == NULL) return NULL;
res->type = NTYPE_CONSTANT;
res->const_value = value;
return (Node)res;
}

Node malloc_operator_node(Operator *op, size_t num_children)
{
if (num_children > MAX_ARITY)
{
// Max. arity exceeded
return NULL;
}

OperatorNode res = malloc(sizeof(struct OperatorNode_) + num_children * sizeof(Node));
if (res == NULL) return NULL;

for (size_t i = 0; i < num_children; i++)
{
res->children[i] = NULL;
}

res->type = NTYPE_OPERATOR;
res->op = op;
res->num_children = num_children;
return (Node)res;
}

void free_tree(Node tree)
{
if (tree == NULL) return;
if (get_type(tree) == NTYPE_OPERATOR)
{
for (size_t i = 0; i < get_num_children(tree); i++)
{
free_tree(get_child(tree, i));
}
}
free(tree);
}

NodeType get_type(Node node)
{
return *node;
}

Operator *get_op(Node node)
{
return ((OperatorNode)node)->op;
}

size_t get_num_children(Node node)
{
return ((OperatorNode)node)->num_children;
}

Node get_child(Node node, size_t index)
{
return ((OperatorNode)node)->children[index];
}

{
return &((OperatorNode)node)->children[index];
}

void set_child(Node node, size_t index, Node child)
{
((OperatorNode)node)->children[index] = child;
}

char *get_var_name(Node node)
{
return ((VariableNode)node)->var_name;
}

double get_const_value(Node node)
{
return ((ConstantNode)node)->const_value;
}


Is this common practice? Would there be a better way to do it? Would it have been okay to just waste the space and use a single struct as I did before? This would almost always safe me a level of indirection when dealing with trees and transforming them because all Nodes would have the same size and could be recycled. If you want to look at the full file(s): node.h hosted at GitHub

Edit: Changed ConstantType to double because the type was not defined in the excerpt I posted

• You have provided a link to the source code, however, it would be better if the entire node.h file and node.c file were here for review. It might also be better if you provided enough code from other files to show how this code was used. At least one type, ConstantType lacks a definition in the code that is here. – pacmaninbw Oct 6 at 13:59
• Do you have any unit testing set up, or is the only way to test it to run the calculator? It would be better for you if you could test the parser separately from the calculator. – pacmaninbw Oct 6 at 14:02
• I have a separate parser test, which is located at github.com/PhilippHochmann/Calculator/blob/master/tests/… and is run when invoking make.sh with the flag -d – PhilippHochmann Oct 6 at 14:20
• Just a suggestion, but if you're running on Linux you might want to look into using CMake, on almost all systems (Windows, Linux, OSX) Make is supported. The value of Make over the make.sh file you have is that only source files and header files that have changed will be recompiled. Many development environments build the make file for you as you add files. – pacmaninbw Oct 6 at 14:20
• Polymorphism is an implementation-agnostic term - you don't have C++ polymorphism, but you do still have polymorphism. It's not really 'faux'. – Reinderien Oct 6 at 14:23

Is this common practice?

Enum-based type tracking in C? Yes.

Would there be a better way to do it?

Depends on a few things, including your definition of better. I think this is fine, but if your type-conditional code ends up being extremely long, then you can move to a more C++-style approach, where instead of tracking a type enum, you track function pointers; then your if (get_type()) code disappears and you can blindly call the function pointer. It's a little more complicated, and can have performance implications.

Would it have been okay to just waste the space and use a single struct as I did before?

Again - it depends. How many of these structures are you instantiating? Seven, or seven billion?

Wasting the space can actually be more performant - you can simplify your allocation logic.

There's yet another option where you don't waste space at all - C allows you to do a dirty trick called union punning. Basically, write multiple versions of the structure whose memory overlaps, and choose the right one based on context.

Until performance becomes a very specific and dominant issue, just stick with what you have, which is simple and legible, and resist the urge to prematurely optimize.

Remarks for beginners:

• Never hide a pointer behind a typedef! Never! It makes the code confusing and very hard to read and maintain.
• You can't unfortunately use a generic Node pointer like in your code, because this isn't well-defined by the language. There are ways around it, but they are a bit controversial (see advanced reply below).
• Generally, when doing any kind of polymorphism, you might want to have an "abstract base class". In this case it would have been NodeType, but it should be a struct of its own and each inherited class should contain an instance of the base class as first member. Not a pointer to it.
• Avoid calling functions in the controlling statement of a for loop like you do in for (size_t i = 0; i < get_num_children(tree); i++). This will often produce needlessly slow code. Instead call the function once before the loop, then store the result in a variable.

Remarks for veterans (beginners ignore):

One advanced trick which is supposedly fully supported by the standard (but might have diverse quality of implementation on different compilers) is the "union common initial sequence" trick.

There's a rule stating that if you expose a union containing all those structs to the same translation unit as where those structs are used, type punning between the structs is well-defined. In your case something like this:

union type_punning
{
struct VariableNode_ a;
struct ConstantNode_ b;
struct OperatorNode_ c;
};


This union just needs to sit there; you don't need to use it, or even show it to the caller. This tells the compiler that since these struct share a common initial sequence, the NodeType member, we can type pun between them and it is well-defined, as long as we only access shared members of that initial sequence.

Meaning that suddenly we can do this:

void func (struct VariableNode_* vn)
{
if(vn->type == NTYPE_CONSTANT)
{
struct ConstantNode_* cn = (struct ConstantNode_*)vn;
cn->const_value = something; // well-defined!
}
}


There's also exceptions to the strict aliasing rule allowing this use.

Source: C17 6.5.2.3

One special guarantee is made in order to simplify the use of unions: if a union contains several structures that share a common initial sequence (see below), and if the union object currently contains one of these structures, it is permitted to inspect the common initial part of any of them anywhere that a declaration of the completed type of the union is visible. Two structures share a common initial sequence if corresponding members have compatible types (and, for bit-fields, the same widths) for a sequence of one or more initial members.

• On bullet 4 in the beginner section are you say that when it is compiled -O3 the compiler won't put that value into a register or temporary variable and reuse it? Not that this would be specified by the standard. – pacmaninbw Oct 8 at 14:11
• @pacmaninbw The compiler can't do that if the function has external linkage. Some standard lib functions like strlen might be inline optimized, but custom functions most likely not. – Lundin Oct 8 at 14:19
• @pacmaninbw It depends on what the function does too, of course. It might not be feasible to inline it because it's too big. Generally the compiler is better suited than the programmer to determine what to inline (why inline is regarded as a mostly obsolete keyword). At any rate, there is never any harm with calling the function before the loop - it will make the loop slightly easier to read if nothing else. – Lundin Oct 8 at 14:26
• @PhilippHochmann It leads to muddy use. Before you know it, people will start using Node* which is actually a pointer to pointer, to avoid passing the variable by value. Or write bugs because they don't realize it is a pointer, like Node n = (Node){0}; ... return n;. So there is absolutely no point in hiding the pointer syntax to the user. If they can or can't acccess the pointed-at contents is irrelevant. – Lundin Oct 9 at 6:32
• @PhilippHochmann To cast a pointer to struct into a pointer of the type of its first element is well-defined. However, your various struct types are not compatible with each other. What I'm trying to say is that you should have a struct which acts as base class, containing the enum. Then have every other struct type declare an instance of that struct acting as base class, as its first member. This would allow you to write an API where functions take the base class pointer as parameter, but may invoke inherited class functionality. Also known as polymorphism in OO design. – Lundin Oct 9 at 6:42