Dynamically allocating 2d array with adjacent rows in memory

In a previous post “Allocating multidimentional array at runtime in C” I have explained a technique to allocate multidimensional arrays on runtime. While playing around with OpenMPI, I came to know that while sending/receiving a buffer, it requires the elements of a 2d matrix (or any dimension) to be in adjacent. Basically it does not care what you send, or receive, what it cares is the number of elements to be send should be adjacent to one another. In the previous post, the process will allocate the 2d or n-d matrix, but the rows of the matrix may not be adjacent to each other, as each row was allocated separately with malloc and then inserted into another array of pointers, each of which location points to the base addresses of these memory block. Read the post for details.

In C language the 2d array/matrix are stored in a row-major order, that is the elements of the matrix are stored adjacent to each other in the memory row wise. The first row comes first then just after the first row the second row starts, and so on. In the previous method the rows of the matrix may be scattered throughout the memory, as they are allocated with seperate malloc calls, but each of these returned addresses to the memory blocks (used as rows) are assigned to another array of pointers, which holds the rows together, and allows the mat[i][j] syntax to work.

For the applications in which, we might need to allocate the matrix dynamically at runtime, also have the rows of the matrix requires to be adjacent in the memory, and also make the mat[i][j] syntax work can be fulfilled by the following approach.

How it works

Let us assume that we have a 2d matrix having m rows and n columns, ie. we have an m X n matrix. Also assume that the matrix holds type int (for convenience of description). The approach is to first allocate a single block of memory containing m * n elements. Then allocate an array of pointers to integers, of m elements, representing the rows. Next we assign the i^th row address from the linear block, by computing the offset into it, to the i^th location of the array of pointers. The code for allocation is like as follows:

int **allocate_2d_matrix (int m, int n)
{
  int *linear, **mat;
  int i;

  linear = malloc (sizeof (int) * m * n);
  mat = malloc (sizeof (int *) * m);
  for (i = 0; i < m; i++)
  {
    mat[i] = &linear[i*n];
  }
  return mat;
}

First we allocate the buffer of length m * n together, therefore all the m * n elements are adjacent to each other. The next malloc will allocate an array of pointers to ints (int *) of length m. In the loop the i*n value is the index of the starting element of the i^th in the linear representation, and the address of this starting row is assigned into the i^th element of mat.

Here is what we did in the previous post

 mat = malloc (sizeof (char *) * m);
 for (i = 0; i < m; i++)
 {
   mat[i] =  malloc (sizeof (int) * n);
 }

Note the basic difference in this case and the case described in the previous post.
The point of the mat = malloc (sizeof (int *) * m); is to allocate the m pointers which will point to the m rows. But in the previous post, we allocate and assign the rows together through a malloc inside the loop. But in this case the allocation of the rows are done previously through linear = malloc (sizeof (int) * m * n);, the loop will only do the assignment of the appropriate row start addresses into the array of row pointers.

And for freeing it is:

void free_2d_matrix (int **mat)
{
  free (mat[0]); /* Points to the linear buffer allocated in the first malloc */
  free (mat);    /* Address of the mat allocated in the second malloc */
}

In this case mat[0] points to the address of the first row of the matrix, which also happens to the address of the linear buffer allocated in the allocate_2d_matrix routine. We free it first. Next we need to free the mat also, which represents the base address of the array of (int *)s. This will free every byte we allocated and prevent any memory leak.

After allocation we can access the elements as follows:

mat[i][j];

In this case the access of the matrix elements are identical to the description in the previous post. Only the difference is that now the rows sit adjacent to themselves in the memory.

More dimensions

To allocate more than 2 dimensions, the idea still is the same. The main essence is to find the start address of the dimensions. I am not going to write about the specific implementations. I think this question in StackOverflow can be helpful: “Linear simulation of multidimensional array”

Related Posts

• Allocating multidimentional array at runtime in C