lib/misc/alloca.c

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