Flexible array of flexible arrays in C

Question

Is it possible to use nested flexible arrays (flexible array of flexible arrays) in C?

I tried the following code to test flexible arrays:

#include <stdlib.h>
#include <stdio.h>

typedef struct {
    int x;
    int y;
} node;

typedef struct {
    int len;
    node elem[];
} cell;

int cell_size = 3;

int main(void) {
    cell *set = malloc(sizeof *set + cell_size * sizeof set->elem[0]);
    set->len = cell_size;

    for (int j = 0; j < cell_size; j++) {
        set->elem[j].x = j;
        set->elem[j].y = j * 10;
    }

    printf("set size: %d\n", set->len);
    for (int j = 0; j < cell_size; j++) {
        printf("x: %d, ", set->elem[j].x);
        printf("y: %d\n", set->elem[j].y);
    }

    return 0;
}

The output is:

set size: 3
x: 0, y: 0
x: 1, y: 10
x: 2, y: 20

Here everything is fine as expected. Allocated space for set is 28 bytes.

But when I tried to modify this code like this to put flexible array inside other array:

#include <stdlib.h>
#include <stdio.h>


typedef struct {
    int x;
    int y;
} node;


typedef struct {
    int len;
    node elem[];
} cell;


typedef struct {
    int len;
    cell group[];
} obj;


int cell_size = 3;
int obj_size = 4;

int main(void) {

    obj *set = malloc(
        sizeof *set + obj_size * sizeof (
        sizeof (cell) + cell_size * sizeof(node)
    ));
    set->len = obj_size;

    for (int i = 0; i < obj_size; i++) {
        set->group[i].len = cell_size;
        for (int j = 0; j < cell_size; j++) {
            set->group[i].elem[j].x = j;
            set->group[i].elem[j].y = j * 10 + i;
        }
    }

    printf("set size: %d\n", set->len);
    for (int i = 0; i < obj_size; i++) {
        printf("group size: %d\n", set->group[i].len);
        for (int j = 0; j < cell_size; j++) {
            printf("x: %d, ", set->group[i].elem[j].x);
            printf("y: %d\n", set->group[i].elem[j].y);
        }
    }

    return 0;
}

Allocated space for set is 20 bytes and the output is wrong:

set size: 4
group size: 3
x: 3, y: 3
x: 3, y: 0
x: 3, y: 1
group size: 3
x: 3, y: 3
x: 0, y: 3
x: 1, y: 13
group size: 3
x: 3, y: 0
x: 3, y: 1
x: 13, y: 2
group size: 3
x: 0, y: 3
x: 1, y: 13
x: 2, y: 23

Even if I set malloc manually to any reasonable value the output is still incorrect. I think this is because the compiler don't know the size of group[] member in the top structure (obj). However I didn't get any compiler errors or warnings (GCC 6.3.0).

And I don't know how to set this size and make compiler process this code correctly.

this looks fishy: `sizeof ( sizeof (cell) + cell_size * sizeof(node))` — Christian Gibbons, Feb 20 '19 at 21:09
The FAM is not included in the size of the structure. So when you're indexing the `group` array, it won't include the size of the `elem` array in the nested `cell`. — Barmar, Feb 20 '19 at 21:14
@ChristianGibbons Yes, may be this calculation is incorrect, but the problem is not allocation, but incorrect behavior of code. Even if I set `malloc(10000)` the output is still incorrect. — cyclone125, Feb 20 '19 at 21:16
@Barmar So, there is no way to make nested flexible arrays working? Something similar? — cyclone125, Feb 20 '19 at 21:18
Add `-pedantic` warnings `"warning: invalid use of structure with flexible array member - cell group[];"` — David C. Rankin, Feb 20 '19 at 21:21
Trying to map a single contiguous block of memory to a complex set of nested structures is not the sort of thing you find in the average C program. And seems like an optimization, and difficult to maintain. If you want to understand what's going on here, check out the addresses of the various structures, arrays, and elements, relative to the address returned from malloc. These addresses won't line up with what your expectation is. And you will see what is actually happening in memory. — Tom Drake, Feb 20 '19 at 21:24
Suggest `typedef struct { int len; cell group[]; } obj;` --> `typedef struct { int len; cell *group[]; } obj;` ( --> `*` and adjust code accordingly.) — chux - Reinstate Monica, Feb 21 '19 at 02:19

score 2 · Answer 1 · answered Feb 20 '19 at 21:25

2

Correct ... there is no way to make "nested flexible arrays".

All members of an array must have the same size. You must have

sizeof arr[i] == sizeof arr[j]

For all i, j within array boundaries.

answered Feb 20 '19 at 21:25

pmg

106,608
13
126
198

David C. Rankin · Accepted Answer · 2019-02-20T22:45:24.437

Structures with flexible array members cannot be used as members to another structure or in an array. You can only have one FAM. Otherwise, if you attempt to declare an array of FAM, each FAM member of the array of struct would point to a memory location between adjacent array members -- giving you the incorrect overwritten results you see.

For a complete discussion on the C-Standard Sections applicable see: How does an array of structures with flexible array members behave?

"So, there is no way to make nested flexible arrays working?"

Answer: NO

That would violate C11 Standard - 6.7.2.1 Structure and union specifiers(p3)

"Something similar?"

Answer: Yes

All you need to do is make node elem[]; node *elem; and then allocate cell_size * sizeof (node) bytes per set->group[i].elem, e.g.

typedef struct {
    int len;
    node *elem;
} cell;
...
    obj *set = malloc (sizeof *set + obj_size * sizeof (cell));
    ...
    for (int i = 0; i < obj_size; i++) {
        set->group[i].len = cell_size;
        set->group[i].elem = malloc (cell_size * sizeof (node));

That will allocate cell_size * sizeof (node) for each set->group[i].elem doing what you want, e.g.

#include <stdlib.h>
#include <stdio.h>

typedef struct {
    int x;
    int y;
} node;

typedef struct {
    int len;
    node *elem;
} cell;


typedef struct {
    int len;
    cell group[];
} obj;


int cell_size = 3;
int obj_size = 4;

int main (void) {

    obj *set = malloc (sizeof *set + obj_size * sizeof (cell));
    set->len = obj_size;

    for (int i = 0; i < obj_size; i++) {
        set->group[i].len = cell_size;
        set->group[i].elem = malloc (cell_size * sizeof (node));
        for (int j = 0; j < cell_size; j++) {
            set->group[i].elem[j].x = j;
            set->group[i].elem[j].y = j * 10 + i;
        }
    }

    printf("set size: %d\n", set->len);
    for (int i = 0; i < obj_size; i++) {
        printf("group size: %d\n", set->group[i].len);
        for (int j = 0; j < cell_size; j++) {
            printf("x: %d, ", set->group[i].elem[j].x);
            printf("y: %d\n", set->group[i].elem[j].y);
        }
        free (set->group[i].elem);
    }

    free (set);

    return 0;
}

Example Use/Output

$ ./bin/fam_array2
set size: 4
group size: 3
x: 0, y: 0
x: 1, y: 10
x: 2, y: 20
group size: 3
x: 0, y: 1
x: 1, y: 11
x: 2, y: 21
group size: 3
x: 0, y: 2
x: 1, y: 12
x: 2, y: 22
group size: 3
x: 0, y: 3
x: 1, y: 13
x: 2, y: 23

Memory Use/Error Check

$ valgrind ./bin/fam_array2
==7686== Memcheck, a memory error detector
==7686== Copyright (C) 2002-2015, and GNU GPL'd, by Julian Seward et al.
==7686== Using Valgrind-3.12.0 and LibVEX; rerun with -h for copyright info
==7686== Command: ./bin/fam_array2
==7686==
set size: 4
group size: 3
x: 0, y: 0
x: 1, y: 10
x: 2, y: 20
group size: 3
x: 0, y: 1
x: 1, y: 11
x: 2, y: 21
group size: 3
x: 0, y: 2
x: 1, y: 12
x: 2, y: 22
group size: 3
x: 0, y: 3
x: 1, y: 13
x: 2, y: 23
==7686==
==7686== HEAP SUMMARY:
==7686==     in use at exit: 0 bytes in 0 blocks
==7686==   total heap usage: 5 allocs, 5 frees, 168 bytes allocated
==7686==
==7686== All heap blocks were freed -- no leaks are possible
==7686==
==7686== For counts of detected and suppressed errors, rerun with: -v
==7686== ERROR SUMMARY: 0 errors from 0 contexts (suppressed: 0 from 0)

Look things over and let me know if you have further questions.

Flexible array members are neither static or `static`. Each flexible array member must be the last member of a structure with at least one other member, but there is no reason you cannot have many of them in a translation unit. (Is that what you meant by “compilation unit”?) And, if somebody attempts to construct an array of structures containing flexible array members, there is no reason they would all “point” to the same address. If anything, the flexible array member would be near (plus or minus some padding) the beginning of the next structure, not its last member. — Eric Postpischil, Feb 20 '19 at 22:20
Now we may be talking about the same thing with different terminology. If you have `struct foo { int a; int fam[]; }` you cannot declare an array of `foo` because `fam` will have the same address. While not technically `static` the behavior is the same. I'll look for the SO link that discussed this in detail. [How does an array of structures with flexible array members behave?](https://stackoverflow.com/questions/36118536/how-does-an-array-of-structures-with-flexible-array-members-behave) — David C. Rankin, Feb 20 '19 at 22:24
@EricPostpischil alright, I think I've taken care of the terminology and the effect of where declaring an array of a stuct with a FAM would cause the arrayed FAM members to point. Not the "same" location, the "same" location relative to each array element (ending up between adjacent array elements containing the FAM). — David C. Rankin, Feb 20 '19 at 22:49
@DavidC.Rankin Thank you, the code works fine. I appreciate your answer. — cyclone125, Feb 22 '19 at 01:25

Serge Ballesta · Answer 3 · 2019-02-21T07:42:35.007

You cannot have flexible array of a objects whose size is not known at compile time. And the size of a struct having a flexible array member is not. The only thing that is known is its size without the flexible member.

But in your use case, all the flexible arrays will have the same size, even it is only known at run time. So you can replace the flexible array of the inner struct with a pointer, allocate enough space for the struct including its flexible array plus enough space for all the nodes and assign the pointers in that free space. Code could be:

#include <stdlib.h>
#include <stdio.h>


typedef struct {
    int x;
    int y;
} node;


typedef struct {
    int len;
    node *elem;
} cell;


typedef struct {
    int len;
    cell group[];
} obj;


int cell_size = 3;
int obj_size = 4;

int main(void) {

    obj *set = malloc(
        sizeof *set + obj_size * (
            sizeof(cell) + cell_size * sizeof(node)
            ));
    set->len = obj_size;

    // nodes will exist in the allocated buffer after the cells
    node *node_start = (node *)(((char *) set) + sizeof *set + obj_size * sizeof(cell));

    for (int i = 0; i < obj_size; i++) {
        set->group[i].len = cell_size;
        // assign the elem pointers in the free space
        set->group[i].elem = node_start + i * cell_size;
        for (int j = 0; j < cell_size; j++) {
            set->group[i].elem[j].x = j;
            set->group[i].elem[j].y = j * 10 + i;
        }
    }

    printf("set size: %d\n", set->len);
    for (int i = 0; i < obj_size; i++) {
        printf("group size: %d\n", set->group[i].len);
        for (int j = 0; j < cell_size; j++) {
            printf("x: %d, ", set->group[i].elem[j].x);
            printf("y: %d\n", set->group[i].elem[j].y);
        }
    }
    free(set);
    return 0;
}

Flexible array of flexible arrays in C

3 Answers3