lib/alloca.c

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