C circular dependency

Question

I have this problem with circular dependency in C, I looked around the other questions about this topic but really couldn't find the answer.

I have this first struct named vertex:

#ifndef MapTest_vertex_h
#define MapTest_vertex_h

#include "edgelist.h" //includes edgelist because it's needed

typedef struct 
{
    char* name;
    float x, y;
    edgelist* edges;
} vertex;

#endif

The second struct is the edgelist which is included by the vertex.

#ifndef edgelist_h
#define edgelist_h

#include "edge.h" //include edge, because its needed

typedef struct _edgelist
{
    edge** edges; 
    int capacity, size;
} edgelist;

//...

#endif

And then the last struct, the one where the problem raises, the edge struct gets included by the edgelist above.

#ifndef MapTest_edge_h
#define MapTest_edge_h

#include "vertex.h" //needs to be included because it will be unkown otherwise

typedef struct 
{
    float weight;
    vertex* destination;
    int found; 
} edge;

#endif

I tried everything I could, forward declaring, using #ifndef, #define etc. but couldn't find the answer.

How can I resolve this circular dependency problem?

In C11, you can repeat typedefs harmlessly. You could write `typedef struct edge edge;` — `typedef struct vertex vertex;` — `typedef struct edgelist edgelist;` in any or all the headers, and then simply define the structure type information (without the `typedef` prefix or the name at the end) in the relevant header: `struct vertex { … };` — `struct edge { … };` — `struct edgelist { … };`. This will not work in C99 or C90, though; defining a `typedef` for the same name is an error in earlier versions of C. — Jonathan Leffler, Mar 07 '17 at 22:05

score 15 · Accepted Answer · edited Mar 07 '17 at 22:00

Seems like you shouldn't need to include anything in any of the files. A forward declaration of the relevant types should be sufficient:

#ifndef MapTest_vertex_h
#define MapTest_vertex_h

struct edgelist;

typedef struct
{
    char* name;
    float x, y;
    edgelist* edges;    // C++ only - not C
} vertex;

#endif

etc. In C coding, you have to write:

struct edgelist;

typedef struct
{
    char* name;
    float x, y;
    struct edgelist* edges;
} vertex;

score 2 · Answer 2 · answered Apr 12 '12 at 11:52

2

This kind of dependency is broken using a forward declaration. Instead of including a file with the full definition of the struct, there are two alternatives:

1.

typedef struct 
{
    char* name;
    float x, y;
    struct _edgelist* edges; /* add "struct" here (elaborated type specifier) */
} vertex;

2.

struct __edgelist; /* better form: forward declaration */

typedef struct 
{
    char* name;
    float x, y;
    struct _edgelist* edges; /* still need to add "struct" here */
} vertex;

answered Apr 12 '12 at 11:52

Potatoswatter

134,909
25
265
421

1

Note that symbols starting with an underscore followed by either another underscore or a capital letter are unconditionally reserved for use by 'the implementation'. In general, avoid creating names starting with an underscore. – Jonathan Leffler Mar 07 '17 at 21:59

score 1 · Answer 3 · answered Apr 12 '12 at 11:40

I'm assuming a vertex needs to know what edges connect to it, and an edge needs to know what vertices it connects to.

If it were up to me, I'd create separate data types to associate vertices and edges:

struct vertex {
  char *name;
  float x, y;
};

// edgelist as before

struct edge {
  float weight;
  int found;
};

// New struct to map edges and vertices

struct vertexEdge { // you can probably come up with a better name
  struct vertex *v;
  struct edgelist *edges;
};

// New struct to map vertices and edges

struct edgeVertext {
{
  struct edge *e;
  struct vertex *vertices;
};

I'm running about 10-12 hours behind on sleep for the week, so I'm pretty sure there's a better way to design the mapping types (probably in a way that doesn't require more than one type), but this is the general approach I'd take.

C circular dependency

3 Answers3

Linked

Related