Array of structs each containing dynamic arrays

Question

I'm somewhat well-versed with C and I thought I had pointers all figured out until I ran into this problem. I'm creating an array-implemented stack of structs. Easy enough, but I'm running into a problem when my struct contains a dynamically allocated array.

The struct is:

typedef struct state {
    int* S;
    double prob;
} state_t;

Now say I'd like to create an array of 10 of those structs, each with an integer array of say 5 integers. I can allocate that array as:

state_t *newContents;
newContents = (state_t *)malloc((sizeof(state_t) + 5 * sizeof(int)) * 10);

And I can create a struct to go in the first slot:

state_t *root = malloc(sizeof *root + 5 * sizeof(int));
root->prob = 1.0;
root->S[0] = 3;
root->S[1] = 5;
root->S[2] = 7;
root->S[3] = 2;
root->S[4] = 0;
newContents[0] = *root;

But when I attempt to add a second struct, Seg fault. It's because the way the array is indexing is by the size of the struct without the int array, meaning each entry is 16 bytes long - 8 for the double + 8 for the pointer. I want it to instead index by 28 - 8 for the double and 4*5 for the ints. Does anyone know a way to access elements of this array correctly?

Thanks!

Answer 1

You're allocating your structs wrong. The struct itself is separate from its dynamically-allocated array and needs to be allocated separately:

// Allocate the structs.
state_t *newContents = malloc(10*sizeof(*newContents));

// Allocate the S array of the first struct.
newContents[0].S = malloc(5*sizeof(int));
newContents[0].S[0] = 3;
...

If you want a struct that actually contains an array of runtime-determined length, rather than pointing to one as your current struct does, you need a flexible array member:

struct state_t {
    double prob;
    int S[]; // No length specified!
};

Then you can malloc(sizeof(state_t) + n*sizeof(int)) and actually get a contiguous block of memory where the struct and its array are together. However, you can't put make an array of state_ts properly if you do this, since the compiler would have no idea where one struct ends and another begins.

Answer 2

Do this:

state_t *newContents;
newContents = malloc(sizeof(state_t)*10);

int i;
for (i=0;i<10;i++)
   (newContents+i)->S=malloc(5 * sizeof(int));

If you want newContents to be an array of structs of size 10, then it should allocate size equal to sizeof(state_t)*10. The int *s within each struct should be allocated explicitly.

Answer 3

Using

1. Arrays of Length Zero and GCC extensions of it
2. proper type casting
3. proper pointer arithmetic

you could get what you want, more or less.

Here is my testing program (compiling with gcc -std=c99):

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

typedef struct state {
    double prob;
    int S[];
} state_t;

int main(void) {
    size_t stateSize;
    state_t *newContents;
    stateSize = sizeof(state_t) + 5*sizeof(int);
    newContents = malloc(stateSize * 10);

    for (int i = 0; i < 10; i++) {
        state_t *state = (state_t *)((char *)newContents + i * stateSize);
        state->prob = i;
        for (int j = 0; j < 5; j++) {
            state->S[j] = i * j;
        }
    }

    for (int i = 0; i < 10; i++) {
        state_t *state = (state_t *)((char *)newContents + i * stateSize);
        printf("[%d] prob: %f\n", i, state->prob);
        for (int j = 0; j < 5; j++) {
            printf("\tS[%d]: %d\n", j, state->S[j]);
        }
    }
}

Run:

$ ./a.out 
[0] prob: 0.000000
    S[0]: 0
    S[1]: 0
    S[2]: 0
    S[3]: 0
    S[4]: 0
[1] prob: 1.000000
    S[0]: 0
    S[1]: 1
    S[2]: 2
    S[3]: 3
    S[4]: 4
[2] prob: 2.000000
    S[0]: 0
    S[1]: 2
    S[2]: 4
    S[3]: 6
    S[4]: 8
[3] prob: 3.000000
    S[0]: 0
    S[1]: 3
    S[2]: 6
    S[3]: 9
    S[4]: 12
[4] prob: 4.000000
    S[0]: 0
    S[1]: 4
    S[2]: 8
    S[3]: 12
    S[4]: 16
[5] prob: 5.000000
    S[0]: 0
    S[1]: 5
    S[2]: 10
    S[3]: 15
    S[4]: 20
[6] prob: 6.000000
    S[0]: 0
    S[1]: 6
    S[2]: 12
    S[3]: 18
    S[4]: 24
[7] prob: 7.000000
    S[0]: 0
    S[1]: 7
    S[2]: 14
    S[3]: 21
    S[4]: 28
[8] prob: 8.000000
    S[0]: 0
    S[1]: 8
    S[2]: 16
    S[3]: 24
    S[4]: 32
[9] prob: 9.000000
    S[0]: 0
    S[1]: 9
    S[2]: 18
    S[3]: 27
    S[4]: 36