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