Copyright © 1989, Dr. Dobb's Journal

Copyright © 1989, Dr. Dobb's Journal

Copyright © 1989, Dr. Dobb's Journal

Copyright © 1989, Dr. Dobb's Journal

Copyright © 1989, Dr. Dobb's Journal

Paul Anderson

When you declare arrays in C, their sizes remain fixed. You have to decide before your program runs how large an array will be, regardless of whether you declare it as automatic or static. What about declaring arrays at run time? In this case, you need to call the C library routine malloc( ) or calloc( ) to build dynamic arrays from memory (called the heap). This approach eliminates anticipating array bounds at compile time and makes programs allocate only as much memory as they need.

One-dimensional arrays are easy because a call to malloc( ) or calloc( ) returns a pointer to a chunk of heap memory that you may use as a one-dimensional array. You cast the heap pointer to an appropriate data type and use either array notation or pointers to reference the allocated elements.

Multidimensional arrays, however, are more difficult. There's no standard C library routine that sets up the heap so that you may use it as a multidimensional array. To the heap manager, heap storage is merely a block of consecutive bytes with no notion of rows, columns, and so on. You need a way to organize the heap for run-time multidimensional arrays. Moreover, it would be nice to retain the concepts of rows and columns so that heap memory appears like a multidimensional array to your programs.

In this article, I'll discuss C functions that create run-time two-dimensional and three-dimensional arrays of any data type (including arrays of structures and unions). I'll also discuss a technique to mimic the subroutine calling conventions of Basic and Fortran with two-dimensional arrays. Along the way, I'll review two-dimensional and three-dimensional arrays and the relationships between pointer expressions and array references. This should give you the information you need to implement these concepts in your own C programs.

Let's start with how C views arrays. For a one-dimensional array of any data type, the following equivalence exists between an array reference and a pointer expression:

  a[i] = (*(a + i))

I call this the basic rule because it applies to many complicated pointer expressions, as you will see later on. Note that you may omit the outer parentheses most of the time except for expressions where C's precedence rules require them. The basic rule helps explain simple relations such as &a[i] = a +i, where I apply C's address operator (&) to both sides of the relation and use C's precedence rules to simplify the result. Using the same method, the basic rule helps derive the relations a[0] = *a and &a[0] = a.

  #include <stdio.h>
  main ()
  {
     static char a[] = "0123456789";
     int i = 5;

     printf ("%c %c %c %c\n", a[i], a[5], i[a], 5[a]);
  }

Viewing multidimensional arrays as grids with rows and columns is for our benefit. Unfortunately, the compiler has a harder job than we do making the connection between arrays and grids. Physical memory is accessed as a one-dimensional array, so the compiler maps multidimensional arrays to blocks of memory. Each time you reference a multidimensional array element, the compiler calculates an address in the memory block.

Figure 3 shows the memory layout for the declaration double mint[3][5]. C stores two-dimensional arrays in memory by rows (this is called row major form). The second subscript varies faster than the first one. Therefore, mint[0] points to the first double in the first row, mint[1] points to the first double in the second row, and so forth. The compiler calculates the address for an array reference by locating the appropriate row and accessing the correct column within that row.

When you use the array reference mint[i][j] in a C program, the compiler implements the following pointer expression: *(&mint[0][0] + 5 * i + j). Subscript i is the row number, subscript j is the column number, and &mint[0][0] is the base address of the array. I call this above expression a storage map equation. Every multidimensional array declaration in a program has one. This particular storage map equation is for the two-dimensional array double mint[3][5].

  main ()
  {
     extern double mint [][5]; /* OK */
     . . . mint [i][j] . . .
     f(mint);
  }
  f(a)
  double a [][5];              /* OK */
  {
    . . . a[i][j] . . .
  }

To generate the storage map equation for a[i][j] inside f( ), the compiler requires the number of columns but not the number of rows. Likewise, the extern statement provides the compiler with the necessary information to reference mint[i][j], even though the array is declared in another file.

  int *p;
  int **a;

  p = (int *) calloc(2 * 3, sizeof(int));     /* pointer to data */
  a = (int **) malloc(2 * sizeof(int *));     /* pointer to rows */

  a[0] = p;                                      /* first row */
  a[1] = p + 3;                                  /* second row */

  int **a;                              /* 2D array of integers */
  struct something **s;       /* 2D array of structures */

  a = (int **) dim2 (3, 5, sizeof(int));
  s = (struct something **) dim2 (4, 6, sizeof(struct something));

Function dim2( ) allocates heap memory for the row pointer array (pointed to by prow) and the data array (pointed to by pdata). The forloop connects the row pointer array to the data array. Function free2( ) makes two calls to free( ) to release heap memory. The first call frees the data array and the second call releases the row pointer array. Note that the order for the calls to free( ) is significant!

  int ***a;                                 /* 3D array of integers */
  struct something ***s;                    /* 3D array of structures */

  a = (int ***) dim3 (3, 4, 5, sizeof(int));
  s = (struct something ***) dim3 (4, 6, 8, sizeof(struct something));

Function dim3( ) allocates heap memory for the grid pointer array (pointed to by pgrid), the row pointer array (pointed to by prow), and the data array (pointed to by pdata). Two for loops connect the grid pointer array to the row pointer array and to the data array. Function free3( ) makes three calls to free( ) to release heap memory for the data array, the row pointer array, and the grid pointer array, respectively.

Languages such as Fortran and Basic allow you to pass different-size multidimensional arrays as arguments to the same function and use array notation to reference elements. In Fortran, for example, the statements:

  SUBROUTINE FUNC(A, M, N)
  DIMENSION A(M, N)
  . . .
  END

allow a subroutine called FUNC( ) to access a two-dimensional array called A with run-time values for M rows and N columns. Programs call FUNC( ) with different-size arrays. Fortran libraries use subroutines such as FUNC( ) to invert matrices or calculate mathematical items, such as determinants and eigenvalues. This convention is useful because subroutines may reference elements by rows and columns.

C doesn't provide such a built-in feature. Consider what happens, for example, when you pass the address of a multidimensional array to a function. Inside the function, the compiler uses a storage map equation with fixed sizes. To illustrate, suppose you declare the following two-dimensional array of integers: int data[5][9].

       func(data, 5, 9);

  Inside func(), you have the following:

  func(a, rows, cols)
  int a[][9];
  int rows, cols;
  {
    register int i, j;

    for (i = 0; i < rows; i++)
       for (j = 0; j < cols; j++)
           . . . a[i][j] . . .    /* array references OK */

Suppose you have another two-dimensional array called int moredata [4][10]; You can't use func( ) to access data in this array. The function call func(more data, 4, 10) won't work because func( ) is compiled with the number of columns set to 9 and not 10. Attempts to use it make func( ) reference memory incorrectly.

Another alternative is to pass the address of the first element of the two-dimensional array. The statements:

  func(&data[0][0], 5, 9);
  func(&moredata[0][0], 4, 10);

  func(a, rows, cols)
  int *a;
  int rows, cols;
  {
    register int *p = a, *end = a + row * cols;
    while (p < end) {
       . . . *p++ . . .      /* Can't use a[i][j] references */
    }
  }

Here, parameter a is a pointer to an integer (previously, it was a pointer to an array of integers). This allows you to use compact pointer expressions such as *p++ to access memory as a series of rows*cols integers. Although this is relatively fast, the concept of rows and columns disappears. Functions that compute matrix inversions and determinants need this information, though.

In situations such as this, we'd like to have C behave like Fortran or Basic. This would help us translate Fortran and Basic subroutines to C more easily. Let's apply the previous techniques to solve this problem.

What about performance issues? The techniques I've shown you for run-time multidimensional arrays substitute pointer indirections for storage map equations. (Remember, storage map equations typically generate integer multiplies or shifts and adds in assembly code.) I've benchmarked these programs and others using Microsoft's C compiler (under DOS and Xenix for 286 and 386 machines) and discovered that pointer indirections are no worse in execution time than integer multiplies (and often execute faster). In the two-dimensional case, the overhead of allocating heap memory for the row pointer array isn't too bad, but remember that three-dimensional arrays require two pointer arrays. This approach uses more heap memory and can take more time to set up. It's also possible to eliminate function call overhead by using macros to generate the arrays (the solutions are in the bibliography). Ultimately, you'll have to judge whether the overhead of setting up run-time multidimensional arrays is worth the effort for your application.

Anderson, Paul and Anderson, Gail; Advanced C: Tips and Techniques. Indianapolis, Ind.: Howard W. Sams & Company, 1988.

I'd like to thank Gail Anderson, Marty Gray, and Tim Dowty for their assistance.

All source code for articles in this issue is available on a single disk. To order, send $14.95 (Calif. residents add sales tax) to Dr. Dobb's Journal, 501 Galveston Dr., Redwood City, CA 94063; or call 800-356-2002 (from inside Calif.) or 800-533-4372 (from outside Calif.). Please specify the issue and format (MS-DOS, Macintosh, Kaypro).

C MULTIDIMENSIONAL ARRAYS AT RUN TIME by Paul Anderson

Copyright © 1989, Dr. Dobb's Journal