Declaration rule in struct typedef

Question

I'm reading 'The C Programming Language' and encountered a problem about typedef of struct. The code is like this:

typedef struct tnode *Treeptr;
typedef struct tnode { /* the tree node: */
    char *word; /* points to the text */
    int count; /* number of occurrences */
    struct tnode *left; /* left child */
    struct tnode *right; /* right child */
} Treenode;

By the time we write

typedef struct tnode *Treeptr;

tnode is still not declared yet, but we don't get any compilation error, but when we change the statement above into:

typedef Treenode *Treeptr;

We get compilation error:

error: parse error before '*' token
warning: data definition has no type or storage class

What causes the difference? Isn't "struct tnode" the same as "Treenode"?

You might find [Which part of the C standard allows this code to compile?](http://stackoverflow.com/questions/12200096/which-part-of-the-c-standard-allows-this-code-to-compile) and [Does the C standard consider that there are one or two `struct uperms_entry` types in this header?](http://stackoverflow.com/questions/11697705/does-the-c-standard-consider-that-there-are-one-or-two-struct-uperms-entry-typ) as relevant, but they may be pitched at a level that is beyond where you're at. — Jonathan Leffler, Nov 09 '12 at 06:32

score 6 · Accepted Answer · answered Nov 09 '12 at 06:41

You can't use a type before it is defined.

With the typedef struct tnode { ... } Treenode; declaration, the type Treenode is not defined until the semi-colon is reached.

The situation with typedef struct tnode *Treeptr; is different. This tells the compiler 'there is a structure type called struct tnode, and the type Treeptr is an alias for a pointer to a struct tnode'. At the end of that declaration, struct tnode is an incomplete type. You can create pointers to incomplete types but you cannot create variables of the incomplete type (so you could define Treeptr ptr1; or struct tnode *ptr2; and they are the same type, but you could not define struct tnode node;).

The body of the struct tnode could be written as:

typedef struct tnode
{
    char    *word;
    int      count;
    Treeptr  left;
    Treeptr  right;
} Treenode;

because Treeptr is a known alias for the type struct tnode * before the structure is defined. You can't use Treenode *left; because Treenode is not a known alias until the final semi-colon is reached (roughly speaking).

score 1 · Answer 2 · answered Nov 09 '12 at 06:41

1

When you declare TreePtr, you are not implementing the struct. That is known as a "forward declaration". Something like: "here we use this, but later I will explain it better". The implementation must appear later, only once, and that is what you find in the second typedef.

And TreePtr is not the same as the struct, because TreePtr will be in fact a new type that includes the fact of beeing a pointer.

answered Nov 09 '12 at 06:41

felixgaal

2,403
15
24

Thanks, Fèlix, nice explanation. So you mean `struct undefined_struct *a;` is allowed, but we should implement the `undefined_struct` before we say `struct undefined_struct b", is that right? But what is the intention for this "_foward declaration_"? – Rain Nov 09 '12 at 07:14
1

Forward declarations, or incomplete types, can be helpful in two cases. It is possible to create mutually recursive structures, so that `struct a` contains a pointer to a `struct b` and `struct b` contains a pointer to a `struct a`. That's esoteric (but would be a real problem if forward declaration was not possible). The more coogent reason for incomplete types is that you can define the interface to a set of functions in terms of pointers to incomplete types and the public header never has to reveal what's inside the structures; they are an 'opaque type', and you're using information hiding. – Jonathan Leffler Nov 09 '12 at 07:29
You can do things like `struct undef a;`, `struct undef *b;`, etc. in any combination, as much as you need. You can include them inside another struct. But you _must_ declare the implementation of the struct once, where and when you prefer. – felixgaal Nov 09 '12 at 21:34
@FèlixGalindoAllué: I think it's only necessary to supply any definition for a struct in cases where one either dereferences it or tries to create a storage location of the structure type (rather than a pointer-to-structure type). If a pointer types is never used as anything other than an opaque pointer type, there's no need to ever supply definition for the struct contents. – supercat Dec 12 '13 at 20:39

score 0 · Answer 3 · answered Nov 09 '12 at 06:40

A line typedef struct tnode *Treeptr; has implicit forward declaration of "tnode" struct. It's similar to:

typedef struct tnode Treenode;
typedef Treenode *Treeptr;

struct tnode { /* the tree node: */
    char *word; /* points to the text */
    int count; /* number of occurrences */
    struct tnode *left; /* left child */
    struct tnode *right; /* right child */
};

Declaration rule in struct typedef

3 Answers3

Linked