How can a double pointer be used for a two dimensional matrix?

Question

I am trying my hand at C by implementing Conway's game of Life.

I am trying to dynamically build two grids (int matrices), one for the current and one for the next generation, so after I determine what the next generation looks like, I just swap pointers.

At first I tried hopelessly to define the pointer to the grid like int * grid, which you cannot subscript with a second set of brackets like [][] because - obviously - the first set of brackets returns an int.

I also tried something like int * grid[HEIGHT][WIDTH], but this gives problems assigning one pointer like this to another. (And in fact, I have no idea what this really does in memory!)

In my naïve hopefulness, I thought the following could work after stumbling across double pointers. The program compiles, but fails when running on the line indicated. (In Windows, I get no more detail other than that the Problem Event Name is APPCRASH).

DISCLAIMER: This is not the actual program, just a proof of concept for the problem.

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

int HEIGHT = 20;
int WIDTH = 20;

int ** curr_gen; // Current generation
int ** next_gen; // Next generation

/* Entry Point main */
int main(int argc, char** argv) {

    // Allocate memory for the grids
    curr_gen = malloc(sizeof (int) * WIDTH * HEIGHT);
    next_gen = malloc(sizeof (int) * WIDTH * HEIGHT);

    curr_gen[0][0] = 0; //<< PROGRAM FAILS HERE

    // Release heap resources
    free(curr_gen);
    free(next_gen);

    return 0;
}

Answer 1

A common way to do this is described in http://c-faq.com/aryptr/dynmuldimary.html

Answer 2

You can simply allocate the space and cast the pointer to the type which defines the col and row sizes. Looking up a pointer via [][] is expensive. And building a dynamic multi dimensional array this way should be reserved for ragid arrays.. IE: only use it when necessary.

You can define a type:

typedef int MyArray[20][20];

And then cast the malloc pointer to the type you want:

MyArray * curr_gen = (MyArray *) malloc(...);

However this assumes that you have a constant, known at compile time height and width. If it must be dynamic then by all means use the index into a pointer table method. But keep in mind that the actual pointer looked up must be loaded at the last possible minute leading to Pipeline stalls, and potential cache misses. Making it 100 times more expensive than just doing the math yourself via [row * 20 + col].

So the real question you should ask yourself is "Does it need to run fast, or do I want the code to look 'Neat'?"

Answer 3

You can just use int* as the type of grid in my way.

Convert the 2D position to 1D by a macro define or a function:

#define MATRIX2INDEX(x, y, width)  ((x) + (y) * (width))  // `width` is the max of x + 1 :)
int Matrix2Index(int x, int y, int width)
{
    return MATRIX2INDEX(x, y, width);
}

Visit the data by 2D position in int*:

int* grid = (int*)malloc(sizeof(int) * WIDTH * HEIGHT);
grid[MATRIX2INDEX(0, 0, WIDTH)] = 0; // here: get the data you want by 2D position
free(grid); grid = NULL;