Dynamic and Variable Length Structures

[Derek R. Foster]

In article <5624 at rouge.usl.edu> pcb at gator.cacs.usl.edu (Peter C. Bahrs) writes:
>I want to write a dynamiclly dimensioned container type (oo flavors) 
>that is dynamic in the size and number of dimensions, hopefully without
>any bounds on either.
>
>Suppose I want to create a thing that can point to integers.  So I want to write
>  Type?  *x;
>  x = dim(3,4,5);
>    or
>  dims[0]=3;dims[1]=4;dims[2]=6;dims[3]=4; dims[4]= -1;
>  Dim (x, dims);
>And now to get an integer I want to say: y = Retrieve(x,dims) where dims
>now contains the index (i.e. x[2][3][4]  or x[4][8])
>
>I CAN put a bound on the dimension and use something like
>  int ***x;      /* 3 dimensions */
>  x = (int ***) calloc (N1, sizeof (int **)); 
>  then for each x[i] : x[i] = (int **) calloc (N2, sizeof (int *));
> and x[i][j] = (int *) calloc (N3, sizeof (int));
> so: y = x[a][b][c] is valid;
>
>Yuck (or is it?)
>
>Is there any way to parameterize the (int ***) casts into a #define or an
>array so that a simple loop index will invoke the appropriate level of cast?  
>This may imply that x should be of type void *. 
>Does anyone have any ideas on a solution?  

There is a fairly elegant (in my opinion) way to do this. It looks somewhat
involved. However once the basic routines are written, they need only be
called. Take a look at the code I have sketched out below, and consider
modifying it to suit your needs. The basic "Idea" is to assume that all
pointer types are the same size (and representation) as a void pointer
(I know this isn't always portable), and to use a recursive routine
to allocate your arrays. The routines below declare variable-sized arrays
with variable number of dimensions, of any type. You may be able to
simplify them somewhat by restricting the types to integers, etc.
The corresponding "FreeArray" functions are "left as an exercise for the
reader." Also, for arrays with truly variable numbers of dimensions, you
may need to write a Retrieve(x[a][b],c,type) macro. Take a look at my
suggestions after the functions, also. I haven't tried to compile these
(This is just a sketch - I'm writing off the top of my head), so there may
be errors.

Note that the dims[] array contains dimensions in the
REVERSE order that your post specified. This simplifies the procedures.

-----------
#define POINTERSIZE sizeof(void *)

/* you never need to call this directly (unless you really want to.) */
/* The next function is a nicer "front end" to it. */

void * AllocDimension(size_t elsize, unsigned Ndim, int dims[])
{  
  void * * c;
  int i;

  if (Ndim < 1)
    return(NULL);
  if (Ndim == 1)
    temp = malloc(elsize * dims[1]);
  else
  {
    c = (void * *) malloc(POINTERSIZE * dims[Ndim]);
    for (i=0; i<dims[Ndim]; i++,c++)
      *c = AllocDimension(elsize, Ndim-1, dims);
  }
}

/* Allocate an array with Ndim dimensions, with elements of size elsize */

void * AllocArray(size_t elsize, int Ndim, ... )
{
  va_list argptr;
  int * dims;
  void * retval;
  int i;

  dims = (int *) malloc(Ndim * elsize);
  
  va_start(argptr, Ndim);
  for (i=0; i<Ndim-1; i++)
    dims[Ndim-i-1] = va_arg(argptr, int);
  va_end(argptr);

  retval = AllocDim(elsize, Ndim, dims);
  free(dims);
  return(retval);
}




/*
Then, when you want to declare an array,
*/

/* assuming XDIM,YDIM,ZDIM,DIM1,DIM2,DIM3,DIM4,DIM5 are integers */

#define Array(x, y, type) ((type *) x)[y])

void main(void)
{
  int *** int3array;
  char ***** char5array;
  void * variablearray;

  int3array = AllocArray(sizeof(int),3,XDIM,YDIM,ZDIM);
  char5array = AllocArray(sizeof(char),5,DIM1,DIM2,DIM3,DIM4,DIM5);
  variablearray = AllocArray(sizeof(long),4,DIM1,DIM2,DIM3,DIM4);
  
  int3array[11][22][33] = 42;

  char5array[11][22][33][44][55] = 'Q';

  Array(variablearray[11][22][33],44,long) = 15L;
    .
    :
  FreeArray(int3array, /* what goes in here depends on how you write it -
    see below */ );
  FreeArray(char5array, /* ditto */);
  FreeArray(variablearray, /* ditto */);
}

-----------

If you REALLY wanted to get tricky, you could declare the topmost block
of memory in an array to have extra space at the beginning, and have 
AllocArray store Ndims, elsize, and dims[] in it as well, making the
pointer it returned into the address of the END of this info (which
would also be the start of an array of pointers or elems, depending
on how many dimensions the block had.)

Then routines such as FreeArray() could access this information by 
SUBTRACTING from the pointer passed to them. ((int *)P-1 could be nelems,
(int *)P-2 could be elsize, (int *)P-(3+x) could be the size of dimension
x (==dims[x])), while by ADDING to it, they could access elements of
P like normal ((int *)P+x = P[x], etc.)

This would allow you to simply call FreeArray(P) instead of having to call
FreeArray(P, elsize, nelems, dim[0],dim[1],...,dim[n]); Other routines could
also use the information to process arrays. (macro Array() above could
be changed into functions which would not need type info, for instance.)

>/*----------- Thanks in advance... --------------------------------------+
>| Peter C. Bahrs                                                         |
>| The USL-NASA Project                                                   |
>| Center For Advanced Computer Studies      INET: pcb at gator.cacs.usl.edu |
>| 2 Rex Street                                                           |
>| University of Southwestern Louisiana      ...!uunet!dalsqnt!gator!pcb  | 
>| Lafayette, LA 70504                                                    |
>+-----------------------------------------------------------------------*/

Hope this helps!

Derek Riippa Foster