C/C++ statically defined circular data forward definition for array

Question

I am looking for the best know method for statically defining C/C++ data structures which need to be circularly linked. E.g. a tree where child and parent both need pointers to each other.

extern struct Op op_subops[4]; // fwd ref to children of ops

struct Op
{
    const char *name;
    struct Op  *parent;
    struct Op  *children;
};


struct Op ops[128] = {
    {"op",0,&op_subops[0]}
};

struct Op op_subops[4] = {
    {"subop1",&ops[1],0},
    {"subop2",&ops[1],0}
};

The above compiles (g++ 5.2). The extern keyword seems to permit me to create a forward reference from ops into ops_subops, and the other direction works out naturally since ops precedes ops_subops.

The thing I don't like is that, I'd prefer both arrays to be static (not create a publicly visible symbol in the object file).

I could use an integer index for one of the directions, but that seems a little hokey, and I'd rather just have the linker resolve the address for me.

Anyone have a magic keyword to make this work?

Thanks!

EDIT: I need to avoid things like C++ static constructors and bleeding-edge C++17 extensions (sadly). And my approach needs to platform independent.

Answer 1

As you're looking for declaring your arrays as static and can't accept them remaining global, I assume that your intention is to have both arrays remain inaccessible from the outside world.

Idea 1: just (forward-)declare the static array:

I first thought this would be the solution for the forward delclaration. This compiled well with gcc for a C file: online demo 1. But unfortunatemy it doesn't compile neither on MSVC nor on C++ because it's not standard:

    static struct Op op_subops[];  // compiler dependent - it's standard!

In reality it's simpler: just declare the array with its dimension:

    static struct Op op_subops[4]; // as simple as that

Online demo 2

The subsequent initialization doesn't define/redefine the array; it designates the already declared array to be initialized. In fact you could leave the array dimension out from the initialization. And this time it compiles on gcc and on MSVC:

    static struct Op op_subops[] = {  // [] or [4]
         ...
    };

Idea 2: put both arrays in an unnamed namespace (C++ only)

Then you no longer have to decare the items as static: the unnamed namespace ensures that other compilation units can't refer to these objects

Answer 2

In either C or C++, the bottom line is that you cannot refer to an object before you declare it, but both languages allow you to write "forward declarations" that declare the name and (possibly-incomplete) type without defining the object. Being more familiar with C, I'll answer from that perspective; some of the semantics may differ in C++.

In C, the main problem with the code you've presented is that it runs afoul of the requirement that for arrays

The element type shall be complete whenever the array type is specified.

(C2011, 6.2.5/20)

That means that although you can forward-declare array op_subops without a size (leaving its type incomplete in that sense), you cannot issue any declaration for it before type struct Op is defined. That can be solved just by swapping the positions of the two declarations.

Having corrected the ordering problem, it's perfectly fine in C to declare both arrays with static linkage; you simply have to be sure that if any object is declared more than once (i.e. op_subops) that all declarations agree about its linkage:

struct Op
{
    const char *name;
    struct Op  *parent;
    struct Op  *children;
};

static struct Op op_subops[4]; // fwd ref to children of ops

static struct Op ops[128] = {
    {"op",0,&op_subops[0]}
};

static struct Op op_subops[4] = {
    {"subop1",&ops[0],0},
    {"subop2",&ops[1],0}
};

You can omit the length of op_subop from its first declaration if you wish, and in fact I would recommend that you do so to avoid having to keep the length consistent in the two declarations.

Although you ask for the "best [known] method", that would be a question of opinion, as colored by context, and opinion questions are off-topic here. On the other hand, you seem to require an array for the children in this case, so I don't see what other alternatives there could be without changing types.