C Pointer to Pointer Problems in Matrix Function

Question

I know there are very similar questions, but I've read them and I don't understand what is going wrong or what exactly I haven't understood about pointers to pointers.

My teacher is using a "learning by doing" approach to pointers and it has left me with approximately 100 questions. Sometimes I just change things around until it compiles, but it really isn't becoming any more clear to me, so if someone could help clarify a few things, I'd really appreciate it.

struct Matrix {
    int rows; // number of rows
    int cols; // number of columns
    double **data; 
};
typedef struct Matrix Matrix;

The pointer to a pointer, is something like this, right?

double *row1 = (double *) malloc (n_cols*sizeof(double));
double *row2 = (double *) malloc (n_cols*sizeof(double));
double *row3 = (double *) malloc (n_cols*sizeof(double));
double *data[] = { row1, row2, row3};

Data is pointing to the row number which is pointing to the doubles in the rows.

Now I am supposed to make a constructor function that makes a Matrix with a 0 in every position returns a pointer to a Matrix.

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

    double **rows_and_columns = xmalloc(n_rows * n_cols * sizeof(double));
    memset(rows_and_columns, 0, m->rows * m->cols * sizeof(double)); 
    m->data = *rows_and_columns;

    return m;
}

So I made a pointer for the matrix, then I assigned the values for the rows and columns. Then I got confused (although I am not sure how confused, because this part compiles). I made a pointer to pointer for the last element of the struct Matrix (**data). Since **rows_and_columns has to hold the rows and columns, I allocated xmalloc(n_rows * n_cols * sizeof(double)) memory to it. I then set the whole thing to 0 and assign it to data. I think this m->data = rows_and_columns; says that m points to data and since data is a pointer and rows_and_columns is a pointer, we'll align their addresses, so m->data will also point to a bunch of 0s? Or is this wrong? And I am returning m, because the output is Matrix * and the m will get the * upon output, correct?

The next step is to copy a matrix, at which point I got even more lost.

Matrix *copy_matrix(double *data, int n_rows, int n_cols) {

    Matrix *m = make_matrix(n_rows, n_cols);

    double *row = (double *) malloc (n_cols*sizeof(double));

    int i = 0;
    for (int j = 0; j < n_rows; j++) {
        for (; i < n_cols; i++) {
            row = (double *) malloc (n_cols*sizeof(double));
            row [i] = data[i + j*n_cols];   
        }
        m->data [j] = *row [i];

    }
    free(row);      
    return m;
}

So we are returning a pointer to a Matrix again. The input is now a pointer to double values, which I am assuming are the rows. First, I made a matrix. Then I made a pointer for a row with a n columns worth of memory (double *) malloc (n_cols*sizeof(double)).

This is where I got super confused. I was imagining **data the whole time as something like above (double *data[] = { row1, row2, row3};). So, I wanted to copy each row of *data into *row, then save that as an entry in **data, like data[0] = row0, but something isn't clicking with the pointers, because I am not allowed to assign m->data [j] = row [i];, because I'm assigning incompatible types by assigning double * from type double?

Answer 1

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.

Answer 2

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.

Answer 3

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;
}

Answer 4

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) {...}.