3

I am used to code like below for long.

But how does C compiler resolve the circular definition issue? Or does that issue really exist?

struct node {
    int data;
    struct node *next; // circular definition for "struct node" type?
};

ADD 1

Or, on a 32-bit machine, can I somewhat treat struct node * next member just as a member of 32-bit unsigned integer type? That makes me feel better.

ADD 2

The reason I think of circular definition is, when compiler encounters something like next -> data or next -> next, it has to know the exact offset of each member to add to the next pointer to get the correct location of each member. And that kind of calculation requires knowledge of each member's type. So for the member next, the circular definition issue may arise:

The type of next is struct node *, the struct node type contains a next, the type of next is struct node *...

ADD 3

And how does the compiler calculate the sizeof(struct node)?

ADD 4

Well, I think the critical concept to understand this seemingly circular issue is, a pointer's size is not relevant to what type it points to. And the size is fixed on a specific machine. A pointer's type is only meaningful at compile-time for the compiler to generate instructions for pointer calculation.

chqrlie
  • 131,814
  • 10
  • 121
  • 189
smwikipedia
  • 61,609
  • 92
  • 309
  • 482
  • It doesn't matter whether *you* can do it or not; the question is whether thw compiler can do it. And the answer is that the compiler understands the mapping between addresses and *k*-bit integers, as well as the value of *k*. – rici Mar 06 '17 at 01:48
  • What issue do you think the compiler needs to resolve? – user253751 Mar 06 '17 at 01:50
  • There's no issue. You would not write `next -> next` until after the struct definition is complete, at which point the compiler has all the information to work out the offsets – M.M Mar 06 '17 at 02:37
  • The size of the structure is the size of an `int` plus the size of a structure pointer (all structure pointers have the same size) plus any alignment padding that's required (none on a 32-bit platform; probably 4 bytes on a 64-bit platform). – Jonathan Leffler Mar 06 '17 at 02:41

2 Answers2

7

next is a struct node *, which is just a pointer, not a struct node, so there's no actual circular definition. The details of a struct aren't required to figure out how to make a pointer to it.

To address your addenda:

  1. Although that's more or less accurate and will probably work, it's not guaranteed by the standard, and you shouldn't do it.
  2. Again, struct node and struct node * are entirely different types. A struct node * doesn't contain any other objects.
Joseph Sible-Reinstate Monica
  • 45,431
  • 5
  • 48
  • 98
1

Let me answer your questions in order:

But how does C compiler resolve the circular definition issue?

struct node *next; is not a circular definition, struct node is an incomplete type, next is defined as a member with type struct node *, which is just a pointer.

Or does that issue really exist?

No, not really an issue. As a matter of fact, you could have members defined as pointers to any undefined structure.

Or, on a 32-bit machine, can I somewhat treat struct node *next member just as a member of 32-bit unsigned integer type?

You should not make any assumptions on the actual size, offset or alignment of structure members. A 32-bit machine could have pointers sizes that are not 32 bits, it does not matter as long as you use them as pointers, not integers.

The reason I think of circular definition is, when compiler encounters something like next->data or next->next, it has to know the exact offset of each member to add to the next pointer to get the correct location of each member.

That's correct, but by the time the compiler parses such code, the structure definition is complete and it can determine the offset of the data and next members.

And how does the compiler calculate the sizeof(struct node)?

After parsing the structure definition, the compiler has all the information needed to compute the size of structure instances. For such a computation, all pointers to structures and/or unions are assumed to have the same size.

Well, I think the critical concept to understand this seemingly circular issue is, a pointer's size is not relevant to what type it points to. And the size is fixed on a specific machine. A pointer's type is only meaningful at compile-time for the compiler to generate instructions for pointer calculation.

A pointer size is relevant to the type it points to, and on some architectures, different pointer types may have different sizes. Yet the C Standard specifies some constraints:

  • All pointer types can be converted to void * and back.
  • Pointers to all structures and unions have the same size.

On most modern architectures, and specifically on Posix compliant systems, all standard pointers types have the same size.

chqrlie
  • 131,814
  • 10
  • 121
  • 189
  • (Thanks for the detailed answer.) For your 1st answer, when you say "`struct node` is an *incomplete type*", do you mean when compiler sees the definition of `struct node* next`, which is *before* the parsing of the `struct node` type is finished. – smwikipedia Mar 06 '17 at 12:58
  • And for your last answer, I checked the size of with several pointer types in a 32bit program. All sizes are 4 bytes. When will different pointer types have different size? – smwikipedia Mar 06 '17 at 13:00
  • @smwikipedia: you are unlikely to find such architectures today, but the Standard allows for pointers to `int` to have a different size from pointers to `char`. This is the case on some DSPs and some older mainframe computers. Note also that some segmented architectures supported by Windows 2.x used to have different pointer sizes for data and code pointers. – chqrlie Mar 06 '17 at 16:50