CODEWITHSUNDEEP
c
Kudayar Pirimbaev
Kudayar Pirimbaev

Reputation: 1320

C: Confusing types when allocating memory

For the following declaration of graph (that I cannot change - assignment),

#define TAG(vp)   ((vp)->tag)
#define LABEL(vp) ((vp)->label)  
#define EDGE(vp)  ((vp)->edge)

typedef struct vertex 
{
    char tag;
    char *label;
    struct vertex *edge[1];
}
vertex, *vp;

when I allocate memory with the following line

EDGE (test) = (vp *) malloc (sizeof (vp) * 3); // where test is a node of a graph

I get the following error

error: incompatible types when assigning to type ‘struct vertex *[1]’ from type ‘struct vertex **

Also I cannot assign EDGE as NULL. I guess I'm missing something with the declaration (it uses *ptr[1] which is quite confusing me). Can you help?

Thanks in advance.

Upvotes: 1

Views: 125

Answers (4)

V-X
V-X

Reputation: 3029

Instead of

EDGE (test) = (vp *) malloc (sizeof (vp) * 3);

you need to do

EDGE (test) = malloc (sizeof (vp)); // to allocate array of pointer to vertex
EDGE (test)[0] = malloc (sizeof (vertex)); // to allocate the vertex itself.

if you cannot change

struct vertex *edge[1];

Upvotes: 0

Carl Norum
Carl Norum

Reputation: 224844

What you're looking at is pre-C99 code called the "struct hack". In C99 or later, you'd use a flexible array member.

The general idea is that you allocate the structure plus some extra space at the end that you use through the array member:

struct vertex *v = malloc(sizeof *v + n * sizeof(struct vertex *));

To allocate a structure with space for n edges (and a sentinel, as @EricPostpischil mentions below). I didn't use your *vp typedef, since I don't like hiding pointer types via typedef like that.

After that allocation, you can just use the array like normal:

v->edge[0] = &someOtherVertex;
v->edge[1] = &someOtherOtherVertex;

And so on.

Upvotes: 5

Adrian Panasiuk
Adrian Panasiuk

Reputation: 7343

Using the readily available on linux systems program, cdecl I can see what does

 struct vertex *edge[1];

mean:

adi@laps:~$ cdecl
Type `help' or `?' for help
cdecl> explain struct vertex *edge[1];
declare edge as array 1 of pointer to struct vertex
cdecl>

Thus your prescribed data structure represents the edges coming out of a vertex as pointers stored in a structure. Because you do not have any count of how many edges there are, you are left to use a sentinel, NULL, to mark the end of the array.

Thus EDGE(vp)[0] is the first coincident vertex, EDGE(vp)[1] is the second, etc., until you read a NULL.

This is called the trailing array idiom and you must remember that sizeof(struct vertex) is the amount of memory needed for a vertex having no edges (only the sentinel) and whenever adding more edges to a vertex, you must make sure that enough memory was allocated for the block holding the struct.

Also, this idiom has been standarized in C99 as the flexible arrays and the difference is you do not declare the size of the array

 struct vertex {
      struct vertex* edge[];
 }

Upvotes: 0

rodrigo
rodrigo

Reputation: 98338

If you want just one edge per vertex do:

struct vertex *edge;

Or else you can modify your macros (ug? why?) such as:

#define EDGE(vp)  ((vp)->edge[0])

but you probably want the first option, as you seem to be creating the array dynamically.

What you cannot do is to assign to the array itself: either make it a pointer or assign to the (only) element of the array.

Note that the usual idiom in C to create a dynamic array is declaring a plain pointer and make it point to the first element of the dynamic array.

Upvotes: 2

Related Questions