Need a two-dimensional array of "variable" size in a struct

Question

I am attempting to implement a grid of cells, analogous to that of Conway's game of life.

While each individual grid should have fixed size in both dimensions, I would like a Grid struct that allows for any size in both dimensions.

This is in analogy to how arrays can be of any size, but an array once initialized has a fixed size.

This is what I have so far:

typedef struct Cell {
    int data;
    // stuff to be added later
} Cell;

typedef struct Grid {
    unsigned width;
    unsigned height;
    Cell cell[][];
} Grid;

Grid initGrid(unsigned width, unsigned height) {
    Grid g;
    g.width = width;
    g.height = height;
    g.cell = malloc( sizeof(Cell)*width*height );
    return g;
}

However I get the following compile-time error:

main.c|12|note: declaration of `‘cell’ as multidimensional array must have bounds for all dimensions except the first|

How can I define a Grid data type with flexible size?

Post scriptum: as a C newbie, I thought the following would work:

typedef struct Grid {
    unsigned width;
    unsigned height;
    Cell cell[width][height];
} Grid;

Post post scriptum: I am always uneasy whenever I use malloc. Am I doing (or trying to do) anything horribly wrong here?

Answer 1

You can't do it with double indexing (cell[x][y]) in C, there's no way to express that the number of bytes to jump for each row is dynamic.

So, the best (in my opinion) way to do is it to just do the indexing manually, using a one-dimensional array.

Put a plain:

Cell *cell;

in the struct (keeping width and height) and then index like so:

set_cell(Grid *g, unsigned int x, unsigned int y, Cell value)
{
  g->cell[y * g->width + x] = value;
}

it's not unlikely that the compiler will inline this, and it's going to be pretty tight. Probably faster than the jagged array" approach which uses much more memory and another layer of indirection.

Allocation is simple:

Grid initGrid(unsigned int width, unsigned int height)
{
    Grid g;
    g.width = width;
    g.height = height;
    g.cell = malloc(width * height * sizeof *g.cell);
    // add assert or error here, can't return NULL for value type
    return g;
}

if you wanted to heap-allocate Grid too, you could co-allocate it with its elements.

And yes, you need to free() the allocation when you're done with it, in order to not leak memory. Strictly speaking on modern systems the OS will free all resources when the program ends anyway, but it's good form to free anyway:

void destroyGrid(Grid g)
{
  free(g.cell);
}

Answer 2

following this excelent post: How do I work with dynamic multi-dimensional arrays in C? read @JensGustedt post and follow his link variable length arrays (VLAs)

there is actually a way - I followed his post and written a small test program to verify:

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

int main(int argc, char ** argv)
{
    unsigned int height = 100;
    unsigned int width = 10;

    int (*array)[width] = malloc (sizeof(int[height][width]));

    array[90][2] = 1231;
    printf("%d", array[90][2]);
}

---

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

int main(int argc, char ** argv)
{
    unsigned int height;
    unsigned int width;
    int i,j;

    printf("enter width: ");
    scanf("%d", &width);
    printf("enter height: ");
    scanf("%d", &height);
    int (*array)[width] = malloc (sizeof(int[height][width]));

    for (i = 0; i < height; i++ )
        for (j = 0; j < width; j++ )
            array[i][j] = i;

    for (i = 0; i < height; i++ ) {
        for (j = 0; j < width; j++ )
            printf("%d ", array[i][j]);
        printf("\n");
    }
}

---

and the console:

enter width: 10
enter height: 6
0 0 0 0 0 0 0 0 0 0 
1 1 1 1 1 1 1 1 1 1 
2 2 2 2 2 2 2 2 2 2 
3 3 3 3 3 3 3 3 3 3 
4 4 4 4 4 4 4 4 4 4 
5 5 5 5 5 5 5 5 5 5 

---

I'll admit it suprising - I was not aware this exists...

---

EDIT - using structs:

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

typedef struct Cell {
    int data;
    // stuff to be added later
} Cell;

typedef struct Grid {
    unsigned width;
    unsigned height;
    Cell *cell;
} Grid;

Grid initGrid(unsigned width, unsigned height) {
    Grid g;
    g.width = width;
    g.height = height;
    g.cell = malloc( sizeof(Cell[height][width]) );
    return g;
}
int main(int argc, char ** argv)
{
    unsigned int height;
    unsigned int width;
    int i,j;
    Grid test;

    printf("enter width: ");
    scanf("%d", &width);
    printf("enter height: ");
    scanf("%d", &height);
    test = initGrid (width, height);
    Cell (*array)[width] = test.cell;

    for (i = 0; i < height; i++ )
        for (j = 0; j < width; j++ )
            array[i][j].data = i;

    for (i = 0; i < height; i++ ) {
        for (j = 0; j < width; j++ )
            printf("%d ", array[i][j].data);
        printf("\n");
    }
}

console output:

enter width: 20
enter height: 10
0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 
1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 
2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 
3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 
4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 
5 5 5 5 5 5 5 5 5 5 5 5 5 5 5 5 5 5 5 5 
6 6 6 6 6 6 6 6 6 6 6 6 6 6 6 6 6 6 6 6 
7 7 7 7 7 7 7 7 7 7 7 7 7 7 7 7 7 7 7 7 
8 8 8 8 8 8 8 8 8 8 8 8 8 8 8 8 8 8 8 8 
9 9 9 9 9 9 9 9 9 9 9 9 9 9 9 9 9 9 9 9 

there is a casting warning which i did not have time to resolve, but one can implement the idea - just do it cleanly... again it's a POC not an actual program

Answer 3

You are pretty much out of luck here, as there is no way in C to use variable array lengths within a struct definition. What you can do is this:

typedef struct Grid {
    unsigned width, height;
    void* cell_internal;    //Type: Cell(*)[height]
} Grid;

#define cell(myGrid) ((Cell(*)[(myGrid).height])(myGrid).cell_internal)

//in the constructor of Grid
newGrid->width = ...;
newGrid->height = ...;
cell(*newGrid) = malloc(newGrid->width*sizeof(*cell(*newGrid)));
for(unsigned x = 0; x < newGrid->width; x++) {
    for(unsigned y = 0; y < newGrid->height; y++) {
        cell(*newGrid)[x][y] = ...;
    }
}

This is a dirty little hack, but it should work fine. The cool part is, that you can simply address your grid cells with cell(aGrid)[x][y]. The downside is, that it does obscure what is actually going on quite thoroughly. And there are not many people who can actually read what the cell() macro does. (Hint: It simply casts the void* to a pointer to a column array Cell(*)[myGrid.height], whatever myGrid.height may be at that point in time.)

---

Of course, you can go more explicit like this:

typedef struct Grid {
    unsigned width, height;
    void* cell_internal;    //Type: Cell(*)[height]
} Grid;

//in the constructor of Grid
newGrid->width = ...;
newGrid->height = ...;
Cell (*cells)[newGrid->height] = malloc(newGrid->width*sizeof(*cells));
newGrid->cell_internal = cells;
for(unsigned x = 0; x < newGrid->width; x++) {
    for(unsigned y = 0; y < newGrid->height; y++) {
        cells[x][y] = ...;
    }
}

The downside of this approach is, that you will need to explicitly create an alias pointer for the cell_internal pointer in each function that works on the cell data with

Cell (*cells)[myGrid->height] = myGrid->cell_internal;

Probably, this is the better approach, as it would seem to be readable to more people.

Answer 4

Use a flexible array. It's trivial to do with two malloc() calls, and possible to do with just one if you care to push the limits of alignment restrictions or strict aliasing or want to write the code to coerce the alignment of the portion of malloc()'d used to store Cell structures.

typedef struct Grid {
    unsigned width;
    unsigned height;
    Cell *cell[];
} Grid;

Grid *initGrid(unsigned width, unsigned height )
{
    // the Grid structure itself
    size_t bytesNeeded = sizeof( Grid );

    // space for pointers
    bytesNeeded += height * sizeof( Cell * );

    Grid *g = malloc( bytesNeeded );
    g->width = width;
    g->height = height;

    // get all the data needed with one malloc call
    g->cell[ 0 ] = malloc( width * height * sizeof( Cell ) );

    // fill in the pointers
    for ( unsigned ii = 1; ii < height; ii++ )
    {
        g->cell[ ii ] = g->cell[ 0 ] + ii * width;
    }

    return g;
}

void freeGrid( Grid *g )
{
    free( g->cell[ 0 ] );
    free( g );
}

If you don't mind pushing the limits of strict aliasing, you can do it with a flexible array and a single call to malloc() (it's left as an exercise for the reader to coerce the alignment of the data portion so that there's no potential alignment problems - that definitely is possible to do):

typedef struct Grid {
    unsigned width;
    unsigned height;
    Cell *cell[];
} Grid;

Grid *initGrid(unsigned width, unsigned height )
{
    // the Grid structure itself
    size_t bytesNeeded = sizeof( Grid );

    // space for pointers
    bytesNeeded += height * sizeof( Cell * );

    // space for data
    bytesNeeded += width * height * sizeof( Cell );

    Grid *g = malloc( bytesNeeded );
    g->width = width;
    g->height = height;

    // fill in the pointers
    // (technically a strict-aliasing/alignment violation as it assumes
    // that &(g->cell[ height ]) is suitable to store a Cell...)
    for ( unsigned ii = 0; ii < height; ii++ )
    {
        g->cell[ ii ] = ( Cell * ) &(g->cell[ height ]) +
            ii * width;
    }

    return g;
}