Recursive macro for nested arguments

Question

I want to define a data structure at compile time using macros. The data structure looks something like:

struct {
    int a;
    int b;
    int c;
    unsigned int top;
    unsigned int first;
} array[N];

Where N is some compile time constant. User then defines a macro like so:

#define List                     \
    (10, -3, 8,                  \
        (-1, -1, 13,             \
            (0, -7, 15, Empty)), \
        (-4, 14, 13, Empty)),    \
    (17, 0, 1, Empty),           \
    (3, 3, 3,                    \
        (1, 1, 0, Empty))        \

from which the array shall be generated. The result would be:

array = {
    [0] = {10, -3, 8, NoValue, 1/*array[1]*/},
    [1] = {-1, -1, 13, 0/*array[0]*/, 2/*array[2]*/},
    [2] = {0, 7, 15, 0/*array[0]*/, NoValue},
    [3] = {-4, 14, 13, 0/*array[0]*/, NoValue},
    [4] = {17, 0, 1, NoValue, NoValue},
    [5] = {3, 3, 3, NoValue, 6/*array[6]*/},
    [6] = {1, 1, 0, 5/*array[5]*/, NoValue},
};

Where #define NoValue 9000 /* special value used only for this purpose */. Basically create entry in array for every element enclosed in (). Additionally link sub-elements to the parent-element and the parent-element to its first sub-element.

What I have so far is using FOR_EACH macro from https://stackoverflow.com/a/11994395/1806687. The problem is that the macro that would define an array entry also contains FOR_EACH macro to iterate over any possible sub-elements which breaks down and doesn't work.

How can I make this work?

EDIT:

I guess the first obstacle is recursively iterating through the tree to define an enumeral for every element (). We could add a one more argument to every element like so #define List (Name1, 10, -3, 8, ... from which we can generate an enumeration whose values we can then use in place of array indices (top and first members).

#define List                        \
(Name1, 10, -3, 8,                  \
    (Name2, -1, -1, 13,             \
        (Name3, 0, -7, 15, Empty)), \
    (Name4, -4, 14, 13, Empty)),    \
(Name5, 17, 0, 1, Empty),           \
(Name6, 3, 3, 3,                    \
    (Name7, 1, 1, 0, Empty))        \

#define EnumFromList(name, a, b, c, top, first) \
    enum_##name,

enum NameEnum {
    FOR_EACH(EnumFromList, List)
};

Still, nesting of the sub-elements prevents an easy solution (as far as I can see) to this.

EDIT2:

The actual data structure I am using looks more like:

struct {
    int a;
    int b;
    int c;
    unsigned int top;
    unsigned int parent;
    unsigned int first;
} array[N];

Where top is array index of top-parent-element parent is array index of direct(first)-parent-element and first is array index of first-sub-element.

There are no recursive macros in C. You need to unfold the recursion yourself and use two *different* macros (or whatever your desired recursion depth is). — n. m. could be an AI, Nov 24 '22 at 20:25
@HolyBlackCat 4th value is either array index of the top most element or 'NoVaue' and 5th value is either array index of the first sub-element or 'NoValue' — user1806687, Nov 25 '22 at 03:36
@n.m. What would you call this https://stackoverflow.com/questions/6707148/foreach-macro-on-macros-arguments/13459454#13459454 — user1806687, Nov 25 '22 at 03:37
@HolyBlackCat The input data is a tree because of dependencies between elements - that is top and first. Any element can contain any number of sub-elements. I dont see how this could be described with a list? — user1806687, Nov 25 '22 at 03:43
I don't quite understand the difference between top and parent. Otherwise this should be doable, I'll have a go at writing it when I have some spare time. — camel-cdr, Nov 25 '22 at 09:29
@camel-cdr top is the top-most parent index, while the parent is the direct-parent index. For example if using names instead of array indices: `top` of `Name3` would be `Name1` while its `parent` is `Name2`. — user1806687, Nov 25 '22 at 10:34
From someone who has done similar things in the past: Don't do it with preprocessor. Instead define your data in general purpose format (XML, JSON, etc.) and then use general purpose scripting language (Python, etc.) to read data file and transform it into C file. In the end it will be faster and more flexible solution and save you from headaches. — user694733, Nov 25 '22 at 10:37
@user694733 Normally I would agree. The problem with the approach however is additional dependencies, change to build system and generation of multiple files for multiple defined Lists. What is desirable and what I want is self-contained code generation. — user1806687, Nov 25 '22 at 14:40
The problem with C preprocessor approach is that is messy, unmaintanable, near impossible, causes headaches and makes you shoot yourself in a foot. Write a python script. After rethinking your question, I believe it is too big for stackoverflow. This is basically a small library to write with 1000s lines of code in C preprocessor to make it happen and multiple expansion ways. That is just too big. For recursive macros, you can just have different names of chains of macros `FOREACH1` `FOREACH2` `FOREACH3` etc. for every recursion level, that way they will not be painted blue. — KamilCuk, Nov 26 '22 at 18:58
The other is the REPEAT macro https://github.com/pfultz2/Cloak/wiki/C-Preprocessor-tricks,-tips,-and-idioms , but I do not think it's applicable here because you need to pass the context. — KamilCuk, Nov 26 '22 at 18:59
I wasn't able to do it in two attempts, having do dispatch on every top level tuple, to properly set the top variable, and keeping tack of the first successor really complicates things. My recursion schemes didn't end up working with "first". I may revisit this later. — camel-cdr, Nov 28 '22 at 20:50
@camel-cdr Thanks for trying. I've reworked the logic to work with list structure. If you're going to try it again you can ignore the `top` variable. — user1806687, Dec 04 '22 at 20:30
`0, 7, 15, 0/*array[0]*/` why -7 become 7? Shouldn't it point to array[1]? — KamilCuk, Aug 16 '23 at 13:29

KamilCuk · Accepted Answer · 2023-08-16T13:28:36.360

The following code:

#define NOVALUE  ((unsigned)-1)

#define EXPAND(...)  __VA_ARGS__
#define ADDONE(...)  +1

// -----------------------------------

#define IF_EMPTY_IN(a, ...)  a
#define IF_EMPTY(t, f, ...)  IF_EMPTY_IN(__VA_OPT__(f,) t, )


// --------------------------

#define TREE_VAL(idx, a, b, c, up, down)  \
        [idx] = {a, b, c, up, down},

// -----------------------------------

#define TREE_L4_NEXT(...)
#define TREE_L4_VAL_IN(f, idx, up, a, b, c, ...)  \
        f(idx, a, b, c, up, IF_EMPTY(NOVALUE, idx+1 __VA_OPT__(,) __VA_ARGS__)) \
        TREE_L4_NEXT(f, idx+1, idx __VA_OPT__(,) __VA_ARGS__)
#define TREE_L4_VAL(...)  \
        TREE_L4_VAL_IN(__VA_ARGS__)
#define TREE_L4_0(f, idx, up, a)
#define TREE_L4_1(f, idx, up, a)  \
        TREE_L4_VAL(f, idx, up, EXPAND a)
#define TREE_L4_2(f, idx, up, a, ...)  \
        TREE_L4_1(f, idx, up, a) \
        TREE_L4_1(f, idx TREE_L4_NEXT(ADDONE,,,a), up, __VA_ARGS__)
#define TREE_L4_3(f, idx, up, a, ...)  \
        TREE_L4_1(f, idx, up, a) \
        TREE_L4_2(f, idx TREE_L4_NEXT(ADDONE,,,a), up, __VA_ARGS__)
#define TREE_L4_N(_3,_2,_1,_0,N,...)  \
        TREE_L4##N
#define TREE_L4(f, idx, up, ...)  \
        TREE_L4_N(__VA_OPT__(,) __VA_ARGS__,_3,_2,_1,_0)(f, idx, up, __VA_ARGS__)

#define TREE_L3_NEXT(...)  TREE_L4(__VA_ARGS__)
#define TREE_L3_VAL_IN(f, idx, up, a, b, c, ...)  \
        f(idx, a, b, c, up, IF_EMPTY(NOVALUE, idx+1 __VA_OPT__(,) __VA_ARGS__)) \
        TREE_L3_NEXT(f, idx+1, idx __VA_OPT__(,) __VA_ARGS__)
#define TREE_L3_VAL(...)  \
        TREE_L3_VAL_IN(__VA_ARGS__)
#define TREE_L3_0(f, idx, up, a)
#define TREE_L3_1(f, idx, up, a)  \
        TREE_L3_VAL(f, idx, up, EXPAND a)
#define TREE_L3_2(f, idx, up, a, ...)  \
        TREE_L3_1(f, idx, up, a) \
        TREE_L3_1(f, idx TREE_L3_NEXT(ADDONE,,,a), up, __VA_ARGS__)
#define TREE_L3_3(f, idx, up, a, ...)  \
        TREE_L3_1(f, idx, up, a) \
        TREE_L3_2(f, idx TREE_L3_NEXT(ADDONE,,,a), up, __VA_ARGS__)
#define TREE_L3_N(_3,_2,_1,_0,N,...)  \
        TREE_L3##N
#define TREE_L3(f, idx, up, ...)  \
        TREE_L3_N(__VA_OPT__(,) __VA_ARGS__,_3,_2,_1,_0)(f, idx, up, __VA_ARGS__)

#define TREE_L2_NEXT(...)  TREE_L3(__VA_ARGS__)
#define TREE_L2_VAL_IN(f, idx, up, a, b, c, ...)  \
        f(idx, a, b, c, up, IF_EMPTY(NOVALUE, idx+1 __VA_OPT__(,) __VA_ARGS__)) \
        TREE_L2_NEXT(f, idx+1, idx __VA_OPT__(,) __VA_ARGS__)
#define TREE_L2_VAL(...)  \
        TREE_L2_VAL_IN(__VA_ARGS__)
#define TREE_L2_0(f, idx, up, a)
#define TREE_L2_1(f, idx, up, a)  \
        TREE_L2_VAL(f, idx, up, EXPAND a)
#define TREE_L2_2(f, idx, up, a, ...)  \
        TREE_L2_1(f, idx, up, a) \
        TREE_L2_1(f, idx TREE_L2_NEXT(ADDONE,,,a), up, __VA_ARGS__)
#define TREE_L2_3(f, idx, up, a, ...)  \
        TREE_L2_1(f, idx, up, a) \
        TREE_L2_2(f, idx TREE_L2_NEXT(ADDONE,,,a), up, __VA_ARGS__)
#define TREE_L2_N(_3,_2,_1,_0,N,...)  \
        TREE_L2##N
#define TREE_L2(f, idx, up, ...)  \
        TREE_L2_N(__VA_OPT__(,) __VA_ARGS__,_3,_2,_1,_0)(f, idx, up, __VA_ARGS__)

#define TREE_L1_NEXT(...)  TREE_L2(__VA_ARGS__)
#define TREE_L1_VAL_IN(f, idx, up, a, b, c, ...)  \
        f(idx, a, b, c, up, IF_EMPTY(NOVALUE, idx+1 __VA_OPT__(,) __VA_ARGS__)) \
        TREE_L1_NEXT(f, idx+1, idx __VA_OPT__(,) __VA_ARGS__)
#define TREE_L1_VAL(...)  \
        TREE_L1_VAL_IN(__VA_ARGS__)
#define TREE_L1_0(f, idx, up, a)
#define TREE_L1_1(f, idx, up, a)  \
        TREE_L1_VAL(f, idx, up, EXPAND a)
#define TREE_L1_2(f, idx, up, a, ...)  \
        TREE_L1_1(f, idx, up, a) \
        TREE_L1_1(f, idx TREE_L1_NEXT(ADDONE,,,a), up, __VA_ARGS__)
#define TREE_L1_3(f, idx, up, a, ...)  \
        TREE_L1_1(f, idx, up, a) \
        TREE_L1_2(f, idx TREE_L1_NEXT(ADDONE,,,a), up, __VA_ARGS__)
#define TREE_L1_N(_3,_2,_1,_0,N,...)  \
        TREE_L1##N
#define TREE_L1(f, idx, up, ...)  \
        TREE_L1_N(__VA_OPT__(,) __VA_ARGS__,_3,_2,_1,_0)(f, idx, up, __VA_ARGS__)

// -----------------------------------

#define TREE_SIZE(...)  0 TREE_L1(ADDONE, 0, NOVALUE, __VA_ARGS__)
#define TREE(...)       TREE_L1(TREE_VAL, 0, NOVALUE, __VA_ARGS__)

// -----------------------------------

#include <stdio.h>
#include <string.h>

struct array_s {
    int a;
    int b;
    int c;
    unsigned int top;
    unsigned int first;
};

#define LIST                     \
    (10, -3, 8,                  \
        (-1, -1, 13,             \
            (0, -7, 15)), \
        (-4, 14, 13)),    \
    (17, 0, 1),           \
    (3, 3, 3,                    \
        (1, 1, 0))         \
    /* */

static const struct array_s array[] = { TREE(LIST) };

static const char *snovalue(char *buf, unsigned v) {
    if (v == NOVALUE) {
        strcpy(buf, "NoValue");
    } else {
        sprintf(buf, "%u", v);
    }
    return buf;
}
#define SNOVALUE(v) snovalue((char[200]){0}, v)
int main() {
    for (int i = 0; i < sizeof(array)/sizeof(*array); ++i) {
        const struct array_s *const e = &array[i];
        printf("[%d]={%2d,%2d,%2d,%10s,%10s},\n",
            i, e->a, e->b, e->c, SNOVALUE(e->top), SNOVALUE(e->first));
    }
}

Outputs the content of array[] generated from TREE(LIST) as:

[0]={10,-3, 8,   NoValue,         1},
[1]={-1,-1,13,         0,         2},
[2]={ 0,-7,15,         1,   NoValue},
[3]={-4,14,13,         0,   NoValue},
[4]={17, 0, 1,   NoValue,   NoValue},
[5]={ 3, 3, 3,   NoValue,         6},
[6]={ 1, 1, 0,         5,   NoValue},

I removed EMPTY, I see no value in it. EMPTY, is just nothing, do not pass an argument. Then the macros can detect the number of arguments, and zero arguments, with the help of __VA_OPT__.

I have written the TREE_L* macros so that it is easy to generate them. You can just write a simple loop to generate a lot of them, and the last just has to have TREE_L*_NEXT empty.

On each tree level, calculating the next index has been a challenge. A separate temporary tree is traversed in idx TREE_L*_NEXT(ADDONE in each branch to calculate the current "depth" of the tree to get the index.

The code works like this: on each level, overload on number arguments. For each argument, output an [idx] = {stuff}, and then, if there are children, repeat the overload with incremented "up" index. Each level knows the "up" - the index of the upper level tree. On each traversing level, the TREE_L<num> is incremented because "used up" macros are painted blue by the preprocessor. All in all, this is a recursive algorithm.

Recursive macro for nested arguments

1 Answers1