Dynamic memory allocation code explanation

Question

Being a beginner C/C++ programmer, I am having to spend several hours, trying to decipher the code below: Could someone walk me (step me through the code below for dynamic memory allocation) line by line.

 char **alloc_2d_char(const int rows, const int cols) 
 {
   char *data = (char *)malloc(rows*cols*sizeof(char));
   char **array= (char **)malloc(rows*sizeof(char*));

   for (int i=0; i<rows; i++)
      array[i] = &(data[cols*i]);

   return array;
 }

Pointer to Pointers is explained separately than from Pointers to Arrays. I have been able to get parts of the information from various sources, but none that stitches the lines cohesively.

Answer 1

Each * in a declaration refers to one level of pointer indirection. so int ** means a pointer to a pointer to an int. So your function:

char **alloc_2d_char(const int rows, const int cols) 
{

returns a pointer to a pointer to a char.

  char *data = (char *)malloc(rows*cols*sizeof(char));

This declares a pointer to a char. The pointer is called data. The initialization calls malloc, which allocates a number of bytes equal to the value of the argument. This means there are rows*cols*sizeof(char) bytes, which will be equal to rows*cols, since a char is 1 byte. The malloc function returns the pointer to the new memory, which means that data now points to a chunk of memory that's rows*cols big. The (char *) before the call to malloc just casts the new memory to the same type as the pointer data.

  char **array= (char **)malloc(rows*sizeof(char*));

array is a pointer to a pointer to a char. It is also being assigned using malloc. The amount of memory being allocated this time is rows*sizeof(char), which is equal to rows. This means that array is a pointer to a pointer to a chunk of memory big enough to hold 1 row.

 for (int i=0; i<rows; i++)
    array[i] = &(data[cols*i]);

The rest of your code initializes each element of array to hold the address of the corresponding row of the big chunk of memory. Your data pointer will point to a chunk of memory that looks like this:

col:   0 1 2 3 ... cols-1
row: 0 *
     1 *
     2 *
     3 *
     .
     .
     .
rows-1 *

And your array pointer will point to a chunk of memory with a list of pointers, each of which points to one of the asterisks in the memory chunk above.

   return array;
 }

This just returns your array pointer to a pointer, which matches the return type of the alloc_2d_char function: char **. This means that the caller of the function will essentially obtain an array of pointers, and each of these pointers points to one of the rows of the 2D array.

Answer 2

The code is using a single contiguous block of memory to hold a 2-D array.

char *data = (char *)malloc(rows*cols*sizeof(char));

Ok -- this line is allocating space for the entire 2-D array. The 2-D array is rows rows by cols columns. So the total number of elements is rows * cols. Then you have to multiply that by the amount of space each element takes up, which is sizeof(char) since this is a 2-D array of char. Thus the total amount of memory to be allocated is rows * cols * sizeof(char) which is indeed the argument to malloc.

The malloc call returns a pointer to the allocated memory. Since this memory will be used to hold char, you cast the return value to char *.

char **array= (char **)malloc(rows*sizeof(char*));

array is being declared as type "pointer to pointer to char" because that's what it's going to do. It'll point to memory that will hold pointers to char. It will be one pointer for each row. So you have to allocate rows * sizeof(char *) memory: the number of pointers times the size of a pointer of the right type. And since this was allocated to point to pointers to char, we cast the return value to char **.

for (int i=0; i<rows; i++)
   array[i] = &(data[cols*i]);

This is the magic :). This sets each pointer in array to point to within the block of actual data allocated earlier. Consider a concrete example where rows is 2 and cols is 3. Then you have the block of 6 characters in memory:

 [0][1][2][3][4][5]

And data[n] (for n from 0 to 5) is the n-th element and &data[n] is the *address of the n-th element.

So what that loop does in this case is do:

array[0] = &data[0];
array[1] = &data[3];

So array[0] points to the sub-block starting at [0] and array[1] points to the sub-block starting at [3]. Then when you add the second subscript you're indexing from the start of that pointer. So array[0][2] means "get the pointer stored in array[0]. Find what it points to, then move ahead 2 elements from there.:

array[0] points to [0][1][2] (well, actually points to [0]). Then you move two elements ahead and get [2].

Or if you start with array[1][1], array[1] points to [3][4][5] (and actually points at [3]. Move one element ahead and get [4].

Answer 3

Is not hard to decipher...

char *data = (char *)malloc(rows*cols*sizeof(char));

simple memory allocation

char **array= (char **)malloc(rows*sizeof(char*));

memory allocation of #row char pointers

array[i] = &(data[cols*i]);

every array[i] is a pointer, a pointer to data[cols*i]

Answer 4

You can think of the 2-D array that it is creating as an array of single-dimensional arrays. Each row entry points to an array of char that represents the column data for that row.

The following is the original code with comments added to attempt to describe each step:

char **alloc_2d_char(const int rows, const int cols) 
{
  // This allocates the chunk of memory that stores that actual data.
  // It is a one single-dimensional array that has rows*cols characters.
  char *data = (char *)malloc(rows*cols*sizeof(char));

  // This allocates an array of pointers that will then be assigned to the
  // individual rows (carved out of the previous allocation).
  char **array= (char **)malloc(rows*sizeof(char*));

  // This assigns each row to the appropriate position in the data array.  
  // The &(data[cols*i]) bit of it is the address of a portion in the 
  // memory pointed to by data.  The cols*i is the offset to the portion that
  // represents row i.
  for (int i=0; i<rows; i++)
     array[i] = &(data[cols*i]);

  // After doing this, then you can assign a value such as:
  //   array[r][c] = 'x';
  // That statement would store 'x' into data[r*c + c]

  return array;
}

Answer 5

The first malloc is getting memory for the 2D character array. The second malloc is getting memory for rows index.

The for loop is setting the pointer to each row.

Finally the row index is returned.