type of bool** is incompatible with type bool*[4]

Question

I'm working on a pathfinding library for fun and to become more familiar with C, and I have no idea what's causing this error or how to fix it. Why are the types of bool** and bool*[4] not compatible? Is there a work around for this or is there a better way of going about this problem?

#include <stdbool.h>
#include <stdlib.h>

int * A_Star_SolveUnweighted(bool **graph) {

}

int main() {
    bool graph[5][4] = {{0, 0, 0, 0}, {0, 0, 0, 0}, {0, 0, 0, 0}, {0, 0, 0, 0}, {0, 0, 0, 0}};
    
    int *path = A_Star_SolveUnweighted(graph);


    return 0;
}

Answer 1

The following are different types, with only the one relationship noted between them:

• bool graph[5][4] is an array of five arrays of 4 bool. In many uses, it will be automatically converted to a pointer to an array of 4 bool.
• bool (*)[4] is a pointer to an array of 4 bool. It is the result of the above conversion.
• bool *[4] is an array of 4 pointers to bool. It has no relation to bool (*)[4].
• bool ** is a pointer to a pointer to a bool. It is not an array or a pointer to an array.

The routine is declared to take a bool **. Passing it graph results in an argument of type bool (*)[4], due to the automatic conversion. These are not compatible types, so the compiler complains. The argument type, bool (*)[4], points to where there are 4 bool (and additional subarrays of 4 bool after it). The parameter type, bool **, requires something that points to where there is a pointer. Since 4 bool and a pointer are very different things, these types are not compatible.

To resolve the issue, you might change the declaration of A_Star_SolveUnweighted to be int *A_Star_SolveUnweighted(bool (*graph)[4]) or int *A_Star_SolveUnweighted(size_t Columns, bool (*graph)[Columns]).

Answer 2

bool graph[5][4] is an array of arrays. It's represented by, effectively, 20 Booleans in a row (possibly with some padding). It can be decayed into bool(*)[4], which is a pointer to some number of collections of four Booleans in a row.

On the other hand, bool** is a pointer to one or more pointers to one or more Booleans. There's an additional layer of indirection, in that the first array contains pointers to the second, as opposed to simply containing the second directly. At the top layer, it's easy to convert from T[] to T*, since that's effectively just taking an address, but if it's not the top layer of the array, then it would require iterating over the array to change all of the constituents. And that's more or less what you need; an array of pointers.

bool** graph = calloc(5, sizeof(bool*))
for (int i = 0; i < 5; i++) {
  graph[i] = calloc(4, sizeof(bool));
  // Initialize graph[i] here ...
}

Then you'll need to free it all at the end.

for (int i = 0; i < 5; i++) {
  free(graph[i]);
}
free(graph);

Of course, if you have control over the signature of the target function, you may consider just changing it to take a bool*. Then you can work with one-dimensional arrays and just keep track of the number of "rows" and "columns", which will better align your memory and avoid issues like this.