Multidimensional arrays in structs memory allocation for unknown sizes

Question

I want to be able to use a struct where a member is a 2-dimensional array, and the struct is stored on the heap.

typedef struct Map
{
    int xSize;
    int ySize;
    int mapMatrix[][];
} Map;

My IDE (VS Code, with the C/C++ MS extension) says that I may not have an array with elements of that type. I don't know what the sizes of the array dimensions (not fixed to a specific size), so I can't around it like that.

I've thought of instead using:

typedef struct Map
{
    int xSize;
    int ySize;
    int *mapMatrix[]; // or potentially 'int **mapMatrix;'?
} Map;

but I'm not certain how I would need to allocate the memory for this array (would there be overhead for the pointers more so than a typical 2D array?) I also want to initialise the memory to 0s, so I would be using the calloc function.

Thank you for any help.

EDIT: After having looked at the suggestions, I like the idea of using utility functions to interact with the map struct, and implementing the matrix as a single dimensional array (suggested by Joop Eggen) with specific indexing functions.

What I have now is (ignore the mapGenerationFunction parameter, and not worrying yet about the verification of allocation):

typedef struct Map
{
    size_t rowSize;
    size_t columnSize;
    int *mapMatrix;
} Map;

Map *initialiseMap(size_t rowSize, size_t columnSize,
                   void (*mapGenerationFunction)(Map *));
size_t getRowSize(Map *map);
size_t getColumnSize(Map *map);
void setMapPosition(Map *map, int row, int column, int value);
int isPositionEmpty(Map *map, int row, int column);

Map *initialiseMap(size_t rowSize, size_t columnSize,
                   void (*mapGenerationFunction)(Map *))
{
    Map *map = (Map *)malloc(sizeof(Map));
    map->rowSize = rowSize;
    map->columnSize = columnSize;
    map->mapMatrix = (int *)calloc(rowSize * columnSize, sizeof(int));
    return map;
}

size_t getRowSize(Map *map)
{
    return map->rowSize;
}
size_t getColumnSize(Map *map)
{
    return map->columnSize;
}
void setMapPosition(Map *map, int row, int column, int value)
{
    map->mapMatrix[row * getRowSize(map) + column] = value;
}
int isPositionEmpty(Map *map, int row, int column)
{
    return map->mapMatrix[row * getRowSize(map) + column];
}

would this be considered acceptable?

Also, I notice that Lundin has used Map* map = calloc(1, sizeof *map + sizeof(int[x][y])); - how would I get the pointer to the first address space of the array here?

Answer 1

There always will be a tradeoff between allocation complexity and access speed.

You have two options:

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

/**
 * @struct Map
 * @brief A structure to represent a 2D map with dynamic dimensions.
 *
 * This struct contains the dimensions of the map and a flexible array member
 * for storing the map data.
 */
typedef struct Map
{
    size_t xSize;      /**< The number of columns in the map. */
    size_t ySize;      /**< The number of rows in the map. */
    int mapMatrix[];   /**< Flexible array member for storing map data. */
} Map;

/**
 * @brief Allocates a Map structure with a flexible array sized based on xSize and ySize.
 * 
 * This function allocates memory for a `Map` structure, including the variable-length 
 * `mapMatrix` array with `xSize * ySize` elements. It also initializes the map dimensions.
 * 
 * @param xSize The number of columns.
 * @param ySize The number of rows.
 * @return A pointer to the allocated `Map` structure, or `NULL` if allocation fails.
 */
Map *allocate(size_t xSize, size_t ySize)
{
    // Allocate memory for the Map structure, including space for the 2D array data.
    Map *map = malloc(sizeof(*map) + sizeof(map->mapMatrix[0]) * xSize * ySize);

    // Initialize map dimensions if allocation succeeded.
    if (map)
    {
        map->xSize = xSize;
        map->ySize = ySize;
    }
    return map;
}

/**
 * @def ACCESS(map)
 * @brief Macro to simplify accessing `mapMatrix` as a 2D array.
 *
 * This macro casts `mapMatrix` to a pointer to an array of integers,
 * allowing 2D indexing with `[row][column]` syntax.
 * 
 * @param map Pointer to the `Map` structure.
 * @return A pointer to an array of `int`, which can be indexed as a 2D array.
 */
#define ACCESS(map) ((int (*)[map->xSize])((map)->mapMatrix))

/**
 * @brief Main function demonstrating the use of the `Map` structure.
 *
 * This function allocates a `Map` structure, accesses and modifies an element
 * using the `ACCESS` macro, and then frees the allocated memory.
 * 
 * @return `0` on successful execution.
 */
int main(void)
{
    // Allocate a map with dimensions 40x50.
    Map *m = allocate(40, 50);

    // Use the ACCESS macro to access and set an element in the mapMatrix.
    ACCESS(m)[10][20] = 10;

    // Print the element to verify it was set correctly.
    printf("%d\n", ACCESS(m)[10][20]);

    // Free the allocated map memory.
    free(m);
}

or with more complicated allocation and deallocation:

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

/**
 * @struct Map
 * @brief A structure to represent a 2D map with dynamic dimensions.
 *
 * This struct contains the dimensions of the map and an array of pointers for each row
 * in the map, allowing dynamic allocation of each row individually.
 */
typedef struct Map
{
    size_t xSize;        /**< The number of columns in the map. */
    size_t ySize;        /**< The number of rows in the map. */
    int *mapMatrix[];    /**< Array of pointers, each pointing to a row in the map. */
} Map;

/**
 * @brief Allocates a `Map` structure and dynamically allocates each row.
 * 
 * This function allocates memory for a `Map` structure, including an array of pointers
 * for each row and dynamic allocation of memory for each row individually.
 * 
 * @param xSize The number of columns in each row.
 * @param ySize The number of rows.
 * @return A pointer to the allocated `Map` structure, or `NULL` if allocation fails.
 */
Map *allocate(size_t xSize, size_t ySize)
{
    // Allocate memory for the Map structure and space for row pointers.
    Map *map = malloc(sizeof(*map) + sizeof(map->mapMatrix[0]) * ySize);

    // If allocation succeeded, initialize dimensions and allocate rows.
    if (map)
    {
        map->xSize = xSize;
        map->ySize = ySize;
        
        for (size_t y = 0; y < ySize; y++)
        {
            // Allocate memory for each row with `xSize` elements.
            map->mapMatrix[y] = malloc(sizeof(map->mapMatrix[0][0]) * xSize);
            if (!map->mapMatrix[y])
            {
                // Handle memory allocation error for a row.
                /* Error handling code */
            }
        }
    }
    return map;
}

/**
 * @brief Frees the dynamically allocated memory in a `Map` structure.
 *
 * This function deallocates the memory for each row in `mapMatrix`, then
 * frees the `Map` structure itself.
 * 
 * @param map A pointer to the `Map` structure to be deallocated.
 */
void destroy(Map *map)
{
    if (map)
    {
        // Free each dynamically allocated row.
        for (size_t y = 0; y < map->ySize; y++)
        {
            free(map->mapMatrix[y]);
        }
    }
    // Free the Map structure itself.
    free(map);
}

/**
 * @brief Main function demonstrating the use of the `Map` structure.
 *
 * This function allocates a `Map` structure, accesses and modifies an element
 * in the map, and then frees the allocated memory.
 * 
 * @return `0` on successful execution.
 */
int main(void)
{
    // Allocate a map with dimensions 40x50.
    Map *m = allocate(40, 50);

    // Set an element in the mapMatrix and print it to verify.
    m->mapMatrix[10][20] = 20;
    printf("%d\n", m->mapMatrix[10][20]);

    // Free the allocated map memory.
    destroy(m);
}

Side note - use size_t type for sizes.

Answer 2

Look at the data layout

The most important aspect is that [][] is ambiguous to the actual data structures at disposal.

An array of int pointers allows to store non-square "matrices".

*-> [ * ; * ; * ]
      |   |   |
      +---|---|--------->  [ 1 ; 2 ; 3 ]
          +---|--------->  [ 4 ; 5 ]
              +--------->  [ 6 ; 7 ; 8 ; 9 ]

The access happens in two steps and for the second index one would need some bound information.

Your usage of "matrix" seems to indicate a rectangular grid.

*----> [ 1   2   3   4
         5   6   7   8
         9  10  11  12 ]

Here much less allocations are needed and access is direct. And copying is a single memcpy.

The compiler can realize such things with fixed bounds: int m[3][4]; or int m[3][];. For dynamic bounds the easiest would be to make the second one dimensional int[] and convert a (i, j) coordinate pair to a single linear index.

For clarity (that it is no ordinary vector) you might use int*.

Answer 3

There is no elegant solution for 2D flexible array members. Common work-arounds to deal with this is to either use a 1D array but access it through index arithmetic or otherwise cast to a pointer to a 2D before access:

typedef struct
{
    int xSize;
    int ySize;
    int matrix[];
} Map;

Map* map = calloc(1, sizeof *map + sizeof(int[x][y]));
...

map->matrix[i*x + j] = ... ;

//or alternatively:
int (*arr)[map->ySize] = (void*)map->matrix;
arr[i][j] = ...;