Path: utzoo!attcan!uunet!lll-winken!lll-tis!helios.ee.lbl.gov!pasteur!ucbvax!ucsd!orion.cf.uci.edu!paris.ics.uci.edu!beaver.ics.uci.edu!schmidt
From: schmidt@beaver.ics.uci.edu (Doug Schmidt)
Newsgroups: comp.lang.c
Subject: Re: "Dynamic Allocation of 2-D Arrays"
Message-ID: <712@paris.ICS.UCI.EDU>
Date: 16 Sep 88 00:14:27 GMT
References: <2347@phred.UUCP>
Sender: news@paris.ics.uci.edu
Reply-To: schmidt@beaver.ics.uci.edu (Doug Schmidt)
Organization: University of California, Irvine - Dept of ICS
Lines: 71

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