home *** CD-ROM | disk | FTP | other *** search
/ The C Users' Group Library 1994 August / wc-cdrom-cusersgrouplibrary-1994-08.iso / listings / v_08_11 / 8n11116a < prev    next >
Text File  |  1990-09-24  |  10KB  |  306 lines
  1. /* Listing 2. */
  2.  
  3. /***************************************************
  4.  *
  5.  * Module Name:
  6.  *    daa - dynamic array allocator
  7.  *
  8.  * Description:
  9.  *    this dynamic array allocator is designed to be 
  10.  *    efficient, i.e., it uses only one valloc() for 
  11.  *    the entire array, and flexible. It can allocate
  12.  *    arrays of up to 10 dimensions of any type that
  13.  *    will return a size with the sizeof "C" operator.
  14.  *    it is also very efficient from the point of 
  15.  *    view of array access.  the single valloc() 
  16.  *    ensures locality of reference that eliminates
  17.  *    excess paging encountered with dynamic array 
  18.  *    allocation schemes that use multiple malloc()'s.
  19.  *    Unless the array is larger than a full page 
  20.  *    it will be contained entirely on one page.  
  21.  *    It can allocate arrays of structure, enum or 
  22.  *    union type. A corresponding free(free(ptr)) 
  23.  *    of the allocated area must normally be done 
  24.  *    (unless you want to allocate to program ter-
  25.  *    mination). The sixth parameter returns a 
  26.  *    pointer to do a free on.  do not free on the
  27.  *    function return pointer since arrays of non-
  28.  *    zero subscripted first dimensions will not
  29.  *    point to the allocated space, but some offset 
  30.  *    based on the subscript offset of the first 
  31.  *    dimension. The array is initialized to the 
  32.  *    value pointed to by the last parameter, or 
  33.  *    not initialized if  NULL.  the last parameter 
  34.  *    pointer should point to something with a size
  35.  *    the same as the size of the type in the sizeof
  36.  *    first argument. arrays may be allocated to 
  37.  *    have one or more dimensions with non-zero
  38.  *    integer(+ or -) start subscripts.  thus, 
  39.  *    arrays may be one based or zero based or 
  40.  *    any based for that matter.
  41.  *
  42.  * parameters:
  43.  *    size        - size of the basic array data 
  44.  *                  object, this will usually be
  45.  *                  passed from the sizeof() operator
  46.  *                  in the call
  47.  *
  48.  *    no_dim      - number of array dimensions
  49.  *
  50.  *    dimensions  - a single dimensional array of 
  51.  *                  the dimensions of the array to 
  52.  *                  be allocated
  53.  *
  54.  *    start       - a single dimensional array of 
  55.  *                  integer start subscripts for each 
  56.  *                  corresponding dimension of the
  57.  *                  dimensions array, may be negative
  58.  *
  59.  *    err_code    - pointer to returned error code 
  60.  *                  value
  61.  *
  62.  *    free_ptr    - pointer to the base pointer of 
  63.  *                  the vallocated array space  
  64.  *                  for the caller to free
  65.  *
  66.  *    init_ptr    - initialization pointer parameter
  67.  *                  (NULL if no initialization is 
  68.  *                  desired).
  69.  *
  70.  * returns:
  71.  *    a pointer to char that points to the start of 
  72.  *    the dynamically allocated array area.  this 
  73.  *    will normally need to be cast to the type of 
  74.  *    the subsequent array references.  routine
  75.  *    failure will return NULL.
  76.  *
  77.  * examples:
  78.  *        char *fptr;
  79.  *
  80.  *    allocate 3 dimensional 3x3x3 zeroed int array 
  81.  *    all zero based:
  82.  *        int ***array;
  83.  *        int init = 0;
  84.  *        unsigned d[3] = {3,3,3};
  85.  *        int st[3] = {0,0,0};
  86.  *        array = (int ***)
  87.  *         daa(sizeof(int), 3, d, st, &err_code, 
  88.  *              &fptr, &init);
  89.  *        array[0][2][1] = 1; assign int
  90.  *        free(fptr);
  91.  *
  92.  *    allocate 2 dimensional 2x3 double array 
  93.  *      initialized to 1.0 and one based:
  94.  *        double **array;
  95.  *        double init = 1.0;
  96.  *        unsigned d[2] = {2,3};
  97.  *        int st[2] = {1,1};
  98.  *        array = (double ***)
  99.  *         daa(sizeof(double), 2, d, st, &err_code, 
  100.  *               &fptr, &init);
  101.  *        array[1][2] = 1.5; assign double
  102.  *        free(fptr);
  103.  *
  104.  *    allocate 3 dimensional 4x3x2 array of structures 
  105.  *    initialized to the s_init structure and the 
  106.  *    first index zero based with the second index five
  107.  *    based and the third index -2 based:
  108.  *        struct s {
  109.  *            int i;
  110.  *            double d;
  111.  *        };
  112.  *        struct s s_init = {5, 2.5};
  113.  *        struct s ***array;
  114.  *        unsigned d[3] = {4,3,2};
  115.  *        int st[3] = {0,5,-2};
  116.  *        array = (struct s ***)
  117.  *         daa(sizeof(struct s), 3, d, st, &err_code,
  118.  *               &fptr, &s_init);
  119.  *        array[1][5][-2].i = 1; assign first element
  120.  *        array[3][6][-2].d = 1.5; assign 2nd element
  121.  *        free(fptr);
  122.  *
  123.  * errors:
  124.  *    error free operation returns 0 in *err_code.
  125.  *    any of the following errors will result in a 
  126.  *    NULL pointer return and *err_code set to the 
  127.  *    error number.
  128.  *    1. number of dimensions must be > 0 and <= 10
  129.  *    2. size must be greater than 1
  130.  *    3. no dimension may be zero
  131.  *    4. memory must be successfully allocated
  132.  *        (valloc() != NULL)
  133.  *
  134.  *    failure to index the subscripts in the manner 
  135.  *    established by the starting index array will 
  136.  *    of course result in run time errors.  this is
  137.  *    not an array allocation error but an array 
  138.  *    usage error, similar to any array access on a
  139.  *    static "C" zero based array outside the normal 
  140.  *     0...n-1 bounds.
  141.  *
  142.  ****************************************************
  143.  */
  144. #include <stdio.h>
  145.  
  146. #define MAX_DIM 10 /* max no. of array dimensions */
  147.  
  148. /* these variables are used in the recursive 
  149.    pointer setup routines */
  150. static unsigned long data_size; /* data unit size*/
  151. static unsigned long num_dim; /* # of dimensions */
  152.    /* dimensions of array */
  153. static unsigned long dim[MAX_DIM]; 
  154.    /* product of dimensions from 0 to
  155.       index, dim[0]*dim[1]...dim[index] */
  156. static unsigned long dp[MAX_DIM];
  157.    /* start index of array dimensions */
  158. static int st[MAX_DIM];
  159.    /* size of pointer */
  160. static unsigned long ptr_size = sizeof(char *); 
  161.    /* points to base of allocated array */
  162. static char  *base; 
  163.  
  164. char *daa(size, no_dim, dimensions, 
  165.          start, err_code, free_ptr, init_ptr)
  166.     unsigned size;
  167.     unsigned no_dim;
  168.     unsigned dimensions[];
  169.     int start[];
  170.     unsigned *err_code;
  171.     char **free_ptr;
  172.     char *init_ptr;
  173. {
  174.     /* offset in pointer words of first data byte */
  175.     unsigned long    data_off;
  176.     /* array of current dimension indices */
  177.     unsigned long    dim_ind[MAX_DIM];
  178.     unsigned long    i,j;
  179.     char          *p_data, /* pointer to array data */
  180.                   *p; /* tmp pointer */
  181.  
  182.     char             *al();
  183.     unsigned long    doff();
  184.     unsigned long    off();
  185.  
  186.     *err_code = 0;
  187.     if (no_dim < 1 || no_dim > MAX_DIM){
  188.         *err_code = 1;
  189.         return NULL;
  190.     }
  191.  
  192.     if (size < 1){
  193.         *err_code = 2;
  194.         return NULL;
  195.     }
  196.  
  197.     num_dim = no_dim;
  198.  
  199.     /* set dim_ind to all zeros, the multiple invocations 
  200.      * of the recursive array allocation routine al() 
  201.      * will pass changed by 1 dim_ind arrays to each 
  202.      * invocation of al().  set dim[] and dp[] from 
  203.      * dimensions[] input array and st[] from start[] 
  204.      * input array */
  205.     dp[0] = dimensions[0];
  206.     for (i = 0;i < num_dim;i++){
  207.         dim_ind[i] = 0;
  208.         if (dimensions[i] == 0){
  209.             *err_code = 3;
  210.             return NULL;
  211.         }
  212.         dim[i] = dimensions[i];
  213.         if (i > 0){
  214.             dp[i] = dp[i-1]*dimensions[i];
  215.         }
  216.         st[i] = start[i];
  217.     }
  218.  
  219.     data_size = size;
  220.  
  221.     /* allocate enough memory for the data plus 
  222.        all the array pointers */
  223.     if ((base = (char *)
  224.         valloc((data_off = off(num_dim-1))*ptr_size +
  225.                      dp[num_dim-1]*data_size)) == NULL){
  226.         *err_code = 4;
  227.         return NULL;
  228.     }
  229.  
  230.     /* return allocated space pointer that caller 
  231.      * should use to free space */
  232.     *free_ptr = base;
  233.  
  234.     /* if init_ptr is NULL skip initialization */
  235.     if (init_ptr != NULL){
  236.          /* set p_data to point to the start of 
  237.             the data area */
  238.         p_data = base + data_off*ptr_size;
  239.     
  240.          /* initialize the array */
  241.         for (i = 0;i < dp[num_dim-1];i++){
  242.             p = init_ptr;
  243.             for (j = 0;j < data_size;j++){
  244.                 *p_data++ = *p++;
  245.             }
  246.         }
  247.     }
  248.  
  249.     /* do array setup i.e. all the pointer stuff */
  250.     return al(0, dim_ind);
  251. }
  252.  
  253.     static char *
  254. al(level, dim_ind)
  255.     unsigned long level;
  256.     unsigned long dim_ind[];
  257. {
  258.     char **ptrs;
  259.     unsigned long i;
  260.     if (level < num_dim - 1){
  261.         ptrs = (char **) (base + off(level)*ptr_size +
  262.             ((level == 0)?0:doff(level, dim_ind, 
  263.               dp[level])*ptr_size));
  264.         for (i = 0;i < dim[level];i++){
  265.             dim_ind[level] = i;
  266.             ptrs[i] = al(level+1, dim_ind) -
  267.                 st[level+1]*((level+1 == num_dim-1) ?
  268.                   data_size:ptr_size);
  269.         }
  270.         if (level == 0){
  271.             ptrs -= st[0];
  272.         }
  273.     } else {
  274.         ptrs = (char **) (base + off(level)*ptr_size +
  275.                 doff(level, dim_ind, dp[level])
  276.                 *data_size - ((level == 0) ? 
  277.                 (st[0]*data_size):0));
  278.     }
  279.     return (char *) ptrs;
  280. }
  281.  
  282.     static unsigned long
  283. doff(level, dim_ind, dim_prod)
  284.     unsigned long level;
  285.     unsigned long dim_ind[];
  286.     unsigned long dim_prod;
  287. {
  288.     if (level == 0){
  289.         return 0;
  290.     } else {
  291.         return doff(level-1, dim_ind, dim_prod) +
  292.               (dim_prod/dp[level-1])*dim_ind[level-1];
  293.     }
  294. }
  295.  
  296.     static unsigned long
  297. off(level)
  298.     unsigned long level;
  299. {
  300.     if (level == 0){
  301.         return 0;
  302.     } else {
  303.         return dp[level-1] + off(level-1);
  304.     }
  305. }
  306.