home *** CD-ROM | disk | FTP | other *** search
/ Amiga Elysian Archive / AmigaElysianArchive.iso / prog / c / dyname.lha / dynamem.c next >
C/C++ Source or Header  |  1990-06-04  |  6KB  |  201 lines
  1. /*
  2.  *  NAME
  3.  *    dynamem.3
  4.  *
  5.  *  FUNCTION
  6.  *    dynamem, dynafree -- multidimensional dynamic array handling
  7.  *
  8.  *  SYNOPSIS
  9.  *    char *dynamem(pointer, element_size,
  10.  *                 number_dimensions, dimensions ...)
  11.  *    char **pointer;
  12.  *
  13.  *    dynafree(pointer)
  14.  *    char *pointer;
  15.  *
  16.  *  DESCRIPTION
  17.  *    dynamem() is the multidimensional analogue to malloc().
  18.  *    dynamem allocates a <number_dimensions> dimensional array, 
  19.  *    whose dimensions are stored in a list starting at <dimensions>.
  20.  *    Each array element is of size <element_size>. 
  21.  *    <pointer> is a pointer with <number_dimensions> levels of 
  22.  *    indirection to the memory area, on exiting the procedure this
  23.  *    will point to the beginning of the array.
  24.  *
  25.  *    dynamem() attempts to set up the array required in the same way that 
  26.  *    it would be set up by the compiler at compile time. Thus
  27.  *    a multidimensional dynamically array declared using dynamem()
  28.  *    can be used in exactly the same way as a fixed array declared
  29.  *    by the compiler.   
  30.  *
  31.  *    dynafree() is the dynamem analogue to free(). When passed an
  32.  *    array previously dynamically declared by dynamem(), and the number
  33.  *    of dimensions the function returns this memory to the system.
  34.  *
  35.  *  EXAMPLE
  36.  *    To declare a 4 dimensional array normally one would code:
  37.  *
  38.  *        int array[10][11][12][13];
  39.  *
  40.  *    however, this array is then fixed at compile time. This
  41.  *    same array can be declared dynamically at run time 
  42.  *    using the following code:
  43.  *
  44.  *        int ****array;
  45.  *
  46.  *        array = (int ****) dynamem(&array, sizeof(int), 
  47.  *                    4, 10, 11, 12, 13);
  48.  *
  49.  *    (Note that the number of levels of indirection in the cast
  50.  *    is equal to the number of dimensions in the array.)
  51.  *    This enables array sizes to be fixed via, for example, 
  52.  *    command line arguments. 
  53.  *
  54.  *  SEE ALSO
  55.  *    malloc(3)
  56.  *
  57.  *  DIAGNOSTICS
  58.  *    dynamem() returns NULL if it is unable to allocate sufficient
  59.  *    memory for the array.
  60.  *
  61.  *  NOTES
  62.  *    There is obviously some overhead in the actual
  63.  *    setting up of the array; however, this is minimal.
  64.  *    On a SUN system when dynamically allocating 2 arrays of 346000
  65.  *    unsigned characters and one of the same number of shorts all in
  66.  *    two dimensions, the run time of a convolution of a 7x7 Lapacian-
  67.  *    Marr filter over an image of size 720 by 480 varied as follows:
  68.  *
  69.  *    time convolve -fbfilt -X720 -Y480 -e < bubble2 > test.1
  70.  *        222.0 real       213.4 user         1.6 sys  
  71.  *
  72.  *    time convolve -fbfilt -e < bubble2 > test.2
  73.  *        225.2 real       212.5 user         2.7 sys  
  74.  *
  75.  *    which is probably adequate. From this we can see that 
  76.  *    it takes 1.1 secs for the fixed array to be set up
  77.  *    and zeroed and only 0.9 secs for the array to be
  78.  *    dynamically declared using dynamem(); 
  79.  *    however, using dynamem() the array is not initialized to
  80.  *    0 and this is the reason for the 0.2 speed increase.
  81.  *
  82.  *    This code should really be changed to allocate one extra int 
  83.  *    location four bytes BEFORE the array itself.  Store the number of 
  84.  *    dimensions in that hidden location.
  85.  *
  86.  *    Should be revised to use the stdarg.h variable argument handling
  87.  *    methods defined by ANSI C.
  88.  *
  89.  *  VERSION
  90.  *    1    Kevin Northover           1988-02-23
  91.  *
  92.  *    dynamem was developed by Gareth Waddell at Bristol University, UK
  93.  *    and was posted to the UseNet unix user's network.
  94.  *    The code is public domain, dynafree bug fixed and
  95.  *    debugging macros added by KJEN.
  96.  */
  97.  
  98. extern char *malloc();
  99.  
  100. #include "dbug.h"        /* Fred Fish DBUG macro package */
  101.  
  102. char *
  103. dynamem(p, s, d, d1)
  104. char **p;
  105. int s, d, d1;
  106. {
  107.     int max,        /* size of array to be declared */
  108.     *q;            /* pointer to dimension list */
  109.     char **r,        /* pointer to begining of the array of the
  110.                  * pointers for a dimension */
  111.     **s1, *t, *tree;    /* base pointer to begining of first array */
  112.     int i,            /* loop counters */
  113.      j;
  114.  
  115.     DBUG_ENTER("dynamem");
  116.  
  117.     r = &tree;
  118.     q = &d1;        /* first dimension */
  119.     max = 1;
  120.  
  121.     /* for each of the dimensions but the last */
  122.     for (i = 0; i < d - 1; i++, q++) {
  123.         max *= (*q);
  124.         if ( (char *) 0 == 
  125.         (r[0] = malloc((unsigned) max * sizeof (char **))) ) {
  126.             dynafree(tree, d);
  127.             DBUG_RETURN( r[0] );
  128.         }
  129.         DBUG_PRINT("mchk", ("pointer block at address %lx", r[0]));
  130.         r = (char **) r[0];    /* step through to begining of next
  131.                      * dimension array */
  132.     }
  133.     max *= s * (*q);    /* grab actual array memory */
  134.     if ( (char *) 0 == (r[0] = malloc((unsigned) max)) ) {
  135.         dynafree(tree, d);
  136.         DBUG_RETURN( r[0] );
  137.     }
  138.     DBUG_PRINT("mchk", ("data block at address %lx", r[0]));
  139.  
  140.     /*
  141.      * r is now set to point to the begining of each array so that we can
  142.      * use it to scan down each array rather than having to go across and
  143.      * then down 
  144.      */
  145.     r = (char **) tree;    /* back to the begining of list of arrays */
  146.     q = &d1;        /* back to the first dimension */
  147.     max = 1;
  148.     for (i = 0; i < d - 2; i++, q++) {
  149.         /* we deal with the last array of pointers later */
  150.         
  151.         max *= (*q);    /* number of elements in this dimension */
  152.  
  153.         /* scan down array for first and subsequent elements */
  154.         for (j = 1, s1 = r + 1, t = r[0]; j < max; j++) {
  155.         /*
  156.          *  modify each of the pointers so that it points to
  157.          * the correct position (sub-array) of the next
  158.          * dimension array. s1 is the current position in the
  159.          * current array. t is the current position in the
  160.          * next array. t is incremented before s is, but it
  161.          * starts off one behind. *(q+1) is the dimension of
  162.          * the next array. 
  163.          */
  164.         *s1++ = (t += sizeof (char **) * *(q + 1));
  165.         }
  166.         r = (char **) r[0];    /* step through to begining of next
  167.                      * dimension array */
  168.     }
  169.  
  170.     /* max is total number of elements in the last pointer array */
  171.     max *= (*q);
  172.     for (j = 1, s1 = r + 1, t = r[0]; j < max; j++)    {
  173.         /* same as previous loop, but different size factor */
  174.         *s1++ = (t += s * *(q + 1));
  175.     }
  176.     DBUG_RETURN(tree);        /* return base pointer */
  177. }
  178.  
  179. dynafree(r, d)
  180. char *r;
  181. int d;
  182. {
  183.     char **p;
  184.     int i, j;
  185.  
  186.     DBUG_ENTER("dynafree");
  187.  
  188.     /* we need to count the dimensions to guarantee termination before
  189.      * lots of random memory gets stomped -- kjen 880223
  190.      * free in reverse order of allocation
  191.      */
  192.     for ( j = d-1; j >= 0; j-- ) {
  193.         for (p = &r, i=0; p && (i < j); p = (char **) *p, i++) ;
  194.         if ( p ) {
  195.             DBUG_PRINT("mchk", ("freeing block %lx", *p));
  196.             free(*p);
  197.         }
  198.     }
  199.     DBUG_RETURN(0);
  200. }
  201.