C header file loops

Question

I have a couple of header files, which boil down to:

tree.h:

#include "element.h"

typedef struct tree_
{
    struct *tree_ first_child;
    struct *tree_ next_sibling;
    int tag;
    element *obj;
    ....
} tree;

and element.h:

#include "tree.h"

typedef struct element_
{
    tree *tree_parent;
    char *name;
    ...
} element;

The problem is that they both reference each other, so tree needs element to be included, and element needs tree to be included.

This doesn't work because to define the 'tree' structure, the element structure must be already known, but to define the element structure, the tree structure must be known.

How to resolve these types of loops (I think this may have something to do with 'forward declaration'?)?

Answer 1

I think the problem here is not the missing include guard but the fact that the two structures need each other in their definition. So it's a type define hann and egg problem.

The way to solve these in C or C++ is to do forward declarations on the type. If you tell the compiler that element is a structure of some sort, the compiler is able to generate a pointer to it.

E.g.

Inside tree.h:

// tell the compiler that element is a structure typedef:
typedef struct element_ element;

typedef struct tree_ tree;
struct tree_
{
    tree *first_child;
    tree *next_sibling;
    int tag;

    // now you can declare pointers to the structure.
    element *obj;
};

That way you don't have to include element.h inside tree.h anymore.

You should also put include-guards around your header-files as well.

Answer 2

Crucial observation here is that the element doesn't need to know the structure of tree, since it only holds a pointer to it. The same for the tree. All each needs to know is that there exists a type with the relevant name, not what's in it.

So in tree.h, instead of:

#include "element.h"

do:

typedef struct element_ element;

This "declares" the types "element" and "struct element_" (says they exist), but doesn't "define" them (say what they are). All you need to store a pointer-to-blah is that blah is declared, not that it is defined. Only if you want to deference it (for example to read the members) do you need the definition. Code in your ".c" file needs to do that, but in this case your headers don't.

Some people create a single header file which forward-declares all the types in a cluster of headers, and then each header includes that, instead of working out which types it really needs. That's neither essential nor completely stupid.

The answers about include guards are wrong - they're a good idea in general, and you should read about them and get yourself some, but they don't solve your problem in particular.

Answer 3

The correct answer is to use include guards, and to use forward declarations.

Include Guards

/* begin foo.h */
#ifndef _FOO_H
#define _FOO_H

// Your code here

#endif
/* end foo.h */

Visual C++ also supports #pragma once. It is a non standard preprocessor directive. In exchange for compiler portability, you reduce the possibility of preprocessor name collisions and increase readability.

Forward Declarations

Forward declare your structs. If the members of a struct or class are not explicitly needed, you can declare their existence at the beginning of a header file.

struct tree;    /* element.h */
struct element; /* tree.h    */

Answer 4

Read about forward declarations.

ie.

// tree.h:
#ifndef TREE_H
#define TREE_H
struct element;
struct tree
{
    struct element *obj;
    ....
};

#endif

// element.h:
#ifndef ELEMENT_H
#define ELEMENT_H
struct tree;
struct element
{
    struct tree *tree_parent;
    ...
};
#endif

Answer 5

These are known as "once-only headers." See http://developer.apple.com/DOCUMENTATION/DeveloperTools/gcc-4.0.1/cpp/Once_002dOnly-Headers.html#Once_002dOnly-Headers

Answer 6

Include guards are useful, but don't address the poster's problem which is the recursive dependency on two data structures.

The solution here is to declare tree and/or element as pointers to structs within the header file, so you don't need to include the .h

Something like:

struct element_;
typedef struct element_ element;

At the top of tree.h should be enough to remove the need to include element.h

With a partial declaration like this you can only do things with element pointers that don't require the compiler to know anything about the layout.

Answer 7

IMHO the best way is to avoid such loops because they are a sign of physical couping that should be avoided.

For example (as far as I remember) "Object-Oriented Design Heuristics" purpose to avoid Include Guards because they only mask the cyclic (physical) dependency.

An other approach is to predeclare the structs like this:

element.h:
struct tree_;
struct element_
  {
    struct tree_ *tree_parent;
    char *name;
  };


tree.h:
struct element_;
struct tree_
  {
    struct tree_* first_child;
    struct tree_* next_sibling;
    int tag;
    struct element_ *obj;
  };

Answer 8

Forward declaratio is the way with which you can guarantee that there will be a tyoe of structure which will be defined later on.

Answer 9

I don't like forward declarations cause they are redundant and buggy. If you want all your declarations in the same place then you should use includes and header files with include guards.

You should think about includes as a copy-paste, when the c preprocesor finds an #include line just places the entire content of myheader.h in the same location where #include line was found.

Well, if you write include guards the myheader.h's code will be pasted only one time where the first #include was found.

If your program compiles with several object files and problem persists then you should use forward declarations between object files (it's like using extern) in order to keep only a type declaration to all object files (compiler mixes all declarations in the same table and identifiers must be unique).

Answer 10

A simple solution is to just not have separate header files. After all, if they're dependent on each other you're never going to use one without the other, so why separate them? You can have separate .c files that both use the same header but provide the more focused functionality.

I know this doesn't answer the question of how to use all the fancy stuff correctly, but I found it helpful when I was looking for a quick fix to a similar problem.