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 #include "common.h"
  37
  38 typedef void *pointer;          /* generic pointer type */
  39 #define NULL    0               /* null pointer constant */
  40
  41 extern void free ();
  42 extern pointer xmalloc ();
  43
  44 /*
  45    Define STACK_DIRECTION if you know the direction of stack
  46    growth for your system; otherwise it will be automatically
  47    deduced at run-time.
  48
  49    STACK_DIRECTION > 0 => grows toward higher addresses
  50    STACK_DIRECTION < 0 => grows toward lower addresses
  51    STACK_DIRECTION = 0 => direction of growth unknown
  52  */
  53
  54 #ifndef STACK_DIRECTION
  55 #define STACK_DIRECTION 0       /* direction unknown */
  56 #endif
  57
  58 #if STACK_DIRECTION != 0
  59
  60 #define STACK_DIR       STACK_DIRECTION         /* known at compile-time */
  61
  62 #else /* STACK_DIRECTION == 0; need run-time code */
  63
  64 static int stack_dir;           /* 1 or -1 once known */
  65 #define STACK_DIR       stack_dir
  66
  67 static void
  68 find_stack_direction (void)
  69 {
  70   static char *addr = NULL;     /* address of first
  71                                    `dummy', once known */
  72   auto char dummy;              /* to get stack address */
  73
  74   if (addr == NULL)
  75     {                           /* initial entry */
  76       addr = &dummy;
  77
  78       find_stack_direction ();  /* recurse once */
  79     }
  80   else
  81     /* second entry */ if (&dummy > addr)
  82     stack_dir = 1;              /* stack grew upward */
  83   else
  84     stack_dir = -1;             /* stack grew downward */
  85 }
  86
  87 #endif /* STACK_DIRECTION == 0 */
  88
  89 /*
  90    An "alloca header" is used to:
  91    (a) chain together all alloca()ed blocks;
  92    (b) keep track of stack depth.
  93
  94    PORTME: It is very important that sizeof(header) agree with
  95    malloc() alignment chunk size.  The following default should
  96    work okay.  */
  97
  98 #ifndef ALIGN_SIZE
  99 #define ALIGN_SIZE      sizeof(double)
 100 #endif
 101
 102 typedef union hdr
 103 {
 104   char align[ALIGN_SIZE];       /* to force sizeof(header) */
 105   struct
 106     {
 107       union hdr *next;          /* for chaining headers */
 108       char *deep;               /* for stack depth measure */
 109     }
 110   h;
 111 }
 112 header;
 113
 114 /*
 115    alloca( size ) returns a pointer to at least `size' bytes of
 116    storage which will be automatically reclaimed upon exit from
 117    the procedure that called alloca().  Originally, this space
 118    was supposed to be taken from the current stack frame of the
 119    caller, but that method cannot be made to work for some
 120    implementations of C, for example under Gould's UTX/32.
 121  */
 122
 123 static header *last_alloca_header = NULL;       /* -> last alloca header */
 124
 125 pointer
 126 alloca (unsigned size)          /* returns pointer to storage */
 127 {
 128   auto char probe;              /* probes stack depth: */
 129   register char *depth = &probe;
 130
 131 #if STACK_DIRECTION == 0
 132   if (STACK_DIR == 0)           /* unknown growth direction */
 133     find_stack_direction ();
 134 #endif
 135
 136   /* Reclaim garbage, defined as all alloca()ed storage that
 137      was allocated from deeper in the stack than currently. */
 138
 139   {
 140     register header *hp;        /* traverses linked list */
 141
 142     for (hp = last_alloca_header; hp != NULL;)
 143       if (STACK_DIR > 0 && hp->h.deep > depth
 144           || STACK_DIR < 0 && hp->h.deep < depth)
 145         {
 146           register header *np = hp->h.next;
 147
 148           free ((pointer) hp);  /* collect garbage */
 149
 150           hp = np;              /* -> next header */
 151         }
 152       else
 153         break;                  /* rest are not deeper */
 154
 155     last_alloca_header = hp;    /* -> last valid storage */
 156   }
 157
 158   if (size == 0)
 159     return NULL;                /* no allocation required */
 160
 161   /* Allocate combined header + user data storage. */
 162
 163   {
 164     register pointer new = xmalloc (sizeof (header) + size);
 165     /* address of header */
 166
 167     ((header *) new)->h.next = last_alloca_header;
 168     ((header *) new)->h.deep = depth;
 169
 170     last_alloca_header = (header *) new;
 171
 172     /* User storage begins just after header. */
 173
 174     return (pointer) ((char *) new + sizeof (header));
 175   }
 176 }
 177
 178 #endif /* !__GNUC__ && !__BORLANDC__ */