Handling Circular Dependency

J

joshc

I've found some old posts on this issue but the answer was a bit vague
to me. The problem I am trying to solve is the following:

/***** a.h ***********/
#include "b.h"

/* Forward declaration */
struct type2;

typedef struct type1
{
int x;
int y;
type2 *ptr;
} type1;

void foo1(type1 *ptr, type2 *ptr2);



/********* b.h *********/
#include "a.h"

/* Forward declaration */
struct type1;

typedef struct type2
{
int x;
type1 y;
} type2;


The problem I have here is that for this to work I can't just use the
typedef'd name in the declaration of function foo1, I have to prefix
it with struct type1 *ptr, etc. Furthermore, the forward declaration
only will work for pointer types and won't work in the case of the
struct type2 which contains a member of type1 rather than pointer to
type1.

What is a good solution for this issue? Please don't get into
arguments about typedefs being bad in this case, I'd like to get a
solution to the problem I posed above.

Thanks.
 
C

Chris Torek

I've found some old posts on this issue but the answer was a bit vague
to me. The problem I am trying to solve is the following:

/***** a.h ***********/
#include "b.h"
[snippage...]

/********* b.h *********/
#include "a.h"

Your biggest problem at this point is that "a.h" unconditionally
includes all of "b.h", which immediately unconditionally includes
all of "a.h", which immediately unconditionally includes all of
"b.h", which ... well, this never stops.

If you really want separate header files, you *must* arrange for
each one to be included only once, not infinitely-many-times. :)
If the types are as tightly intertwined as implied here, the "best"
answer may well be "use a single header file". But assuming you
want separate files, consider:

/* a.h */
#ifndef H_A
#define H_A
... contents of a.h ...
#endif /* H_A */

/* b.h */
#ifndef H_B
#define H_B
... contents of b.h ...
#endif

If the "contents" part of a.h begins with "#include b.h", this
starts by including b.h. If b.h has previously been included,
H_B will be defined, and nothing else happens; otherwise, H_B
is defined, and the contents of b.h appear. If those contents
begin by including a.h, nothing happens in that inclusion, since
H_A is now defined -- so the otherwise-infinite inclusion-recursion
terminates in all cases.

That solves everything except the "forward declaration" part.
You should look at <http://web.torek.net/torek/c/types2.html>
as well; but given the assumption that you require (for whatever
reason) separate headers, it is clear that at least *one* of
the two types must remain incomplete while the other is completed.

[contents of a.h:]
#include "b.h"
/* Forward declaration */
struct type2;

If b.h has declared (or fully defined) "struct type2", there is
no need to forward-declare it in a.h (although it will not hurt
either). It may, however, be wise to declare "struct type1"
with a forward declaration at this point -- and, as we will see
later, it may be wise to provide a forward-declaration for
"struct type2" as well.
typedef struct type1
{
int x;
int y;
type2 *ptr;
} type1;

This combines the actual definition of "struct type1" with a
typedef-alias, also named "type1". It is probably wise not to
use the same name for both, simply because it *is* wise to give
typedef-names some sort of "marking", so that it is immediately
obvious that they *are* typedef-names. I also believe it is
often unwise to combine the definition and the typedef. (It
*is*, I think, sensible to combine the forward-declaration and the
typedef, at least at the outermost scope.)

So, assuming that b.h has declared "struct type2", and further,
that the "marker" for "this is a typedef-name" is all-capitals,
I might write instead:

#ifndef H_A
#define H_A

#include "b.h"

typedef struct type1 TYPE1;

struct type1 {
int x;
int y;
TYPE2 *ptr;
};

At this point it is safe to continue on with:

void foo1(TYPE1 *ptr, TYPE2 *ptr2);

#endif /* H_A */

Now, however, we get to "b.h", where things get trickier. Note
the assumption we made above: b.h will have declared or even
fully-defined "struct type2" *and* the typedef-alias TYPE2 *before*
the rest of a.h is processed.

If b.h can be "included first", for the above to hold, we must
write b.h more carefully:

#ifndef H_B
#define H_B

/* DO NOT INCLUDE a.h HERE YET! */

Now we must provide a forward declaration for "struct type2", and
its typedef-alias:

typedef struct type2 TYPE2;

and *now* it is safe to include "a.h":

#include "a.h"

because the names "struct type2" and "TYPE2" both exist, and both
refer to the incomplete type.

Since a.h may include b.h without first declaring "struct type1"
and "TYPE1", however, and since re-including a.h at this point may
be a no-op, we *must not* assume that the inclusion of a.h here
declares the names "struct type1" and "TYPE1". So, while defining
the contents for "struct type2", we must make sure we have a
forward declaration for "struct type1":

typedef struct type2 TYPE2;
struct type1;

struct type2 {
... contents ...
};

Note that "struct type1" remains incomplete at this point; indeed,
it must, because a.h need not have fully-defined it when a.h includes
b.h. Thus, we can have a "struct type1 *" in the contents, but
not a "TYPE1 *" (because this typedef-alias-name does not exist),
nor a "struct type1" (because this type is incomplete).

Unfortunately, you want to have an actual "struct type1" inside
the contents for type2:
typedef struct type2
{
int x;
type1 y;
} type2;

So, as you say:
The problem I have here is that for this to work I can't just use the
typedef'd name in the declaration of function foo1, I have to prefix
it with struct type1 *ptr, etc. Furthermore, the forward declaration
only will work for pointer types and won't work in the case of the
struct type2 which contains a member of type1 rather than pointer to
type1.
What is a good solution for this issue? Please don't get into
arguments about typedefs being bad in this case ...

OK, ignoring the argument against typedefs, we can summarize the
constraints:

- a.h and b.h must be separate files (why? who knows...), and
- b.h uses the (non-opaque, fully-defined) contents of one of
the types in a.h, and
- a.h uses the (opaque, not-necessarily-fully-defined) contents
of one of the types in b.h.

Given these, clearly b.h must fully include a.h. So the "best"
remaining solution is to have b.h include a.h, and have a.h *not*
include b.h at all. Make a.h independent of b.h -- which means
that either:

- a.h must not use the typedef-name that b.h defines, or
- b.h must not be where the typedef-name is defined.

We can achieve the first by making a.h read, in its entirety:

#ifndef H_A
#define H_A

struct type2; /* forward declaration from b.h which we cannot include */

typedef struct type1 TYPE1;

struct type1 {
int x;
int y;
struct type2 *ptr;
};

void foo1(TYPE1 *ptr, struct type2 *ptr2);

#endif /* H_A */

It is now safe for b.h to include a.h, and then depend on the name
TYPE1 being defined, and "struct type1" being a complete type.

We can achieve the second by modifying a.h as follows:

#ifndef H_A
#define H_A

#include "b-incomplete.h"
/* where b-incomplete.h declares (but does not define
"struct type2", and creates the typedef-alias TYPE2 */

typedef struct type1 TYPE1;

struct type1 {
int x;
int y;
TYPE2 *ptr;
};

void foo1(TYPE1 *ptr, struct type2 *ptr2);

#endif /* H_A */

The contents of b-incomplete.h are now obvious, and remarkably short:

#ifndef H_B_INCOMPLETE
#define H_B_INCOMPLETE

typedef struct type2 TYPE2;

#endif /* H_B_INCOMPLETE */

(The "overall best" solution, in my opinion, is to delete the first
requirement -- that a.h and b.h be separate headers -- and simply
put all the appropriate declarations and definitions in one file.)
 
B

Barry Schwarz

I've found some old posts on this issue but the answer was a bit vague
to me. The problem I am trying to solve is the following:

/***** a.h ***********/
#include "b.h"

/* Forward declaration */
struct type2;

typedef struct type1
{
int x;
int y;
type2 *ptr;
} type1;

void foo1(type1 *ptr, type2 *ptr2);



/********* b.h *********/
#include "a.h"

/* Forward declaration */
struct type1;

typedef struct type2
{
int x;
type1 y;
} type2;


The problem I have here is that for this to work I can't just use the
typedef'd name in the declaration of function foo1, I have to prefix

It is legal to typedef a struct type even if the struct is incomplete
at the moment. At the top of a.h you can put
typedef struct type1 type1;
typedef struct type2 type2;
and then declare the complete struct types at your convenience. This
will allow you to declare a pointer to either struct using just the
typedef name.
it with struct type1 *ptr, etc. Furthermore, the forward declaration
only will work for pointer types and won't work in the case of the

The reason a struct can contain a pointer to any struct, even one that
is incomplete at the moment, is that the standard requires all
pointers to struct to have the same size and representation.
Therefore, the compiler can figure out how to place the pointer member
in the struct without knowing anything about the internal details of
the pointed to struct.
struct type2 which contains a member of type1 rather than pointer to

But in order to place an actual struct member (not a pointer member)
inside another struct, the compiler must know at least the alignment
and size of this internal struct.
type1.

What is a good solution for this issue? Please don't get into
arguments about typedefs being bad in this case, I'd like to get a
solution to the problem I posed above.

There is no way for a struct a to contain a member of type struct b
when struct b must also contain a member to type struct a. While
there may be other workarounds that I cannot think of at the moment,
the usual solution is as you coded: completely define the internal
structure, including a pointer to the external structure, and then
completely define the external structure, including a member of type
internal structure.


Remove del for email
 
J

joshc

joshc said:
I've found some old posts on this issue but the answer was a bit vague
to me. The problem I am trying to solve is the following:
/***** a.h ***********/
#include "b.h"
[snippage...]

/********* b.h *********/
#include "a.h"

Your biggest problem at this point is that "a.h" unconditionally
includes all of "b.h", which immediately unconditionally includes
all of "a.h", which immediately unconditionally includes all of
"b.h", which ... well, this never stops.

If you really want separate header files, you *must* arrange for
each one to be included only once, not infinitely-many-times. :)
If the types are as tightly intertwined as implied here, the "best"
answer may well be "use a single header file". But assuming you
want separate files, consider:

/* a.h */
#ifndef H_A
#define H_A
... contents of a.h ...
#endif /* H_A */

/* b.h */
#ifndef H_B
#define H_B
... contents of b.h ...
#endif

If the "contents" part of a.h begins with "#include b.h", this
starts by including b.h. If b.h has previously been included,
H_B will be defined, and nothing else happens; otherwise, H_B
is defined, and the contents of b.h appear. If those contents
begin by including a.h, nothing happens in that inclusion, since
H_A is now defined -- so the otherwise-infinite inclusion-recursion
terminates in all cases.

That solves everything except the "forward declaration" part.
You should look at <http://web.torek.net/torek/c/types2.html>
as well; but given the assumption that you require (for whatever
reason) separate headers, it is clear that at least *one* of
the two types must remain incomplete while the other is completed.

Yes, I know about multiple-inclusion guards but as you can tell I
whipped up a toy example to mimic what is actually happening in my
code and in my haste didn't add the guards.
 
J

joshc

joshc said:
I've found some old posts on this issue but the answer was a bit vague
to me. The problem I am trying to solve is the following:
/***** a.h ***********/
#include "b.h"
[snippage...]

/********* b.h *********/
#include "a.h"

[contents of a.h:]
#include "b.h"
/* Forward declaration */
struct type2;

If b.h has declared (or fully defined) "struct type2", there is
no need to forward-declare it in a.h (although it will not hurt
either). It may, however, be wise to declare "struct type1"
with a forward declaration at this point -- and, as we will see
later, it may be wise to provide a forward-declaration for
"struct type2" as well.
typedef struct type1
{
int x;
int y;
type2 *ptr;
} type1;

This combines the actual definition of "struct type1" with a
typedef-alias, also named "type1". It is probably wise not to
use the same name for both, simply because it *is* wise to give
typedef-names some sort of "marking", so that it is immediately
obvious that they *are* typedef-names. I also believe it is
often unwise to combine the definition and the typedef. (It
*is*, I think, sensible to combine the forward-declaration and the
typedef, at least at the outermost scope.)

So, assuming that b.h has declared "struct type2", and further,
that the "marker" for "this is a typedef-name" is all-capitals,
I might write instead:

#ifndef H_A
#define H_A

#include "b.h"

typedef struct type1 TYPE1;

struct type1 {
int x;
int y;
TYPE2 *ptr;
};

At this point it is safe to continue on with:

void foo1(TYPE1 *ptr, TYPE2 *ptr2);

#endif /* H_A */

Now, however, we get to "b.h", where things get trickier. Note
the assumption we made above: b.h will have declared or even
fully-defined "struct type2" *and* the typedef-alias TYPE2 *before*
the rest of a.h is processed.

If b.h can be "included first", for the above to hold, we must
write b.h more carefully:

#ifndef H_B
#define H_B

/* DO NOT INCLUDE a.h HERE YET! */

Now we must provide a forward declaration for "struct type2", and
its typedef-alias:

typedef struct type2 TYPE2;

and *now* it is safe to include "a.h":

#include "a.h"

because the names "struct type2" and "TYPE2" both exist, and both
refer to the incomplete type.

Since a.h may include b.h without first declaring "struct type1"
and "TYPE1", however, and since re-including a.h at this point may
be a no-op, we *must not* assume that the inclusion of a.h here
declares the names "struct type1" and "TYPE1". So, while defining
the contents for "struct type2", we must make sure we have a
forward declaration for "struct type1":

typedef struct type2 TYPE2;
struct type1;

struct type2 {
... contents ...
};

Note that "struct type1" remains incomplete at this point; indeed,
it must, because a.h need not have fully-defined it when a.h includes
b.h. Thus, we can have a "struct type1 *" in the contents, but
not a "TYPE1 *" (because this typedef-alias-name does not exist),
nor a "struct type1" (because this type is incomplete).

Unfortunately, you want to have an actual "struct type1" inside
the contents for type2:
typedef struct type2
{
int x;
type1 y;
} type2;

So, as you say:
The problem I have here is that for this to work I can't just use the
typedef'd name in the declaration of function foo1, I have to prefix
it with struct type1 *ptr, etc. Furthermore, the forward declaration
only will work for pointer types and won't work in the case of the
struct type2 which contains a member of type1 rather than pointer to
type1.
What is a good solution for this issue? Please don't get into
arguments about typedefs being bad in this case ...

OK, ignoring the argument against typedefs, we can summarize the
constraints:

- a.h and b.h must be separate files (why? who knows...), and
- b.h uses the (non-opaque, fully-defined) contents of one of
the types in a.h, and
- a.h uses the (opaque, not-necessarily-fully-defined) contents
of one of the types in b.h.

Given these, clearly b.h must fully include a.h. So the "best"
remaining solution is to have b.h include a.h, and have a.h *not*
include b.h at all. Make a.h independent of b.h -- which means
that either:

- a.h must not use the typedef-name that b.h defines, or
- b.h must not be where the typedef-name is defined.

We can achieve the first by making a.h read, in its entirety:

#ifndef H_A
#define H_A

struct type2; /* forward declaration from b.h which we cannot include */

typedef struct type1 TYPE1;

struct type1 {
int x;
int y;
struct type2 *ptr;
};

void foo1(TYPE1 *ptr, struct type2 *ptr2);

#endif /* H_A */

It is now safe for b.h to include a.h, and then depend on the name
TYPE1 being defined, and "struct type1" being a complete type.

We can achieve the second by modifying a.h as follows:

#ifndef H_A
#define H_A

#include "b-incomplete.h"
/* where b-incomplete.h declares (but does not define
"struct type2", and creates the typedef-alias TYPE2 */

typedef struct type1 TYPE1;

struct type1 {
int x;
int y;
TYPE2 *ptr;
};

void foo1(TYPE1 *ptr, struct type2 *ptr2);

#endif /* H_A */

The contents of b-incomplete.h are now obvious, and remarkably short:

#ifndef H_B_INCOMPLETE
#define H_B_INCOMPLETE

typedef struct type2 TYPE2;

#endif /* H_B_INCOMPLETE */

(The "overall best" solution, in my opinion, is to delete the first
requirement -- that a.h and b.h be separate headers -- and simply
put all the appropriate declarations and definitions in one file.)

This is ultimately the solution I had come up with on my own. I just
wanted to make sure there was no better way of doing this. Another
thought I had was to maintain the separate headers but include them in
one master header file that then gets included in each of the source
code files.
 

Ask a Question

Want to reply to this thread or ask your own question?

You'll need to choose a username for the site, which only take a couple of moments. After that, you can post your question and our members will help you out.

Ask a Question

Members online

Forum statistics

Threads
473,744
Messages
2,569,481
Members
44,900
Latest member
Nell636132

Latest Threads

Top