1

In the code below, when memory is reallocated with 

g->alist[u] = realloc(g->alist[u], sizeof(struct successors) +
sizeof(int) * (g->alist[u]->len - 1))

how can numbers be added to list[] using 

g->alist[u]->list[g->alist[u]->d++] = v

if it was initialized as list[1]? 

struct graph {
    int n;
    int e;
        struct successors {
            int d;
            int len;
            char is_sorted;
            int list[1];        
         } *alist[1];
};
typedef struct graph *Graph;

Graph graph_create(int n)
{

    Graph g;
    int i;

    g = malloc(sizeof(struct graph) + sizeof(struct successors*) * (n - 1));
    assert(g);
    g->v = n;
    g->e = 0;

    for (i = 0; i < n; i++)
    {
        g->alist[i] = malloc(sizeof(struct successors));
        assert(g->alist[i]);

        g->alist[i]->d = 0;
        g->alist[i]->len = 1;
        g->alist[i]->is_sorted = 1;
    }

    return g;
}

void graph_add_edge(Graph g, int u, int v)
{
    assert(u >= 0);
    assert(u < g->v);
    assert(v >= 0);
    assert(v < g->v);
    while(g->alist[u]->d >= g->alist[u]->len)  
    {
        g->alist[u]->len *= 2;
        g->alist[u] = realloc(g->alist[u], sizeof(struct successors) + 
        sizeof(int) * (g->alist[u]->len - 1));
    }
    g->alist[u]->list[g->alist[u]->d++] = v;
    g->alist[u]->is_sorted = 0;
    g->e++;
}
user3386109
  • 34,287
  • 7
  • 49
  • 68
otan
  • 15
  • 2
  • `alist` is an array of pointers in the `graph` structure. Since it's the last item in the structure, you can allocate more memory to make room for more pointers. `list` is an array of `int`. Since it's the last item in the `successors` structure, you can allocate more memory to make room for more `int`s. – user3386109 Jun 26 '19 at 19:10
  • ... but *neither* of those makes accessing the additional allocated space valid, although it will probably work because it used to be common enough hack, and because it falls out naturally from simple implementations of the language semantics. Additionally, they don't work *together*. – John Bollinger Jun 26 '19 at 19:13
  • 1
    If you want to dynamically allocate or reallocate space then declare a pointer, not an array. – John Bollinger Jun 26 '19 at 19:15
  • 2
    Technically, the flexible array member should be declared without the `1`, e.g. `int list[];` instead of `int list[1];`. That of course affects the size calculations in the `malloc` and `realloc` calls. – user3386109 Jun 26 '19 at 19:19
  • @JohnBollinger In fact, they do work together, since `alist` is an array of pointers. The structure definition is badly written, but the design is correct (provided the arrays are properly declared as flexible array members). – user3386109 Jun 26 '19 at 19:22
  • The structure design isn’t bad; c89 explicitly forbade empty arrays, only to have a later stab at it re-permit them. The only way to make a structure compatible with C and std-C{89, 99, ...} is to use [1]. – mevets Jun 26 '19 at 19:37
  • You may have a look at the following post: [Is using flexible array members in C a bad practice?](https://stackoverflow.com/questions/246977/is-using-flexible-array-members-in-c-bad-practice). Per my understanding, using `[1]` is not fully portable and may cause undesired effects. There are a lot of posts about flexible array members here. – Mance Rayder Jun 26 '19 at 20:16
  • 1
    @mevets no it isn't. The only really compatible way is to use conditional compilation to define a macro that expands to empty string on c99+, 1 on c89 – Antti Haapala -- Слава Україні Jun 27 '19 at 00:31
  • And hope that the c89 compiler in question does not do bounds checking – Antti Haapala -- Слава Україні Jun 27 '19 at 00:32
  • 1
    OT: regarding: `typedef struct graph *Graph;` It is a very poor programming practice to hide a pointer in a 'typedef'. – user3629249 Jun 27 '19 at 13:30

0 Answers0