Can C syntax define a self-contained, statically allocated, totally const data structure with backward and forward references (pointers)?

Question

Question

I need to define a data structure with these constraints:

in C (C99 okay)
one structure (struct) instance containing a number of structure instances containing pointers to other structure instances (a graph structure, but conceptually a doubly linked list is enough to illustrate the point)
the whole structure must be statically allocated at compile time (not address in memory, that would be linking, but full memory layout of the whole structure including pointers)
all fields are declared constant (including pointers)
some references are forward, some backwards. IOW, when parsing the declaration, some pointers refer to fields that have not yet been parsed (but since the structure is known by the compiler, the layout in memory is already known).
portability, standard-compliance a big plus.

Search before you post

I did it, but since I hesitated and found no easy reference, this question serves to help my future self and all others who need the same.

Metaphor

Fun fact: to obey all these constraints feels like folding a cardboard box top: once it's done it fits tightly, but it has to fit all the parts or it does not work.

( picture credits https://www.youtube.com/watch?v=H5oOBLSJzGM )

score 3 · Answer 1 · answered Oct 31 '17 at 14:22

3

C syntax does allow this.

#include <stdio.h>

// Let's say everything is const, so far, so good.
typedef struct node_t
{
        const int field;
        const struct node_t *const previous;
        const struct node_t *const next;
} node_t;

// Even simpler here. Const also.
typedef struct graph_t
{
        const struct node_t node1;
        const struct node_t node2;
        const struct node_t node3;
} graph_t;

// Where all falls into place.
// The .node* labels are not necessary but may be useful for clarity.
// The trick is to use the variable graph being defined.
const graph_t graph =
{
        .node1 =  {1, &graph.node3, &graph.node2},
        .node2 =  {2, &graph.node1, &graph.node3},
        .node3 =  {3, &graph.node2, &graph.node1},
};

int main(int argc, char **argv)
{
        (void)argc;
        (void)argv;
        printf("Value %d\n", graph.node2.field);
        return 42;
}

Compilation

gcc -Wall -W -pedantic a.c  && ./a.out
Value 2

No warning.

Same result with sdcc.

Benefits

The whole struct and instances being const lands in code section, which is nice in constrained systems.

answered Oct 31 '17 at 14:22

Stéphane Gourichon

6,493
4
37
48

1

Since `graph` is declared `const`, you can remove `const` qualifier from `node1`, `node2`, `node3` and `field`. You can also declare `previous` and `next` without the first `const` qualifier like `const struct node_t *`. – user694733 Nov 02 '17 at 11:23
@user694733 the first part, (removing `const` from field declarations) looks true. The benefit is to allow defining a struct where in general you can write, yet you cannot write the particular `graph` instance. The last part seems different. – Stéphane Gourichon Nov 02 '17 at 14:59
True also for your second part, when doing precisely like you wrote (removing `const` between `*` and `previous`). Removing the other `const` yields a rightful warning because then `node_t` does not promise not to change struct which *is* const because part of `const graph_t graph`. Subtle but consistent. Thanks @user694733. – Stéphane Gourichon Nov 02 '17 at 15:12
Here's another take showing two variants: where overall construct is an array then a struct: https://gist.github.com/fidergo-stephane-gourichon/792c194e1b051a70995c27b5af8df92d – Stéphane Gourichon Jul 02 '23 at 19:50

score 1 · Answer 2 · answered Nov 02 '17 at 11:01

1

I had a similar problem some time ago, but with a tree instead of a graph. I used your self-provided solution, but I had a mess with node identifiers and so on, so I was provided with a nice solution to make preprocessor handle them (X-macros). I share the response I was provided with so anyone can use it:

https://stackoverflow.com/a/22745618/3473433

answered Nov 02 '17 at 11:01

eugenioperez

627
7
15

Interesting variant there. Basically, my solution uses a container struct and requires to name at least the members that need reference to them. Yet no IDs are keps after compile time (I don't want them, wouldn't need them). @luserdroog's answer allows to refer to other members by the IDs you already introduced and use. Nice of of X-Macro, too. – Stéphane Gourichon Nov 02 '17 at 15:30