missing/alloca.c

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