2

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.

too honest for this site
  • 12,050
  • 4
  • 30
  • 52
Tim
  • 2,708
  • 1
  • 18
  • 32
  • 2
    Is this C or C++? Your use of `struct X* member;` indicates you may want a C-only solution here. – Mark B Oct 31 '16 at 18:01
  • 1
    There is no language "C/C++". Choose one. You are using C-like code, but compiling with g++, which leaves me confused about which language you're really interested in. – John Bollinger Oct 31 '16 at 18:01
  • Where you ask about statically *defining* data structures, it seems like you may actually be asking about *initialization*. In that the case? – John Bollinger Oct 31 '16 at 18:04
  • @JohnBollinger No he wants static data instead of global, so that they are not visible in other compilation units. If he puts static, he can no longer "forward" define it as external. – Christophe Oct 31 '16 at 18:06
  • @Christophe, these are not mutually exclusive. There would be no problem with declaring everything `static` in C if default initialization were acceptable. Perhaps the story is different in C++, but the OP wants to avoid a vaguely-specified set of C++ features. – John Bollinger Oct 31 '16 at 18:10
  • @John, sorry about the imprecision. I am using g++ to get C++ semantics (so C++). I said C/C++ above because I didn't want to exclude one from the discussion (should one work and the other not). I also meant definition/initialization as whatever it takes to get the compiler/linker to build the thing in at compile time (so it's in the object file statically). – Tim Oct 31 '16 at 21:33
  • The `extern` was just a way of me compelling this to work and isn't necessary otherwise. In the real problem, the top-level array is exposed elsewhere (techincally part of an other initializer). – Tim Oct 31 '16 at 21:34

2 Answers2

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.

John Bollinger
  • 160,171
  • 8
  • 81
  • 157
  • Hmm this was the first thing I tried, but it gets rejected by gcc and g++ as well with `error: redefinition of 'Op op_subops [4]'`. – Tim Oct 31 '16 at 18:46
  • @Tim, as I said, this answer is for C, and C++ semantics may differ. – John Bollinger Oct 31 '16 at 18:47
  • I tried both C and C++ and got the same diagnostic. In any case, the world won't end if I can't perfect this. I was looking for an easy quick solution. I can always fall back to an integer index or step back and eliminate the need for this problem at some higher level. – Tim Oct 31 '16 at 18:49
  • 1
    @Tim, it compiles and runs fine for me at ideone (once I provide a dummy `main()` function), and it compiles fine for me at home, too. I'm pretty sure that if your compiler rejects it then your compiler does not conform. MSVC++, perhaps? – John Bollinger Oct 31 '16 at 18:55
  • I was using gcc/g++ 5.2.0 (Cygwin). The online tool ideone.com allowed me to test g++ 5.1 and clang 3.7. I did notice that "gcc 5.1" (C) does pass. – Tim Oct 31 '16 at 21:29
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

Christophe
  • 68,716
  • 7
  • 72
  • 138
  • Omitting the array size does not work in C. (That is, it does not solve the underlying problem with his declaration when the code is interpreted according to C's rules.) That may or may not be a problem for the OP. – John Bollinger Oct 31 '16 at 18:14
  • Idea one got rejected by g++ (see http://ideone.com/U5QuMZ): `error: storage size of 'op_subops' isn't known`. So I think this might be okay for C, but not C++. – Tim Oct 31 '16 at 18:31
  • @Tim you've selected C++5.1 as language. Look at my link with C on ideone it works. Although I have to admit that MSVC rejects it. – Christophe Oct 31 '16 at 18:34