git.sesse.net Git - rdpsrv/blob - Xserver/programs/Xserver/os/genalloca.c

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