Handling Circular Dependency

**Chris Torek** · Jul 16 '07, 04:05 AM

Re: Handling Circular Dependency

In article <1184553222.576 332.81730@g4g20 00hsf.googlegro ups.com>
joshc <josh.curtz@gma il.comwrote:

>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.)
--
In-Real-Life: Chris Torek, Wind River Systems
Salt Lake City, UT, USA (40°39.22'N, 111°50.29'W) +1 801 277 2603
email: forget about it http://web.torek.net/torek/index.html
Reading email is like searching for food in the garbage, thanks to spammers.

**joshc** · Jul 16 '07, 01:15 PM

Re: Handling Circular Dependency

On Jul 16, 12:03 am, Chris Torek <nos...@torek.n etwrote:

In article <1184553222.576 332.81...@g4g20 00hsf.googlegro ups.com>
>
joshc <josh.cu...@gma il.comwrote:

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.

**joshc** · Jul 16 '07, 01:45 PM

Re: Handling Circular Dependency

On Jul 16, 12:03 am, Chris Torek <nos...@torek.n etwrote:

In article <1184553222.576 332.81...@g4g20 00hsf.googlegro ups.com>
>
joshc <josh.cu...@gma il.comwrote:

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"

>

</snip>

>
[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.

Handling Circular Dependency

Handling Circular Dependency

Comment

Comment

Comment