0

I have been given some code to build upon and I came across a few strange structures:

typedef struct graph_t* Graph;
typedef struct vertex_t* Vertex;

struct vertex_t {
    int id;
    char *label;

    //Implement a way to store edges...
};


struct graph_t {

    /*# vertices...*/
    int order;

    /*# edges...*/
    int size;

    /*Array of vertices...*/
    Vertex vertices;
};

You can probably see this is a way of storing a graph. However, what I'm confused about is the way the "Array of vertices" has been declared: Vertex vertices. There is nothing to indicate that vertices is actually an array, it simply seems like a single vertex (which wouldn't make sense since a graph can have many vertices).

So how can an array be declared in this way and why does this work?

Also, how would I go about initializing(?) the array and how would it be used? In the same way as a normal array?

EDIT: I forgot to add the typedefs and some missing info, it seems the fact that there is a typedef of vertex_t* is what makes this legal?

JavascriptLoser
  • 1,853
  • 5
  • 34
  • 61
  • 4
    Simple: It's not an array. Just because the comment says its an array does not mean it's an array. – ckruczek Mar 22 '16 at 09:56
  • @ckruczek If this is the case, how can it be used as an array (as the developer intended)? – JavascriptLoser Mar 22 '16 at 09:57
  • 3
    It can't. It is not an array and can not be used like an array. – ckruczek Mar 22 '16 at 09:58
  • possibly the comment "// Implement a way to store edges" will be replaced by code that manages a dynamic array. Although calling an array of vertices "Vertex" is strange. Perhaps they intend you to figure out to change `Vertex vertices;` to actually be an array of `Vertex`. – M.M Mar 22 '16 at 09:58
  • there is a thing like [variable-length arrays](http://stackoverflow.com/questions/11733981/what-is-the-purpose-of-a-zero-length-array-in-a-struct) that can be last of structs. however, this is not it, so it's either a bug, or a misleading comment – sp2danny Mar 22 '16 at 09:58
  • 3
    @sp2danny that is *flexible array member*, not variable-length array – M.M Mar 22 '16 at 09:59
  • 1
    The comment is probably means that `vertices` is intended to be used as an array of `vertex_t` structs. Arrays in C often decay into pointers. See http://www.c-faq.com/aryptr/aryptrequiv.html – jamesdlin Mar 22 '16 at 11:14
  • @jamesdlin How would I go about using `vertices` as an array as intended? Do I need to initialize it like normal or is there a special technique I need to follow? – JavascriptLoser Mar 22 '16 at 11:16
  • 1
    You need to initialize `vertices` to point to something, most likely to a buffer dynamically allocated with `malloc`. – jamesdlin Mar 22 '16 at 11:18
  • Would putting a function inside the vertex_t structure be a way to implement this? (Actually a pointer to a function as I don't think you can put a function directly in a structure) – anita2R Mar 22 '16 at 11:24

3 Answers3

1

There is an extremely bad technique that this might be a prologue to. That would involve first allocating a suitably large chunk of memory, and casting it to struct vertex_t.

For example:

size_t size = sizeof(struct vertex_t) + 1000 * sizeof(Vertex);
struct vertex_t* memory = (struct vertex_t *) malloc(size);
Vertex* array = &memory->vertices;

Now array should be able to take subscripts from [0] to [1000] without getting a memory error. But just because you can do it doesn't mean you should. This is a horrible technique and I can't say enough bad things about it. Don't do it. But it may be where the original author of the code was going.

Logicrat
  • 4,438
  • 16
  • 22
  • 1
    Outside of horrible, its also horrible to debug and has completly garbage readability. – Magisch Mar 22 '16 at 10:08
  • @PythonNewb Yes, your edit (which clarifies that `Vertex` is a typedef for `vertex_t*`, not the type of a `struct` itself changes almost everything. (The code is still bad from a readability point, but it is at least legal now.) – jamesdlin Mar 22 '16 at 11:10
  • @jamesdlin Should I create a new question because of the face that everything has been changed or should I wait here for new answers? – JavascriptLoser Mar 22 '16 at 11:11
  • What do you propose as an alternative? And I do not agree that it is as horrible as you are making out, and the technique you outline is not the only way of allocating space such that the pointer can be used as the starting address of an array of vertices. – Jonathan Leffler Mar 22 '16 at 12:35
1

After the post edited, you still have to malloc() a block of memory to every vertices and label on initialization. For example:

Graph newGraph(size_t n, size_t labelPerVertex)
{
    Graph aGraph = malloc(sizeof (struct graph_t));
    aGraph->vertices = malloc(sizeof (struct vertex_t) * n); // n Vertices
    size_t i;
    for(i = 0; i < n; i++)
        aGraph->vertices[i].label = malloc(labelPerVertex); // array of labelPerVertex chars for every vertex
    return aGraph;
}
nalzok
  • 14,965
  • 21
  • 72
  • 139
  • 1
    @PythonNewb It's still pretty bad. The crux of the problem is that the `vertices` member in `struct graph_t` should be declared as a pointer to Vertex (i.e. `Vertex* vertices`) for an array whose size can be set at runtime, or else it should be declared as `Vertex[someConstant] vertices` for an array whose maximum size is known at compile time. – Logicrat Mar 22 '16 at 12:27
  • @PythonNewb I agree with Logicrat. The former is preferred by myself because you may accidentally return a pointer to a local variable in the later case. – nalzok Mar 22 '16 at 12:49
  • @PythonNewb answer updated, hope this is what you want – nalzok Mar 22 '16 at 13:03
0
/*Array of vertices...*/
Vertex vertices;

The comment is incorrect. It is not an array. It cannot be used as an array of Vertex, because it is not one.

Maybe the implementation notice will be replaced with something that makes Vertex itself into an array of vertices, but that would make the comment still ambigous at best.

Magisch
  • 7,312
  • 9
  • 36
  • 52