Inheritance and the C preprocessor

Defining n-ary trees using the C preprocessor

In this article I introduce a compile time C technique used to define inheritance. Instead of giving a lengthy motivation I’ll jump directly to the algorithm and discuss it later. I hope lovers of C and its preprocessor find it useful. #defines first!

#define TOP 0
#define SET_CHILD(n,parent) ( parent==TOP ? n: \
                            ( parent<(1<<4) ? (n<<4) + parent : \
                            ( parent<(1<<8) ? (n<<8) + parent : (n<<12)+parent)))
 
#define IS_SUBNODE(child, parent) ((child & parent) == parent)
 
#define SELECT(X, a, best) ( a > best && IS_SUBNODE(X, a)? a : best)
 
#define SELECT_FROM_5(X, a, b, c, d, e) SELECT(X, a, \
                                        SELECT(X, b, \
                                        SELECT(X, c, \
                                        SELECT(X, d, \
                                        SELECT(X, e, 0)))))
 
#define SELECT_FROM_4(X, a, b, c, d) SELECT_FROM_5(X, a, b, c, d, 0)
#define SELECT_FROM_3(X, a, b, c)    SELECT_FROM_5(X, a, b, c, 0, 0)
#define SELECT_FROM_2(X, a, b)       SELECT_FROM_5(X, a, b, 0, 0, 0)

The `SET_CHILD` macro is used to define up to 15 child nodes of a given root for a n-ary tree of depth 5 with a single root node, named `TOP`. This is encoded within a single number of type `word` which is adequate for most embedded compilers. For 32 or 64 bit processors one can either support more child nodes or a deeper tree.

`SET_CHILD` is assigning a name to n-th child of a given `parent`. One starts with `TOP` as the parent of all nodes and recurses down:

#define A SET_CHILD(1, TOP)
#define B SET_CHILD(2, TOP)
...
#define A1 SET_CHILD(1, A)
#define A2 SET_CHILD(2, A)
...
#define B1 SET_CHILD(1, B)
#define B2 SET_CHILD(2, B)
...
#define A11 SET_CHILD(1, A1)
#define A12 SET_CHILD(2, A1)
...
#define A21 SET_CHILD(1, A2)
#define A22 SET_CHILD(2, A2)
...

By construction no more than 15 child nodes for a given parent are permitted. If more are used, macros like `IS_CHILD` will fail to work correctly.

Once a tree is created with the appropriate nodes, one can use `IS_CHILD` to check for child/parent relationships. The tree is constructed s.t. `IS_CHILD(A, B)` returns 1 iff `A` is a direct child of `B` or a grandchild of `B` etc. otherwise 0. So `IS_CHILD(A22, A)` evaluates to 1 just like `IS_CHILD(A22, A2) ` or `IS_CHILD(A22, TOP)` but `IS_CHILD(A22, A1)` is 0.

The C preprocessor doesn’t support overloading and the flavors I checked didn’t support varargs wich wouldn’t probably be much helpful in this case either. So I defined a group of 5 `SELECT_FROM_xx` macros being distinguished only be the number of arguments. The number 5 isn’t magic and one can extend the range of `SELECT_FROM_xx` macros by need.

How is `SELECT_FROM_xx` used? The first argument `X` is an arbitary node of the tree. If one of the susequent nodes `a`, `b`, … `c` is identical with `X`, `X` will be the value of `SELECT_FROM_xx(X, a, b, …, c)`. Otherwise the most-direct-parent of `X` among the nodes `a`, …`c` will be returned. If none of them is a parent of `X` the return value is `TOP`.

Example:

If we set

#define X A22

then we get

SELECT_FROM_2(X, A, B)        // = A
SELECT_FROM_3(X, A, B, A1)    // = A
SELECT_FROM_3(X, A, B, A2)    // = A2
SELECT_FROM_3(X, A2, B, A)    // = A2
SELECT_FROM_3(X, A2, A, A22)  // = A2
SELECT_FROM_2(X, A1, B)       // = TOP

Inheritance

With the definitions above we can influence conditional compilation:

#if SELECT_FROM_3(X,A2,A,B) == A2
        const int a = 0;
#else if SELECT_FROM_3(X,A2,A,B) == A
        const int a = 1;
#else if SELECT_FROM_3(X,A2,A,B) == B
        const int a = 2;
#else
        const int a = -1;
#endif

The virtue of the construction lies in its robustness. Suppose X is `A22` then the first branch is selected but this remains true also if we build a “subclass” `A22k , k = 1, …, 9, A, …, F` of `A22` and assign e.g.

#define X A225

So if we use conditional compilation for a given System `S` and create a subsystem `T` of `S` e.g. a new version of `S`, we have to adapt our C code only in places where `T` differs explicitely from `S`. This robustness is also the major virtue of using inheritance / polymorphism in OOP. It has led to disrespect of using case-statements in OOP since those do not exploit polymorphism and cause in turn less robust code. We see that case- or if-else statements can be confined with the very same idea and robustness even on the level of the C preprocessor. The additional charme of using the C preprocessor is that child/parent relationships are computed at compile time and do not cause any runtime performance penalty.