How does C type syntax avoid circular definition?

Question

This statement and example is from Essential C by Nick Parlante.

One nice thing about the C type syntax is that it avoids the circular definition problems which come up when a pointer structure needs to refer to itself. The following definition defines a node in a linked list. Note that no preparatory declaration of the node pointer type is necessary.

   struct node {
      int data;
      struct node* next;
   };

How does the C compiler know what is struct node* when it is still inside the struct node.

There is another example of circular definition, wherein a type struct treenode* is used before it is defined further down.

typedef struct treenode* Tree;
struct treenode {
    int data;
    Tree smaller, larger;   // equivalently, this line could say
                            // "struct treenode *smaller, *larger"
};

How does the C compiler know what is struct treenode* when it hasn't been defined yet.

Related SO Question: How does C resolve circular definition when a pointer in struct points to the struct itself? (This is related, it doesn't answer the "How" question).

Edit: I am assuming that C compiler is able to do this in a single pass.

Incidentally, see [Is it a good idea to typedef pointers](https://stackoverflow.com/questions/750178/) — TL;DR the answer is usually "no", except perhaps for function pointers. — Jonathan Leffler, Apr 24 '19 at 20:09

Jonathan Leffler · Accepted Answer · 2018-07-15T05:17:00.870

The C standard stipulates in §6.2.5 Types ¶28 (emphasis added):

A pointer to void shall have the same representation and alignment requirements as a pointer to a character type.⁴⁸⁾ Similarly, pointers to qualified or unqualified versions of compatible types shall have the same representation and alignment requirements. All pointers to structure types shall have the same representation and alignment requirements as each other. All pointers to union types shall have the same representation and alignment requirements as each other. Pointers to other types need not have the same representation or alignment requirements.

Consequently, the C compiler knows how to handle any structure pointer type because all structure pointers must have the same representation and alignment requirements. That applies whether you embed a struct node * or a struct value * — whether or not the compiler was previously aware of the type struct value. This also helps with 'opaque types' — you can have pointers to structure types where the compiler does not know the content of the structure.

What you can't do is embed a struct node (rather than struct node *) within the definition of struct node. You can embed a previously known structure type as a value within the structure. You can also define a structure type within another:

struct node
{
    int data;
    struct node *next;
    struct key_value
    {
        int key;
        char *value;
    } kv;
};

Unlike C++, the struct key_value type is available without problems of scope — it is not restricted to use in the type struct node. This is not good coding practice, but it is permissible.

score 4 · Answer 2 · answered Jul 15 '18 at 04:43

4

You can declare a pointer to an incomplete type - the size and representation of a pointer does not depend on size or representation of the pointed-to type.

It also helps that, per the language standard, that pointers to all struct types have the same size and representation

answered Jul 15 '18 at 04:43

John Bode

119,563
19
122
198

Hi John Bode, could you explain a bit more on the second part of your answer. What's the same size as per the language standard? – Senthil Kumaran Jul 15 '18 at 04:44
1

`struct node {` tells the compiler there will be a of `struct node` defined later. `struct node *` declare a pointer to that type -- which is fine, even though `struct node` is a incomplete type at that point. It is similar to providing a function prototype long before you provide the actual function definition. – David C. Rankin Jul 15 '18 at 05:18
2

@SenthilKumaran In principle, when you have two different types `T1` and `T2`, then `T1 *` and `T2 *` can have different sizes, alignment requirements, etc. But the standard requires that if `T1` and `T2` are struct types, then their pointer types must have the same size and representation (i.e. in `struct foo *ptr;` the `ptr` variable works the same way no matter what `struct foo` is). – melpomene Jul 15 '18 at 06:12

score 0 · Answer 3 · answered Jul 15 '18 at 04:46

0

You can define a pointer, whose size is known by the compiler, to an instance of the struct itself but it is illegal to define a struct inside a struct of the same type in type declaration.

If you attempt to declare a struct rather than a struct*, you would get a compiler error.

answered Jul 15 '18 at 04:46

fnisi

1,181
1
14
24

1

Curiously, you could use `struct node { int value; struct node *next; struct key_value { int key; char *value; } x; };` defining a different structure type inside `struct node`. What you can't do is embed a `struct node` inside the definition of `struct node` — that requires infinite storage and computers don't have that much storage. So, change the last line to say `struct node` (twice) instead of just `struct` and you would be correct. – Jonathan Leffler Jul 15 '18 at 05:11

How does C type syntax avoid circular definition?

3 Answers3