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!<\/p>\n
#define TOP 0\r\n#define SET_CHILD(n,parent) ( parent==TOP ? n: \\\r\n ( parent<(1<<4) ? (n<<4) + parent : \\\r\n ( parent<(1<<8) ? (n<<8) + parent : (n<<12)+parent)))\r\n\r\n#define IS_SUBNODE(child, parent) ((child & parent) == parent)\r\n\r\n#define SELECT(X, a, best) ( a > best && IS_SUBNODE(X, a)? a : best)\r\n\r\n#define SELECT_FROM_5(X, a, b, c, d, e) SELECT(X, a, \\\r\n SELECT(X, b, \\\r\n SELECT(X, c, \\\r\n SELECT(X, d, \\\r\n SELECT(X, e, 0)))))\r\n\r\n#define SELECT_FROM_4(X, a, b, c, d) SELECT_FROM_5(X, a, b, c, d, 0)\r\n#define SELECT_FROM_3(X, a, b, c)\u00a0\u00a0\u00a0 SELECT_FROM_5(X, a, b, c, 0, 0)\r\n#define SELECT_FROM_2(X, a, b)\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0 SELECT_FROM_5(X, a, b, 0, 0, 0)<\/pre>\nThe `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.<\/p>\n
`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:<\/p>\n
#define A SET_CHILD(1, TOP)\r\n#define B SET_CHILD(2, TOP)\r\n...\r\n#define A1 SET_CHILD(1, A)\r\n#define A2 SET_CHILD(2, A)\r\n...\r\n#define B1 SET_CHILD(1, B)\r\n#define B2 SET_CHILD(2, B)\r\n...\r\n#define A11 SET_CHILD(1, A1)\r\n#define A12 SET_CHILD(2, A1)\r\n...\r\n#define A21 SET_CHILD(1, A2)\r\n#define A22 SET_CHILD(2, A2)\r\n...<\/pre>\nBy 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.<\/p>\n
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.<\/p>\n
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.<\/p>\n
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<\/em> of `X` among the nodes `a`, …`c` will be returned. If none of them is a parent of `X` the return value is `TOP`.<\/p>\nExample:<\/strong><\/p>\nIf we set<\/p>\n
#define X A22<\/pre>\nthen we get<\/p>\n
SELECT_FROM_2(X, A, B) \/\/ = A\r\nSELECT_FROM_3(X, A, B, A1) \/\/ = A\r\nSELECT_FROM_3(X, A, B, A2) \/\/ = A2\r\nSELECT_FROM_3(X, A2, B, A) \/\/ = A2\r\nSELECT_FROM_3(X, A2, A, A22) \/\/ = A2\r\nSELECT_FROM_2(X, A1, B) \/\/ = TOP<\/pre>\nInheritance<\/h3>\n
With the definitions above we can influence conditional compilation:<\/p>\n
#if SELECT_FROM_3(X,A2,A,B) == A2\r\n const int a = 0;\r\n#else if SELECT_FROM_3(X,A2,A,B) == A\r\n const int a = 1;\r\n#else if SELECT_FROM_3(X,A2,A,B) == B\r\n const int a = 2;\r\n#else\r\n const int a = -1;\r\n#endif<\/pre>\nThe 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.<\/p>\n
#define X A225<\/pre>\nSo 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.<\/p>\n","protected":false},"excerpt":{"rendered":"
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 … Continue reading