/*
 *  NAME
 *	dynamem.3
 *
 *  FUNCTION
 *	dynamem, dynafree -- multidimensional dynamic array handling
 *
 *  SYNOPSIS
 *	char *dynamem(pointer, element_size,
 *				 number_dimensions, dimensions ...)
 *	char **pointer;
 *
 *	dynafree(pointer)
 *	char *pointer;
 *
 *  DESCRIPTION
 *	dynamem() is the multidimensional analogue to malloc().
 *	dynamem allocates a <number_dimensions> dimensional array, 
 *	whose dimensions are stored in a list starting at <dimensions>.
 *	Each array element is of size <element_size>. 
 *	<pointer> is a pointer with <number_dimensions> levels of 
 *	indirection to the memory area, on exiting the procedure this
 *	will point to the beginning of the array.
 *
 *	dynamem() attempts to set up the array required in the same way that 
 *	it would be set up by the compiler at compile time. Thus
 *	a multidimensional dynamically array declared using dynamem()
 *	can be used in exactly the same way as a fixed array declared
 *	by the compiler.   
 *
 *	dynafree() is the dynamem analogue to free(). When passed an
 *	array previously dynamically declared by dynamem(), and the number
 *	of dimensions the function returns this memory to the system.
 *
 *  EXAMPLE
 *	To declare a 4 dimensional array normally one would code:
 *
 *		int array[10][11][12][13];
 *
 *	however, this array is then fixed at compile time. This
 *	same array can be declared dynamically at run time 
 *	using the following code:
 *
 *		int ****array;
 *
 *		array = (int ****) dynamem(&array, sizeof(int), 
 *					4, 10, 11, 12, 13);
 *
 *	(Note that the number of levels of indirection in the cast
 *	is equal to the number of dimensions in the array.)
 *	This enables array sizes to be fixed via, for example, 
 *	command line arguments. 
 *
 *  SEE ALSO
 *	malloc(3)
 *
 *  DIAGNOSTICS
 *	dynamem() returns NULL if it is unable to allocate sufficient
 *	memory for the array.
 *
 *  NOTES
 *	There is obviously some overhead in the actual
 *	setting up of the array; however, this is minimal.
 *	On a SUN system when dynamically allocating 2 arrays of 346000
 *	unsigned characters and one of the same number of shorts all in
 *	two dimensions, the run time of a convolution of a 7x7 Lapacian-
 *	Marr filter over an image of size 720 by 480 varied as follows:
 *
 *	time convolve -fbfilt -X720 -Y480 -e < bubble2 > test.1
 *		222.0 real       213.4 user         1.6 sys  
 *
 *	time convolve -fbfilt -e < bubble2 > test.2
 *		225.2 real       212.5 user         2.7 sys  
 *
 *	which is probably adequate. From this we can see that 
 *	it takes 1.1 secs for the fixed array to be set up
 *	and zeroed and only 0.9 secs for the array to be
 *	dynamically declared using dynamem(); 
 *	however, using dynamem() the array is not initialized to
 *	0 and this is the reason for the 0.2 speed increase.
 *
 *	This code should really be changed to allocate one extra int 
 *	location four bytes BEFORE the array itself.  Store the number of 
 *	dimensions in that hidden location.
 *
 *	Should be revised to use the stdarg.h variable argument handling
 *	methods defined by ANSI C.
 *
 *  VERSION
 *	1	Kevin Northover           1988-02-23
 *
 *	dynamem was developed by Gareth Waddell at Bristol University, UK
 *	and was posted to the UseNet unix user's network.
 *	The code is public domain, dynafree bug fixed and
 *	debugging macros added by KJEN.
 */

extern char *malloc();

#include "dbug.h"		/* Fred Fish DBUG macro package */

char *
dynamem(p, s, d, d1)
char **p;
int s, d, d1;
{
	int max,		/* size of array to be declared */
	*q;			/* pointer to dimension list */
	char **r,		/* pointer to begining of the array of the
				 * pointers for a dimension */
	**s1, *t, *tree;	/* base pointer to begining of first array */
	int i,			/* loop counters */
	 j;

	DBUG_ENTER("dynamem");

	r = &tree;
	q = &d1;		/* first dimension */
	max = 1;

	/* for each of the dimensions but the last */
	for (i = 0; i < d - 1; i++, q++) {
	    max *= (*q);
	    if ( (char *) 0 == 
		(r[0] = malloc((unsigned) max * sizeof (char **))) ) {
			dynafree(tree, d);
			DBUG_RETURN( r[0] );
	    }
	    DBUG_PRINT("mchk", ("pointer block at address %lx", r[0]));
	    r = (char **) r[0];	/* step through to begining of next
					 * dimension array */
	}
	max *= s * (*q);	/* grab actual array memory */
	if ( (char *) 0 == (r[0] = malloc((unsigned) max)) ) {
		dynafree(tree, d);
		DBUG_RETURN( r[0] );
	}
	DBUG_PRINT("mchk", ("data block at address %lx", r[0]));

	/*
	 * r is now set to point to the begining of each array so that we can
	 * use it to scan down each array rather than having to go across and
	 * then down 
	 */
	r = (char **) tree;	/* back to the begining of list of arrays */
	q = &d1;		/* back to the first dimension */
	max = 1;
	for (i = 0; i < d - 2; i++, q++) {
	    /* we deal with the last array of pointers later */
	    
	    max *= (*q);	/* number of elements in this dimension */

	    /* scan down array for first and subsequent elements */
	    for (j = 1, s1 = r + 1, t = r[0]; j < max; j++) {
		/*
		 *  modify each of the pointers so that it points to
		 * the correct position (sub-array) of the next
		 * dimension array. s1 is the current position in the
		 * current array. t is the current position in the
		 * next array. t is incremented before s is, but it
		 * starts off one behind. *(q+1) is the dimension of
		 * the next array. 
		 */
		*s1++ = (t += sizeof (char **) * *(q + 1));
	    }
	    r = (char **) r[0];	/* step through to begining of next
					 * dimension array */
	}

	/* max is total number of elements in the last pointer array */
	max *= (*q);
	for (j = 1, s1 = r + 1, t = r[0]; j < max; j++)	{
	    /* same as previous loop, but different size factor */
	    *s1++ = (t += s * *(q + 1));
	}
	DBUG_RETURN(tree);		/* return base pointer */
}

dynafree(r, d)
char *r;
int d;
{
	char **p;
	int i, j;

	DBUG_ENTER("dynafree");

	/* we need to count the dimensions to guarantee termination before
	 * lots of random memory gets stomped -- kjen 880223
	 * free in reverse order of allocation
	 */
	for ( j = d-1; j >= 0; j-- ) {
	    for (p = &r, i=0; p && (i < j); p = (char **) *p, i++) ;
	    if ( p ) {
	    	DBUG_PRINT("mchk", ("freeing block %lx", *p));
	    	free(*p);
	    }
	}
	DBUG_RETURN(0);
}