Resolve circular typedef dependency?

Question

What is the best way to resolve the following circular dependency in typedef-ing these structs?
Note the C language tag - I'm looking for a solution in standard gcc C.

typedef struct {
    char* name;
    int age;
    int lefthanded;
    People* friends;
} Person;

typedef struct {
    int count;
    int max;
    Person* data;
} People;

Answer 1

The answer lies in the difference between declaration and definition. You are attempting to declare and define in the same step (in the case of a new type via typedef). You need to break these up into different steps so the compiler knows what you are talking about in advance.

typedef struct Person Person;
typedef struct People People;

struct Person {
    char* name;
    int age;
    int lefthanded;
    People* friends;
};

struct People {
    int count;
    int max;
    Person* data;
};

Note the addition of the two 'empty' typedefs at the top (declarations). This tells the compiler that the new type Person is of type 'struct Person' so that when it sees that inside the definition of struct People it knows what it means.

In your particular case, you could actually get away with only predeclaring the People typdef because that is the only type used before it is defined. By the time you get into the definition of struct People, you have already fully defined the type Person. So the following would also work but is NOT RECOMMENDED because it is fragile:

typedef struct People People;

typedef struct {
    char* name;
    int age;
    int lefthanded;
    People* friends;
} Person;

struct People {
    int count;
    int max;
    Person* data;
};

If you swap the order of the structure definitions (moving struct People above the typedef of Person) it will fail again. That's what makes this fragile and, therefore, not recommended.

Note that this trick does NOT work if you include a struct of the specified type rather than a pointer to it. So, for example, the following WILL NOT compile:

typedef struct Bar Bar;

struct Foo
{
    Bar bar;
};

struct Bar
{
    int i;
};

The above code gives a compiler error because the type Bar is incomplete when it tries to use it inside the definition of struct Foo. In other words, it doesn't know how much space to allocate to structure member 'bar' because it hasn't seen the definition of struct bar at that point.

This code will compile:

typedef struct Foo Foo;
typedef struct Bar Bar;
typedef struct FooBar FooBar;

struct Foo
{
    Bar *bar;
};

struct Bar
{
    Foo *foo;
};

struct FooBar
{
    Foo     foo;
    Bar     bar;
    FooBar  *foobar;
};

This works, even with the circular pointers inside Foo and Bar, because the types 'Foo' and 'Bar' have been pre-declared (but not yet defined) so the compiler can build a pointer to them.

By the time we get to defining FooBar, we have defined how big both Foo and Bar are so we can include the actual objects there. We can also include a self-referential pointer to type FooBar because we have pre-declared the type.

Note that if you moved the definition of struct FooBar above the definitions of either struct Foo or Bar, it would not compile for the same reason as the previous example (incomplete type).

Answer 2

Forward-declare one of the structs:

struct people;

typedef struct {
  /* same as before */
  struct people* friends;
} Person;

typedef struct people {
  /* same as before */
} People;

Answer 3

As for readability :

typedef struct Foo_ Foo;
typedef struct Bar_ Bar;

struct Foo_ {
    Bar *bar;
};

struct Bar_ {
    Foo *foo;
};

It might be a good idea to avoid typedef struct altogether;

Answer 4

Since Person just wants a pointer to People, it should be fine to just predeclare the latter:

typedef struct People People;

Then change the second declaration to just declare using the struct tag, like so:

struct People {
    int count;
    int max;
    Person data[];
};

Answer 5

struct _People;

typedef struct {
    char* name;
    int age;
    int lefthanded;
    struct _People* friends;
} Person;

struct _People {
    int count;
    int max;
    Person data[1];
};

Note: Is Person data[]; standard?