Allocate a contiguous block of memory

Question

I try to work with a contiguous block of memory, more over I try to create an array who's dimensions are not known at compile time (before C99) so no variable-length arrays are involved here.

I came with the following:

#include <stdio.h>
#include <stdlib.h>

int main(void){
    unsigned int row, col,i, j, k;
    int l = 0;

    printf("Give the ROW: ");
    if ( scanf("%u",&row) != 1){
        printf("Error, scanf ROW\n");
        exit(1);
    }

    printf("Give the COL: ");
    if ( scanf("%u",&col) != 1){
        printf("Error, scanf COL\n");
        exit(2);
    }

    int *arr = malloc(sizeof *arr * row * col); /* This doesn't compile with `-pedantic` */
    if(arr == NULL){
        printf("Error, malloc\n");
        exit(3);
    }

    for ( i = 0; i < row ; i++){
        for ( j = 0 ; j < col ; j++){
            arr[i * col + j] = l;
            l++;
        }
    }

    for (k = 0 ; k < (row * col) ; k++){
        printf("%d ",arr[k]);
    }

    free(arr);
}

Which give's me the following:

Give the ROW: 5
Give the COL: 5
0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 

Now I have a Questions:

Is this the right approach?

Answer 1

If you don't know the number of dimensions ahead of time (1, 2, 3, or more dimensions), then this is the only approach you have available. If you know the number of dimensions, but not their values, and you don't have VLAs available, again, this is the only approach you have available.

Because I am bored out of my freaking skull from writing documentation, I womped up this quick and dirty prototype to demonstrate how you can map a 1D array onto arrays of different numbers of dimensions:

#include <stdio.h>
#include <stdlib.h>
#include <stdarg.h>

/**
 * Compute the offset into a 1D array based on a set of dimensions
 * and indices, and return the element at that offset.  You must pass
 * at least as many indices as number of dimensions; any extra indices
 * will not be processed.  
 *
 * Inputs:
 *    a       -- 1D array of data
 *    ndims   -- number of dimensions to map array onto
 *    dims    -- dimension sizes
 *    ...     -- index values
 *
 * Outputs: none
 *
 * Returns: value at desired index
 */
int access( const int * restrict a, size_t ndims, const size_t * restrict dims, ... )
{
  va_list ap;
  va_start( ap, dims );  point to first index value in argument list

  size_t idx = 0;

  /**
   * To find the right index for a given number of dimensions, 
   * we need to compute
   *
   *  d0 x d1:           i * d1 + j             
   *  d0 x d1 x d2:      i * d1 * d2 + j * d1 + k
   *  d0 x d1 x d2 x d3: i * d1 * d2 * d3 + j * d1 * d2 + k * d1 + l
   *
   * The loop below computes these as
   *
   *    i * d1 + j
   *    (i * d2 + j) * d1 + k
   *    (((i * d3 + j) * d2) + k) * d1 + l
   *
   * etc.
   */
  for ( size_t i = 1; i < ndims; i++ )
  {
    idx += va_arg( ap, size_t ); // get next index argument and advance ap
    idx *= dims[i];
  }
  idx += va_arg( ap, size_t );
  va_end( ap );
  return a[idx];
}

int main( void )
{
  int test[] = {0, 1, 2, 3, 4, 5, 6, 7, 8, 9};
  size_t dims2x5[] = {2, 5};       // for mapping test onto a 2x5 array
  size_t dims3x3[] = {3, 3};       // for mapping test onto a 3x3 array
  size_t dims2x2x2[] = {2, 2, 2};  // for mapping test onto a 2x2x2 array

  for ( size_t i = 0; i < dims2x5[0]; i++ )
    for ( size_t j = 0; j < dims2x5[1]; j++ )
      printf( "test[%zu][%zu] = %d\n", i, j, access( test, 2, dims2x5, i, j ) );

  for ( size_t i = 0; i < dims3x3[0]; i++ )
    for ( size_t j = 0; j < dims3x3[1]; j++ )
      printf( "test[%zu][%zu] = %d\n", i, j, access( test, 2, dims3x3, i, j ) );

  for ( size_t i = 0; i < dims2x2x2[0]; i++ )
    for ( size_t j = 0; j < dims2x2x2[1]; j++ )
      for ( size_t k = 0; k < dims2x2x2[2]; k++ )
        printf( "test[%zu][%zu][%zu] = %d\n", i, j, k, access( test, 3, dims2x2x2, i, j, k ));

  return 0;
}

And the output:

test[0][0] = 0
test[0][1] = 1
test[0][2] = 2
test[0][3] = 3
test[0][4] = 4
test[1][0] = 5
test[1][1] = 6
test[1][2] = 7
test[1][3] = 8
test[1][4] = 9

test[0][0] = 0
test[0][1] = 1
test[0][2] = 2
test[1][0] = 3
test[1][1] = 4
test[1][2] = 5
test[2][0] = 6
test[2][1] = 7
test[2][2] = 8

test[0][0][0] = 0
test[0][0][1] = 1
test[0][1][0] = 2
test[0][1][1] = 3
test[1][0][0] = 4
test[1][0][1] = 5
test[1][1][0] = 6
test[1][1][1] = 7

This isn't pretty - access( a, 3, dims2x2x2, i, j, k ) doesn't exactly read as easily as a[i][j][k]. With some additional levels of abstraction you could clean that up a bit, but it's always going to feel a bit awkward. And naturally you sacrifice some performance. But, if you need to be able to map a 1D array onto an arbitary-sized N-dimensional array where you don't even know the number of dimensions ahead of time, this is a possible solution.

Answer 2

You have a hidden error in this line:

arr[i * row + j] = k;

The correct index calculation is

arr[i * col + j] = k;

The reason that you don't notice that problem is that row and col have the same value in the code. If, for example, you set row to 6 and col to 3, the error will be obvious. You will allocate space for 18 ints, but when i is 5 and j is 2, the code will try to access location [5*6 + 2] which is off the end of the array, and will result in undefined behavior.

Here's how the address calculation works. The drawing below shows how a 2D array (row=6 and col=3) is actually laid out in memory. Note that the number of items on each row is equal to the number of columns in the array. So the starting index for each row is a multiple of the number of columns. In this example, since the number of columns is 3, the rows start at indexes 0,3,6,9,... So given an element at index [i][j] in the 2D array, the index in the 1D array is i*col + j.

Answer 3

The approach is okay. And the dimensions are known at compile time.

The reason for getting 15 is that arr it represents the base address so when you add 15 to arr it will give you the address of block containing 15 and later on de-referencing you will get 15.