Ruby  2.0.0p247(2013-06-27revision41674)
missing/alloca.c
Go to the documentation of this file.
00001 /* alloca -- (mostly) portable public-domain implementation -- D A Gwyn
00002 
00003    last edit:   86/05/30        rms
00004    include config.h, since on VMS it renames some symbols.
00005    Use xmalloc instead of malloc.
00006 
00007    This implementation of the PWB library alloca() function,
00008    which is used to allocate space off the run-time stack so
00009    that it is automatically reclaimed upon procedure exit,
00010    was inspired by discussions with J. Q. Johnson of Cornell.
00011 
00012    It should work under any C implementation that uses an
00013    actual procedure stack (as opposed to a linked list of
00014    frames).  There are some preprocessor constants that can
00015    be defined when compiling for your specific system, for
00016    improved efficiency; however, the defaults should be okay.
00017 
00018    The general concept of this implementation is to keep
00019    track of all alloca()-allocated blocks, and reclaim any
00020    that are found to be deeper in the stack than the current
00021    invocation.  This heuristic does not reclaim storage as
00022    soon as it becomes invalid, but it will do so eventually.
00023 
00024    As a special case, alloca(0) reclaims storage without
00025    allocating any.  It is a good idea to use alloca(0) in
00026    your main control loop, etc. to force garbage collection.
00027 */
00028 #ifndef lint
00029 static char     SCCSid[] = "@(#)alloca.c        1.1";   /* for the "what" utility */
00030 #endif
00031 
00032 #include "ruby/config.h"
00033 #define X3J11 1            /* config.h should contain void if needed */
00034 
00035 #ifdef C_ALLOCA
00036 
00037 #ifdef emacs
00038 #ifdef static
00039 /* actually, only want this if static is defined as ""
00040    -- this is for usg, in which emacs must undefine static
00041    in order to make unexec workable
00042    */
00043 #ifndef STACK_DIRECTION
00044 you
00045 lose
00046 -- must know STACK_DIRECTION at compile-time
00047 #endif /* STACK_DIRECTION undefined */
00048 #endif /* static */
00049 #endif /* emacs */
00050 
00051 #ifdef X3J11
00052 typedef void    *pointer;               /* generic pointer type */
00053 #else
00054 typedef char    *pointer;               /* generic pointer type */
00055 #endif /* X3J11 */
00056 
00057 #ifndef NULL
00058 #define NULL    0                       /* null pointer constant */
00059 #endif
00060 
00061 #define xmalloc ruby_xmalloc
00062 #define xfree ruby_xfree
00063 
00064 extern void     xfree();
00065 extern pointer  xmalloc();
00066 
00067 /*
00068         Define STACK_DIRECTION if you know the direction of stack
00069         growth for your system; otherwise it will be automatically
00070         deduced at run-time.
00071 
00072         STACK_DIRECTION > 0 => grows toward higher addresses
00073         STACK_DIRECTION < 0 => grows toward lower addresses
00074         STACK_DIRECTION = 0 => direction of growth unknown
00075 */
00076 
00077 #ifndef STACK_DIRECTION
00078 #define STACK_DIRECTION 0               /* direction unknown */
00079 #endif
00080 
00081 #if STACK_DIRECTION != 0
00082 
00083 #define STACK_DIR       STACK_DIRECTION /* known at compile-time */
00084 
00085 #else   /* STACK_DIRECTION == 0; need run-time code */
00086 
00087 static int      stack_dir;              /* 1 or -1 once known */
00088 #define STACK_DIR       stack_dir
00089 
00090 static void
00091 find_stack_direction (/* void */)
00092 {
00093   static char   *addr = NULL;   /* address of first
00094                                    `dummy', once known */
00095   auto char     dummy;          /* to get stack address */
00096 
00097   if (addr == NULL)
00098     {                           /* initial entry */
00099       addr = &dummy;
00100 
00101       find_stack_direction ();  /* recurse once */
00102     }
00103   else                          /* second entry */
00104     if (&dummy > addr)
00105       stack_dir = 1;            /* stack grew upward */
00106     else
00107       stack_dir = -1;           /* stack grew downward */
00108 }
00109 
00110 #endif  /* STACK_DIRECTION == 0 */
00111 
00112 /*
00113         An "alloca header" is used to:
00114         (a) chain together all alloca()ed blocks;
00115         (b) keep track of stack depth.
00116 
00117         It is very important that sizeof(header) agree with malloc()
00118         alignment chunk size.  The following default should work okay.
00119 */
00120 
00121 #ifndef ALIGN_SIZE
00122 #define ALIGN_SIZE      sizeof(double)
00123 #endif
00124 
00125 typedef union hdr
00126 {
00127   char  align[ALIGN_SIZE];      /* to force sizeof(header) */
00128   struct
00129     {
00130       union hdr *next;          /* for chaining headers */
00131       char *deep;               /* for stack depth measure */
00132     } h;
00133 } header;
00134 
00135 /*
00136         alloca( size ) returns a pointer to at least `size' bytes of
00137         storage which will be automatically reclaimed upon exit from
00138         the procedure that called alloca().  Originally, this space
00139         was supposed to be taken from the current stack frame of the
00140         caller, but that method cannot be made to work for some
00141         implementations of C, for example under Gould's UTX/32.
00142 */
00143 
00144 static header *last_alloca_header = NULL; /* -> last alloca header */
00145 
00146 pointer
00147 alloca (size)                   /* returns pointer to storage */
00148      unsigned   size;           /* # bytes to allocate */
00149 {
00150   auto char     probe;          /* probes stack depth: */
00151   register char *depth = &probe;
00152 
00153 #if STACK_DIRECTION == 0
00154   if (STACK_DIR == 0)           /* unknown growth direction */
00155     find_stack_direction ();
00156 #endif
00157 
00158   /* Reclaim garbage, defined as all alloca()ed storage that
00159      was allocated from deeper in the stack than currently. */
00160   {
00161     register header     *hp;    /* traverses linked list */
00162 
00163     for (hp = last_alloca_header; hp != NULL;)
00164       if (STACK_DIR > 0 && hp->h.deep > depth
00165           || STACK_DIR < 0 && hp->h.deep < depth)
00166         {
00167           register header       *np = hp->h.next;
00168 
00169           xfree ((pointer) hp); /* collect garbage */
00170 
00171           hp = np;              /* -> next header */
00172         }
00173       else
00174         break;                  /* rest are not deeper */
00175 
00176     last_alloca_header = hp;    /* -> last valid storage */
00177   }
00178 
00179   if (size == 0)
00180     return NULL;                /* no allocation required */
00181 
00182   /* Allocate combined header + user data storage. */
00183 
00184   {
00185     register pointer    new = xmalloc (sizeof (header) + size);
00186     /* address of header */
00187 
00188     ((header *)new)->h.next = last_alloca_header;
00189     ((header *)new)->h.deep = depth;
00190 
00191     last_alloca_header = (header *)new;
00192 
00193     /* User storage begins just after header. */
00194 
00195     return (pointer)((char *)new + sizeof(header));
00196   }
00197 }
00198 
00199 #endif
00200