• Uncategorized

About c : Using-malloc-for-allocation-of-multi-dimensional-arrays-with-different-row-lengths

Question Detail

I have the following C code :

int *a;
size_t size = 2000*sizeof(int);
a = malloc(size);

which works fine. But if I have the following :

char **b = malloc(2000*sizeof *b);

where every element of b has different length.

How is it possible to do the same thing for b as i did for a; i.e. the following code would hold correct?

char *c;
size_t size = 2000*sizeof(char *);
c = malloc(size);

Question Answer

First, you need to allocate array of pointers like char **c = malloc( N * sizeof( char* )), then allocate each row with a separate call to malloc, probably in the loop:


/* N is the number of rows  */
/* note: c is char** */
if (( c = malloc( N*sizeof( char* ))) == NULL )
{ /* error */ }

for ( i = 0; i < N; i++ )
{
  /* x_i here is the size of given row, no need to
   * multiply by sizeof( char ), it's always 1
   */
  if (( c[i] = malloc( x_i )) == NULL )
  { /* error */ }

  /* probably init the row here */
}

/* access matrix elements: c[i] give you a pointer
 * to the row array, c[i][j] indexes an element
 */
c[i][j] = 'a';

If you know the total number of elements (e.g. N*M) you can do this in a single allocation.

The typical form for dynamically allocating an NxM array of type T is

T **a = malloc(sizeof *a * N);
if (a)
{
  for (i = 0; i < N; i++)
  {
    a[i] = malloc(sizeof *a[i] * M);
  }
}

If each element of the array has a different length, then replace M with the appropriate length for that element; for example

T **a = malloc(sizeof *a * N);
if (a)
{
  for (i = 0; i < N; i++)
  {
    a[i] = malloc(sizeof *a[i] * length_for_this_element);
  }
}

Equivalent memory allocation for char a[10][20] would be as follows.

char **a;

a=malloc(10*sizeof(char *));

for(i=0;i<10;i++)
    a[i]=malloc(20*sizeof(char));

I hope this looks simple to understand.

The other approach would be to allocate one contiguous chunk of memory comprising header block for pointers to rows as well as body block to store actual data in rows. Then just mark up memory by assigning addresses of memory in body to the pointers in header on per-row basis. It would look like follows:

int** 2dAlloc(int rows, int* columns) {    
    int header = rows * sizeof(int*);

    int body = 0;
    for(int i=0; i<rows; body+=columnSizes[i++]) {  
    }
    body*=sizeof(int);

    int** rowptr = (int**)malloc(header + body);

    int* buf  = (int*)(rowptr + rows);
    rowptr[0] = buf;
    int k;
    for(k = 1; k < rows; ++k) {
        rowptr[k] = rowptr[k-1] + columns[k-1];
    }
    return rowptr;
}

int main() {
    // specifying column amount on per-row basis
    int columns[] = {1,2,3};
    int rows = sizeof(columns)/sizeof(int);
    int** matrix = 2dAlloc(rows, &columns);

    // using allocated array
    for(int i = 0; i<rows; ++i) {
        for(int j = 0; j<columns[i]; ++j) {
            cout<<matrix[i][j]<<", ";
        }   
            cout<<endl;
    }

    // now it is time to get rid of allocated 
    // memory in only one call to "free"
    free matrix;
}

The advantage of this approach is elegant freeing of memory and ability to use array-like notation to access elements of the resulting 2D array.

If every element in b has different lengths, then you need to do something like:

int totalLength = 0;
for_every_element_in_b {
    totalLength += length_of_this_b_in_bytes;
}
return malloc(totalLength);

I think a 2 step approach is best, because c 2-d arrays are just and array of arrays. The first step is to allocate a single array, then loop through it allocating arrays for each column as you go. This article gives good detail.

2-D Array Dynamic Memory Allocation

int **a,i;

// for any number of rows & columns this will work
a = malloc(rows*sizeof(int *));
for(i=0;i<rows;i++)
    *(a+i) = malloc(cols*sizeof(int));

malloc does not allocate on specific boundaries, so it must be assumed that it allocates on a byte boundary.

The returned pointer can then not be used if converted to any other type, since accessing that pointer will probably produce a memory access violation by the CPU, and the application will be immediately shut down.

You may also like...

Leave a Reply

Your email address will not be published.

This site uses Akismet to reduce spam. Learn how your comment data is processed.