C Pointer to Pointer Problems in Matrix Function

xmalloc() returns a void * pointer to single block of memory. What you need is one block of pointers, serving as an conceptual table header row, holding pointers to other memory blocks which themselves contain the actual doubles.

double **columns -> [double *col0]     [double *col1]     [double *col2] ...
                           |                  |                  |
                           V                  V                  V
                    [double col_val0]  [double col_val0]       ...
                    [double col_val1]  [double col_val1]
                    [double col_val2]  [double col_val2]
                       ...                   ...

A matrix allocation could look like this:

// Allocate the double pointer array:
double **matrix_rows = xmalloc(sizeof(double *) * column_count);

// Iterate over each double-pointer in the double-pointer-array allocated above.
for(int i = 0;  i < column_count; i++) {
    // Allocate a new double-array, and let current double-pointer point to it:
    matrix_rows[i] = malloc(sizeof(double) * row_count);

    // Initialize matrix cell, iterating over allocated values.
    for(int j = 0; j < row_count; j++) {

        // Accessing the i'th col and j'th cell.
        matrix_rows[i][j] = 0.0;
    }
}

A possible implementation of a matrix copy function could be done by iteratively copying individial cells. One way to do this is using a loop composition.

for(int col = 0; col < col_count; col++) {
    for(int row = 0; row < row_count; row++) {
        destination_matrix[col][row] = source_matrix[col][row];
    }
}

To give some intuition where an n-pointer indirection could be used:

• n = 1: Strings, an array of characters.
• n = 2: Paragraph, holding lines of strings.
• n = 3: An article, holding a list of paragraphs.

Please be aware of using two indirections is usually not something you want. It is usually more efficient to store data in a linear fashion and compute linear indices out of two-compoment vectors and the other way around, especially in the case of this matrix example.

If you want to represent a matrix as an array of pointers to rows you need to allocate memory both for the rows and for the array of pointers to rows. It is simpler to allocate the rows consecutively as a single block.

typedef struct
{
    int n_rows;
    int n_cols;
    double **rows;
    double *data;
} Matrix;

Matrix *matrix_new (int n_rows, int n_cols)
{
    // allocate matrix
    Matrix *m = malloc (sizeof(Matrix));
    m->n_rows = n_rows;
    m->n_cols = n_cols;

    // allocate m->data
    m->data = malloc (n_rows * n_cols * sizeof(double));

    // allocate and fill m->rows
    m->rows = malloc (n_rows * sizeof(double*));
    for (int i = 0; i < n_rows; i++) {
        m->rows[i] = &data[i * n_cols];
    }

    // set the matrix to 0
    for (int i = 0; i < n_rows; i++) {
        for (int j = 0; j < n_cols; j++) {
            m->rows[i][j] = 0.0;
        }
    }

    return m;
}

The purpose of the rows array it to give you the convenience of being able to refer to element i,j with m->rows[i][j] instead of m->data[i * m->n_cols + j].

To free the matrix, take the inverse steps:

void matrix_free (Matrix *m)
{
    free (m->rows);
    free (m->data);
    free (m);
}

To copy you can simply allocate a matrix of the same size and copy element by element:

Matrix *matrix_copy (Matrix *m1)
{
    Matrix *m2 = matrix_new (m1->n_rows, m1->n_cols);
    for (int i = 0; i < m1->n_rows; i++) {
        for (int j = 0; j < m1->n_cols; j++) {
            m2->rows[i][j] = m1->rows[i][j];
        }
    }
    return m2;
}

The important thing to note is that you must not copy the rows array since it is unique to each matrix.

It is important to understand the difference between pointers-to-pointers and multi-dimensional arrays.

What makes it extra confusing is that the same syntax is used for referencing individual elements: var[i][j] will reference element (i,j) of var regardless of if var is a pointer to pointer, double **var or a two-dimensional array, double var[22][43].

What really happens is not the same. A two-dimensional array is a contiguous memory block. A pointer to pointers is an array of pointers that point to the individual rows.

// Two-dimensional array
char var1[X1][X2];
int distance = &var[4][7] - &var[0][0];    // distance = 4*X2+7 

// Pointer-to-pointer
char **var2 = malloc(X1 * sizeof(char*));  // Allocate memory for the pointers
for (i=0; i<X1; i++) var2[i] = malloc(X2); // Allocate memory for the actual data
int distance2 = &var2[4][7] - &var[0][0];  // This could result in anything, since the different rows aren't necessarily stored one after another.

The calculation of distance2 invokes undefined behaviour since the C standard doesn't cover pointer arithmetic on pointers that point to different memory blocks.

You want to use pointer-to-pointer. So you need to first allocate memory for an array of pointers and then for each array:

Matrix *make_matrix(int n_rows, int n_cols) {
    Matrix *m = xmalloc(sizeof(Matrix));
    int i, j;
    m->rows = n_rows; 
    m->cols = n_cols;

    m->data = xmalloc(n_rows * sizeof(double*));
    for (i=0; i < n_; i++) {
        m->data[i] = xmalloc(n_cols * sizeof(double));
        for (j=0; j < n_cols; j++) {
            m->data[i][j] = 0.0;
        }
    }
    return m;
}

Don't assume that the double 0.0 will have all bits set to 0!

To copy a matrix:

Matrix *copy_matrix(Matrix *source) {
    Matrix *m = make_matrix(source->n_rows, source->n_cols);
    int i, j;

    for (j = 0; j < n_rows; j++) {
        for (i = 0; i < n_cols; i++) {
            m->data[i][j] = source[i][j];
        }
    }
    return m;
}

I'll backup a bit and start with the basics. Pointers are one of those things that are not difficult to understand technically, but require you to beat your head into the I want to understand pointers wall enough for them to sink in. You understand that a normal variable (for lack of better words) is just a variable that holds a direct-reference to an immediate value in memory.

int a = 5;

Here, a is a label to the memory address that holds the value 5.

A pointer on the other hand, does not directly-reference an immediate value like 5. Instead a pointer holds, as its value, the memory address where 5 is stored. You can also think of the difference this way. A normal variable holds a value, while a pointer holds the address where the value can be found.

For example, to declare a pointer 'b' to the memory address holding 5 above, you would do something like:

int *b = &a;

or equivalently:

int *b = NULL;
b = &a;

Where b is assigned the address of a. To return the value stored at the address held by a pointer, or to operate directly on the value stored at the address held by a pointer, you must dereference the pointer. e.g.

int c = *b;  /* c now equals 5 */
*b = 7;      /* a - the value at the address pointed to by b, now equals 7 */

Now fast forward to pointer-to-pointer-to-type and simulated 2D matricies. When you declare your pointer-to-pointer-to-type (e.g. int **array = NULL), you are declaring a pointer that points to a pointer-to-type. To be useful in simlated 2D arrays (matricies, etc.), you must delcare an array of the pointer-to-pointer-to-type:

int **array = NULL;
...
array = calloc (NUM, sizeof *array); /* creates 'NUM' pointer-to-pointer-to-int. */

You now have NUM pointers to pointers-to-int that you can allocate memory to hold however many int values and you will assign the starting address for the memory block holding those int values to the pointers you previously allocated. For example, let's say you were to allocate space for an array of 5 random int values (from 1 - 1000) to each of the NUM pointers you allocated above:

for (i = 0; i < NUM; i++) {
    array[i] = calloc (5, sizeof **array);
    for (j = 0; j < 5; j++)
        array[i][j] = rand() % 1000 + 1;
}

You have now assigned each of your NUM pointers (to-pointer-to-int) the starting address in memory where 5 random int values are stored. So your array is now complete. Each of your original NUM pointers-to-pointer-to-int now points to the address for a block of memory holding 5 int values. You can access each value with array notation (e.g. array[i][j] or with pointer notation *(*(array + i) + j) )

How do you free the memory? In the reverse order you allocated (values, then pointers):

for (i = 0; i < NUM; i++)
    free (array[i]);
free (array);

Note: calloc both allocates memory and initializes the memory to 0/nul. This is particularly useful for both the pointers and arrays when dealing with numeric values, and when dealing with an unknown number of rows of values to read. Not only does it prevent an inadvertent read from an uninitialized value, but it also allows you to iterate over your array of pointers with i = 0; while (array[i] != NULL) {...}.