home *** CD-ROM | disk | FTP | other *** search
/ Frozen Fish 1: Amiga / FrozenFish-Apr94.iso / bbs / alib / d3xx / d352 / mg.lha / MG / src.LZH / mg / alloca.c next >
C/C++ Source or Header  |  1990-05-23  |  5KB  |  165 lines
  1. /*
  2.  * Note to mg porters: this is included on the off chance you don't have an
  3.  * alloca, and want to use the regexp code. I seriously recommend not using
  4.  * it if you can avoid it.
  5.  */
  6.  
  7. /*
  8.  * alloca -- (mostly) portable public-domain implementation -- D A Gwyn
  9.  * 
  10.  * This implementation of the PWB library alloca() function, which is used to
  11.  * allocate space off the run-time stack so that it is automatically
  12.  * reclaimed upon procedure exit, was inspired by discussions with J. Q.
  13.  * Johnson of Cornell.
  14.  * 
  15.  * It should work under any C implementation that uses an actual procedure stack
  16.  * (as opposed to a linked list of frames).  There are some preprocessor
  17.  * constants that can be defined when compiling for your specific system, for
  18.  * improved efficiency; however, the defaults should be okay.
  19.  * 
  20.  * The general concept of this implementation is to keep track of all
  21.  * alloca()-allocated blocks, and reclaim any that are found to be deeper in
  22.  * the stack than the current invocation.  This heuristic does not reclaim
  23.  * storage as soon as it becomes invalid, but it will do so eventually.
  24.  * 
  25.  * As a special case, alloca(0) reclaims storage without allocating any.  It is
  26.  * a good idea to use alloca(0) in your main control loop, etc. to force
  27.  * garbage collection.
  28.  */
  29. #include "regexp.h"
  30. #ifdef    REGEXP
  31.  
  32. #include "def.h"        /* Get me lotsa defines */
  33.  
  34. #ifdef ANSI
  35. #include <stdlib.h>
  36. #endif
  37.  
  38. typedef VOID   *pointer;    /* generic pointer type */
  39.  
  40. /*
  41.  * Define STACK_DIRECTION if you know the direction of stack growth for your
  42.  * system; otherwise it will be automatically deduced at run-time.
  43.  * 
  44.  * STACK_DIRECTION > 0 => grows toward higher addresses STACK_DIRECTION < 0 =>
  45.  * grows toward lower addresses STACK_DIRECTION undefined => direction of
  46.  * growth unknown
  47.  */
  48.  
  49.  
  50. #ifdef STACK_DIRECTION
  51.  
  52. #define    STACK_DIR    STACK_DIRECTION    /* known at compile-time */
  53.  
  54. #else                /* STACK_DIRECTION undefined -> need to find
  55.                  * it at compile time */
  56.  
  57. static int      stack_dir;    /* 1 or -1 once known */
  58. #define    STACK_DIR    stack_dir
  59.  
  60. static          VOID
  61. find_stack_direction PROTO(( VOID ))
  62. {
  63.     static char    *addr = NULL;    /* address of first `dummy', once
  64.                      * known */
  65.     auto char       dummy;    /* to get stack address */
  66.  
  67.     if (addr == NULL) {    /* initial entry */
  68.         addr = &dummy;
  69.  
  70.         find_stack_direction();    /* recurse once */
  71.     } else
  72.      /* second entry */ if (&dummy > addr)
  73.         stack_dir = 1;    /* stack grew upward */
  74.     else
  75.         stack_dir = -1;    /* stack grew downward */
  76. }
  77.  
  78. #endif                /* STACK_DIRECTION */
  79.  
  80. /*
  81.  * An "alloca header" is used to: (a) chain together all alloca()ed blocks;
  82.  * (b) keep track of stack depth.
  83.  * 
  84.  * It is very important that sizeof(header) agree with malloc() alignment chunk
  85.  * size.  The following default should work okay.
  86.  */
  87.  
  88. #ifndef    ALIGN_SIZE
  89. #define    ALIGN_SIZE    sizeof(double)
  90. #endif
  91.  
  92. typedef union hdr {
  93.     char            align[ALIGN_SIZE];    /* to force sizeof(header) */
  94.     struct {
  95.         union hdr      *next;    /* for chaining headers */
  96.         char           *deep;    /* for stack depth measure */
  97.     }               h;
  98. }               header;
  99.  
  100. /*
  101.  * alloca( size ) returns a pointer to at least `size' bytes of storage which
  102.  * will be automatically reclaimed upon exit from the procedure that called
  103.  * alloca().  Originally, this space was supposed to be taken from the
  104.  * current stack frame of the caller, but that method cannot be made to work
  105.  * for some implementations of C, for example under Gould's UTX/32.
  106.  */
  107.  
  108. static header  *last_alloca_header = NULL;    /* -> last alloca header */
  109.  
  110. pointer
  111. alloca(size)            /* returns pointer to storage */
  112.     unsigned        size;    /* # bytes to allocate */
  113. {
  114.     auto char       probe;    /* probes stack depth: */
  115.     register char  *depth = &probe;
  116.  
  117. #ifndef STACK_DIRECTION
  118.     if (STACK_DIR == 0)    /* unknown growth direction */
  119.         find_stack_direction();
  120. #endif
  121.     /*
  122.      * Reclaim garbage, defined as all alloca()ed storage that was
  123.      * allocated from deeper in the stack than currently.
  124.      */
  125.  
  126.     {
  127.         register header *hp;    /* traverses linked list */
  128.  
  129.         for (hp = last_alloca_header; hp != NULL;)
  130.             if (STACK_DIR > 0 && hp->h.deep > depth
  131.                 || STACK_DIR < 0 && hp->h.deep < depth) {
  132.                 register header *np = hp->h.next;
  133.  
  134.                 free((pointer) hp);    /* collect garbage */
  135.  
  136.                 hp = np;    /* -> next header */
  137.             } else
  138.                 break;    /* rest are not deeper */
  139.  
  140.         last_alloca_header = hp;    /* -> last valid storage */
  141.     }
  142.  
  143.     if (size == 0)
  144.         return NULL;    /* no allocation required */
  145.  
  146.     /* Allocate combined header + user data storage. */
  147.  
  148.     {
  149.         register pointer new = malloc(sizeof(header) + size);
  150.         /* address of header */
  151.  
  152.         ((header *) new)->h.next = last_alloca_header;
  153.         ((header *) new)->h.deep = depth;
  154.  
  155.         last_alloca_header = (header *) new;
  156.  
  157.         /* User storage begins just after header. */
  158.  
  159.         return (pointer) ((char *) new + sizeof(header));
  160.     }
  161. }
  162. #else
  163. #include "nullfile.h"
  164. #endif
  165.