[comp.lang.c] "Dynamic Allocation of 2-D Arrays"

daveh@phred.UUCP (Dave Hampton) (09/14/88)

  Thanks to all who replied to my query on the best way to dynamically
allocate multi-dimensional arrays.  Karl's note incorporated all of the
other suggesttions which I received, so I am posting it (with permission)
as a summary of the techniques required.

------------------------------------------------------------------------

>The closest that I have been able to come (for a 100 by 100 square array
>of integers) is:
>   int (* array_name)[100];
>   array_name = (int *) calloc (1000, sizeof(int));
>   for (x=0; x<ROW; x++) for (y=0; y<COL; y++) array_name[x][y] = x * y;
>   free (array_name);

First, a 100x100 array has 10000 elements, not 1000.

Now, assuming that the column dimension is a constant expression, you're
almost right.  The type of an object looks just like the declaration with the
name removed, so the type of `array_name' is `int (*)[100]'.  The type `array
of 100 ints' is denoted `int [100]'.  What you want is:
   array_name = (int (*)[100])calloc(100, sizeof(int [100]));
This could also be done with
   array_name = (int (*)[100])calloc(10000, sizeof(int));
but I think the former is clearer.

If the column dimension isn't constant, you can't do this.  You could instead
use a pointer to a pointer rather than a pointer to an array (and despite what
anyone tells you, pointers and arrays are not the same thing in C).  This
requires a bit more work to build and destroy, but can still be accessed using
normal subscript notation:
   int **array_name;
   array_name = (int **)calloc(nrows, sizeof(int *));
   for (x=0; x<nrows; ++x) array_name[x] = (int *)calloc(ncols, sizeof(int));
   for (x=0; x<nrows; ++x) for (y=0; y<ncols; ++y) array_name[x][y] = x * y;
   for (x=0; x<nrows; ++x) free(array_name[x]);
   free(array_name);

As a variation on this, it's also possible to combine the allocations so that
the whole mess can be destroyed with a single free():
   #define ALIGN 8 /* implementation-dependent */
   int **array_name;
   int offset = (nrows*sizeof(int *)+ALIGN-1)/ALIGN*ALIGN;
   array_name = (int **)malloc(offset + nrows*ncols*sizeof(int));
   for (x=0; x<nrows; ++x)
     array_name[x] = (int *)((char *)array_name+offset+x*ncols*sizeof(int));
   for (x=0; x<nrows; ++x) for (y=0; y<ncols; ++y) array_name[x][y] = x * y;
   free(array_name);
(The constant ALIGN is technically implementation-dependent, but the value 8
suffices for any implementation I know of.)

Finally, if you don't mind having to do the subscript calculation with a
macro, you can use the simpler mechanism:
   #define array_name(x,y) (_array_space[(x)*(ncols)+(y)])
   int *_array_space;
   _array_space = (int *)calloc(nrows*ncols, sizeof(int));
   for (x=0; x<nrows; ++x) for (y=0; y<ncols; ++y) array_name(x,y) = x * y;
   free(&array_name(0,0));

This is more than you asked for, but I wasn't sure how much generality you
needed.

Karl W. Z. Heuer (ima!haddock!karl or karl@haddock.isc.com), The Walking Lint


-- 
Reply to:  uiucuxc!tikal!phred!daveh {Dave Hampton}
Addr:      Research Division, Physio-Control Corp.
           P.O. Box 97006
           Redmond, WA  98073-9706

schmidt@beaver.ics.uci.edu (Doug Schmidt) (09/16/88)

In article <2347@phred.UUCP> daveh@phred.UUCP (Dave Hampton) writes:
>
[ large section of interesting code deleted ]

>  Thanks to all who replied to my query on the best way to dynamically
>allocate multi-dimensional arrays.  Karl's note incorporated all of the
>other suggesttions which I received, so I am posting it (with permission)
>as a summary of the techniques required.
>As a variation on this, it's also possible to combine the allocations so that
>the whole mess can be destroyed with a single free():
>   #define ALIGN 8 /* implementation-dependent */
>   int **array_name;
>   int offset = (nrows*sizeof(int *)+ALIGN-1)/ALIGN*ALIGN;
>   array_name = (int **)malloc(offset + nrows*ncols*sizeof(int));
>   for (x=0; x<nrows; ++x)
>     array_name[x] = (int *)((char *)array_name+offset+x*ncols*sizeof(int));
>   for (x=0; x<nrows; ++x) for (y=0; y<ncols; ++y) array_name[x][y] = x * y;
>   free(array_name);
>(The constant ALIGN is technically implementation-dependent, but the value 8
>suffices for any implementation I know of.)

Karl's method is neat, and here is a slight variation of it that
eliminates all the multiplications required to initialize the 
access table vector.

------------------------------( cut here )------------------------------
#include <stdio.h>

extern void *malloc();
typedef int ITEM, *ITEM_PTR, **ITEM_VEC;
typedef char BYTE, *BYTE_PTR;

int ALIGN    = 8;
   
main(argc,argv)
int   argc;
char *argv[];
{
   int Num_Rows = atoi(argv[1]);
   int Num_Cols = Num_Rows;
   int Offset = (Num_Rows*sizeof(ITEM_PTR)+ALIGN - 1)/ALIGN*ALIGN;
   ITEM_VEC Vec = (ITEM_VEC)(malloc(Offset+Num_Rows*Num_Cols*sizeof(ITEM)));
   ITEM_PTR Block_Ptr = (ITEM_PTR)((BYTE_PTR)Vec + Offset);
   int Index = 0;
   int x,y;

   for (Offset = 0; Index < Num_Rows; Index++,Offset += Num_Cols) {
      Vec[Index] = Block_Ptr + Offset;
   }

   for (x = 0;x < Num_Rows;x++) {
      for (y = 0;y < Num_Cols;y++) {
         Vec[x][y] = x + y;
      }
   }

   for (x = 0;x < Num_Rows;x++) {
      for ( y = 0;y < Num_Cols;y++) {
         printf("%d",Vec[x][y]);
      }
      putchar('\n');
   }

}
----------------------------------------

This method replaces all that multiplication in the initialization
loop by 2 additions (a good optimizing compiler might perform this
automatically from the original code).  It seems portable enough, but
I'm not betting the farm on it!

Doug Schmidt