0

I am making a minesweeper program in C.

I have this as a global variable:

typedef struct box_t
{
  int box_type;
  int num_mines_bordering;
  int is_flagged;
} box_t;

// my global
box_t * gameboard = NULL;

Later in the application it is allocated in the heap based on the number of rows and columns:


gameboard = (box_t *)malloc((rows * cols) * sizeof(box_t));

All is well, however, they way I index it now seems incorrect and error-prone. I can't simply do gameboard[x][y] because I get compiler errors and what I have now seems incorrect:

#define GET_LOC(ROW, COL) gameboard[(ROW * sizeof(box_t)) + (COL * sizeof(box_t)) * sizeof(box_t)]
// if you call this it would look like: box_t * loc = &GET_LOC(somerow, somecol);

Is there a better way to index it?

trincot
  • 317,000
  • 35
  • 244
  • 286
raging-loon
  • 19
  • 5
  • 2
    Using `sizeof(box_t` is bound to be wrong. You need `#define GET_LOC(r, ncols, c) (gameboard[(r) * (ncols) + (c)])` or something similar — you multiply the row number `r` by the number of columns in one row `ncols` and add the column number `c`. – Jonathan Leffler Nov 21 '22 at 01:22
  • 2
    See [**Correctly allocating multi-dimensional arrays**](https://stackoverflow.com/questions/42094465/correctly-allocating-multi-dimensional-arrays) – Andrew Henle Nov 21 '22 at 01:27
  • @AndrewHenle Lundin's write-up is great but I am kinda scared of VLAs in production code as they don't gracefully fail when out of stack space. I don't think you can tell gcc to disallow vla allocation but allow vla pointers in function calls. – Allan Wind Nov 21 '22 at 01:33
  • 2
    @AllanWind VLAs are not limited to being on the stack. – Andrew Henle Nov 21 '22 at 01:35
  • Suggest making `gameboard` a `struct` with all the pertinent information, `struct { size_t x, y; struct box_t *box; } gameboard` or `box[]` (FAM). – Neil Nov 21 '22 at 01:35
  • @AndrewHenle Sorry, if I am not clear. What I am getting at is that I would like a gcc feature to disable VLA stack allocations due to possible overflow but allow heap allocation and allow function argument syntax. AFAIK, the only flag is -Wvla which disallows any VLA use. Hmm... I should probably just use `-Wvla-larger-than=`. – Allan Wind Nov 21 '22 at 01:39
  • Don't define your own types ending in `_t`; these are reserved for the implementation by POSIX, and defining your own is undefined behavior in a POSIX application. – JohnScott Nov 21 '22 at 01:59
  • You could use a pointer to VLA. `box_t (*gameboard)[cols] = calloc(rows, sizeof *gameboard);`. It **will not** allocate any memory on stack. All memory **will** be heap allocated. The problem is that `gameboard` could not be a global variable because VLA **types** cannot be defined at file scope. – tstanisl Nov 21 '22 at 13:41
  • @AllanWind The key here is _pointer_ to VLA, which in turn can point at any array no matter where it was allocated and no matter if it's a VLA or static sized. Actual stack-allocated VLA should be avoided in a lot of cases and in this case they want heap allocation anyway. Also, pointer to VLA will once again become a mandatory feature in C23. The main advantage of pointer-to-VLA over "mangled" arrays as in your answer is _increased_ type safety, both by the C compiler and through static analysers if such are used. – Lundin Nov 21 '22 at 14:04
  • @Lundin I understand that. The issue is that `gcc -Wvla` will generate a waring for either use case, and I would like the pointer/head benefit but still catch a (large) stack allocation. – Allan Wind Nov 21 '22 at 17:02
  • 1
    @AllanWind I don't really see how someone would declare a large VLA by accident, or why a VLA in that case would be more dangerous than a static array. Either you have `int array[n];` or you have `int array[n];`... the only difference is that for a VLA `n` could be another variable but in case of a local array it has to be an integer constant expression. And either could cause stack overflows just as easily. – Lundin Nov 21 '22 at 19:31
  • @Lundin I think of a static array as a compile-time thing, it either works or blows up, while a VLA might blow at any time based on run-time input. Maybe I am just being overly paranoid. – Allan Wind Nov 21 '22 at 21:52
  • @AllanWind No that's wrong. A local array with static size is allocated on the stack, in run-time, just as a VLA. Either will blow up in run-time in case it causes stack overflow. – Lundin Nov 22 '22 at 12:05

2 Answers2

2

The compiler knows the type and hence the size of each array entry, so the only special thing is the number of columns cols:

box_t *gameboard = malloc((rows * cols) * sizeof(*gameboard));
gameboard[row * cols + col] = ...;
Allan Wind
  • 23,068
  • 5
  • 28
  • 38
1

You could use Variably Modified Type (VMT) (i.e. a pointer to VLA). The issue is that this type cannot be defined at file scope. The simplest solution is using void* for a global variable and VMT for a local, properly typed view.

void* gameboard_glob = NULL;
int gameboard_rows, gameboard_cols;

void allocate(int rows, int cols) {
  gameboard_rows = rows;
  gameboard_cols = cols;
  gameboard_glob = malloc(sizeof(box_t[rows][cols]);
}

void foo(void) {
  box_t (*gameboard)[gameboard_cols] = gameboard_glob;

  .. do stuff with `gameboard[r][c]`
}

Alternatively, one can do allocation and convenient initialization with:

box_t (*gameboard)[cols] = calloc(rows, sizeof *gameboard);

... initialize with gameboard[r][c]

gamebard_glob = gameboard;

The memory is freed with simple free(gamebard_glob).

Note that this type of VLA does not allocate any memory on stack. All the memory is allocated from heap with malloc/calloc. Moreover, the number of rows can be changed with realloc. This solution requires any C99 compliant compiler what includes pretty much any mainstream compiler except infamous MSVC.

tstanisl
  • 13,520
  • 2
  • 25
  • 40
  • 1
    "The issue is that this type cannot be defined at file scope" One cheeky trick that can be used: `typedef struct { size_t rows; size_t cols; gameboard board[]; } box_t;` Now instead of using `board` as a flexible array member, cast it to `gameboard(*)[obj.cols]` whenever it is used. This is a decent compromise between setting size at compile- vs run-time. It can be taken further by making the struct opaque and hide away the casting inside private encapsulation. – Lundin Nov 21 '22 at 14:10
  • @Lundin, yes.. it can be done this way. Though I would prefer using `struct { size_t rows; size_t cols; box_t (*board)[]; } gameboard_t;`. Let the struct contain a pointer to incomplete array type and pass all instances of `gameboard_t` by value if possible to avoid extra indirection. – tstanisl Nov 21 '22 at 14:18
  • Well if you use a pointer to incomplete array type it is compatible to any array with same item type. That can be both an advantage or a disadvantage, depending on if you are looking for increased type safety or convenient assignments without casts. – Lundin Nov 21 '22 at 14:21
  • @Lundin, yes.. there is a trade-off. The C standard should provide some way to somehow use VMTs in the structures. I am aware of multiple complication which it may introduce. – tstanisl Nov 21 '22 at 14:25