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.
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
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.