Statically declare a constant linked list

[pozz]

I want to declare a constant linked list in static way, through
initializers.

First I declare the struct, with a member that points to the same
struct (the next element in the list):
---
typedef struct LIST_s LIST;
struct LIST_s {
const int num;
const LIST *next;
};
---
Then I just declare all the elements, so I'll be able to use their
pointers later during definitions:
---
const LIST l1;
const LIST l2;
const LIST l3;
const LIST l4;
---
At last I define the elements:
---
const LIST l1 = { 1, &l2 };
const LIST l2 = { 1, &l3 };
const LIST l3 = { 2, &l4 };
const LIST l4 = { 3, NULL };
---

It seems work well, but there is a compiler warning for each
declaration of lx variable:
`const' symbol `l1' has no initializer
The only solution I found is to use the 'extern' keywork for those
variables, but I don't think this is a good solution. Indeed I know
'extern' is used to declare a variable defined in a different module,
but I have a single module for the list.

Consider that the example is very simple (it is a constant list of
integers that could be transformed in a constant array), but my real
struct has several members.

 

[Eric Sosman]

I want to declare a constant linked list in static way, through
initializers.

First I declare the struct, with a member that points to the same
struct (the next element in the list):
---
typedef struct LIST_s LIST;
struct LIST_s {
const int num;
const LIST *next;
};
---
Then I just declare all the elements, so I'll be able to use their
pointers later during definitions:
---
const LIST l1;
const LIST l2;
const LIST l3;
const LIST l4;
---
At last I define the elements:
---
const LIST l1 = { 1,&l2 };
const LIST l2 = { 1,&l3 };
const LIST l3 = { 2,&l4 };
const LIST l4 = { 3, NULL };
---

It seems work well, but there is a compiler warning for each
declaration of lx variable:
`const' symbol `l1' has no initializer
The only solution I found is to use the 'extern' keywork for those
variables, but I don't think this is a good solution. Indeed I know
'extern' is used to declare a variable defined in a different module,
but I have a single module for the list.

Define the nodes in tail-to-head order:

const LIST l4 = { 3, NULL };
const LIST l3 = { 2, &l4 };
const LIST l2 = { 1, &l3 };
const LIST l1 = { 1, &l2 };

You might also want to put `static' on l4,l3,l2 to avoid exporting
their names -- the only "legitimate" way to reach these nodes is by
following the list's links, so preventing shortcuts might be desirable.
(I can't think of a way to prevent shortcutting within the module. You
could follow the above with three macros like `#define l2 <>BAD<>' to
make shortcutting more difficult, but #undef would evade your defenses.)

The usual caveat applies: A compiler can emit any diagnostic
messages it feels like, even for perfectly valid code, so there is
no 100% sure way to avoid all warnings all of the time.

 

[James Kuyper]

....
Define the nodes in tail-to-head order:

const LIST l4 = { 3, NULL };
const LIST l3 = { 2, &l4 };
const LIST l2 = { 1, &l3 };
const LIST l1 = { 1, &l2 };

You might also want to put `static' on l4,l3,l2 to avoid exporting
their names -- the only "legitimate" way to reach these nodes is by
following the list's links, so preventing shortcuts might be desirable.
(I can't think of a way to prevent shortcutting within the module.

Make it a stand-alone module, for the sole purpose of defining the list.
As a matter of policy, define functions using the list only in other
modules. The protection provided by this approach is, of course, only as
good as your enforcement of that policy. However, if you're talking
about protecting against someone who has permission to modify the file
in which the list is defined, it's not really possible to provide any
better protection than that.

 

[James Kuyper]

Il 07/11/2011 13:23, Eric Sosman ha scritto:

What is the reason I don't explain better my problem? I thought the
linked list was a simple but good example. Mea culpa :-(

You're right, for a linked list this could be a solution to avoid
warnings from compiler.

In my real problem, I don't have a simple linked list, but a data graph
similar to a tree (it is a menu tree with items that bring to another
sub-menu).

Each node has an array of pointers to other sub-nodes and a single
pointer to the parent node. In this case, several loops are present and
it's impossible to use your approach (N1 points to N2 and N2 points to N1).

For that kind of problem you need to make use of a rather obscure
feature of C called a tentative definition (6.9.2p2). It allows mutually
referential const objects the same way that forward declaration of
functions allow mutually recursive functions:

const circlist l1; // tentative definition
static const circlist l3 = { 3, &l1};
static const circlist l2 = { 2, &l3};
const circlist l1 = { 1, &l2}; // Actual definition

What do you mean with "shortcuts"? I can't follow your thoughts.

By a "shortcut" he means accessing an element of the list directly by
name (such as l3), rather than reaching it by iteratively following the
'next' pointers start from l1.

 

[James Kuyper]

Il 07/11/2011 15:02, James Kuyper ha scritto:

Yes, this is my first approach (see my OP). The question was how to
avoid the warning.

Sorry - I didn't pay close enough attention to your original message,
since someone else had already provided a reasonable answer before I got
around to reading it.

This is perfectly legitimate use of a tentative definition. If the
compiler chooses to warn about it, there's not much you can do but find
the compiler option, if any, to turn off that warning.

 

[BartC]

This is perfectly legitimate use of a tentative definition. If the
compiler chooses to warn about it, there's not much you can do but find
the compiler option, if any, to turn off that warning.

If the warning is turned off, then it will not warn you where you really
have forgotten a definition.

In the OP's code, the names *are* defined later on, so why is the compiler
warning? Doesn't it know about 6.9.2p2?

 

[Thad Smith]

If the warning is turned off, then it will not warn you where you really have
forgotten a definition.

Some compilers will let you switch warning off and on with pragmas. Rather than
use that ugly solution, the OP might turn it off only for a small module with
those definitions. Neither solution is ideal.

In the OP's code, the names *are* defined later on, so why is the compiler
warning? Doesn't it know about 6.9.2p2?

I suspect that the compiler writer was simply being lazy since const tentative
definitions are rarely used and it was easier to warn on encountering the
initial declaration, rather than a when all declarations have been processed.

Thad

 

[Ark]

I want to declare a constant linked list in static way, through
initializers.

First I declare the struct, with a member that points to the same
struct (the next element in the list):
---
typedef struct LIST_s LIST;
struct LIST_s {
const int num;
const LIST *next;
};
---
Then I just declare all the elements, so I'll be able to use their
pointers later during definitions:
---
const LIST l1;
const LIST l2;
const LIST l3;
const LIST l4;
---
At last I define the elements:
---
const LIST l1 = { 1,&l2 };
const LIST l2 = { 1,&l3 };
const LIST l3 = { 2,&l4 };
const LIST l4 = { 3, NULL };
---

It seems work well, but there is a compiler warning for each
declaration of lx variable:
`const' symbol `l1' has no initializer
The only solution I found is to use the 'extern' keywork for those
variables, but I don't think this is a good solution. Indeed I know
'extern' is used to declare a variable defined in a different module,
but I have a single module for the list.

Consider that the example is very simple (it is a constant list of
integers that could be transformed in a constant array), but my real
struct has several members.

If memory serves me right, your clauses like
const LIST l1;
are not declarations; they are "tentative definitions". This is
perfectly fine C; it would be an error if l1 would have not been
initialized by the end of the translation unit. This stuff is seldom
used (and banished from C++) so compiler may think it's a good thing to
issue a warning.
Not sure it's a battle worth winning - or fighting.
OTOH, you may get around with an array of structs and reference other
structs by array index.

 

[Quentin Carbonneaux]

I want to declare a constant linked list in static way, through
initializers.

First I declare the struct, with a member that points to the same
struct (the next element in the list):
---
typedef struct LIST_s LIST;
struct LIST_s {
const int num;
const LIST *next;
};
---
Then I just declare all the elements, so I'll be able to use their
pointers later during definitions:
---
const LIST l1;
const LIST l2;
const LIST l3;
const LIST l4;
---
At last I define the elements:
---
const LIST l1 = { 1, &l2 };
const LIST l2 = { 1, &l3 };
const LIST l3 = { 2, &l4 };
const LIST l4 = { 3, NULL };
---

It seems work well, but there is a compiler warning for each
declaration of lx variable:
`const' symbol `l1' has no initializer
The only solution I found is to use the 'extern' keywork for those
variables, but I don't think this is a good solution. Indeed I know
'extern' is used to declare a variable defined in a different module,
but I have a single module for the list.

Using 'extern' is perfectly legal in this case. It is not a hack, and
extern is not related to "modules" which are not defined in the
standard. 'extern' is related to the "linkage" of identifiers as
specified in 6.2.2.

The program which results from adding 'extern' to the first four
declarators is strictly equivalent to your program by 6.2.2p5. If it
avoids these spurious warnings, you can add them.

However, as said before, there should be another way to placate your
compiler's warning...

 

[Tim Rentsch]

I want to declare a constant linked list in static way, through
initializers.

First I declare the struct, with a member that points to the same
struct (the next element in the list):
---
typedef struct LIST_s LIST;
struct LIST_s {
const int num;
const LIST *next;
};

You can define all the nodes in a list at once in an array:

typedef struct LIST_S List;
struct LIST_S {
const int n;
const List *next;
};

static List list_nodes[] = {
{ 1, list_nodes+1 },
{ 2, list_nodes+2 },
{ 3, list_nodes+3 },
{ 4, 0 },
};

List *head = list_nodes;

If you want to use symbolic names rather than raw integers,
that can be done using designated initializers:

enum { A = 0, B = 3, C = 2, D = 1 };

static List ln2[] = {
[A] = { 1, ln2+B },
= { 2, ln2+C },
[C] = { 3, ln2+D },
[D] = { 4, 0 },
};

The same approach works for trees or more elaborate linked
structures, including graphs with cycles, as long as all
the nodes have the same type (which could be a union to
allow variability).