gnulib/import/alloca.c

   1 /* alloca.c -- allocate automatically reclaimed memory
   2    This file is in the public domain.  */
   3
   4 /* (Mostly) portable implementation -- D A Gwyn
   5
   6    This implementation of the PWB library alloca function,
   7    which is used to allocate space off the run-time stack so
   8    that it is automatically reclaimed upon procedure exit,
   9    was inspired by discussions with J. Q. Johnson of Cornell.
  10    J.Otto Tennant <jot@cray.com> contributed the Cray support.
  11
  12    There are some preprocessor constants that can
  13    be defined when compiling for your specific system, for
  14    improved efficiency; however, the defaults should be okay.
  15
  16    The general concept of this implementation is to keep
  17    track of all alloca-allocated blocks, and reclaim any
  18    that are found to be deeper in the stack than the current
  19    invocation.  This heuristic does not reclaim storage as
  20    soon as it becomes invalid, but it will do so eventually.
  21
  22    As a special case, alloca(0) reclaims storage without
  23    allocating any.  It is a good idea to use alloca(0) in
  24    your main control loop, etc. to force garbage collection.  */
  25
  26 #include <config.h>
  27
  28 #include <alloca.h>
  29
  30 #include <string.h>
  31 #include <stdlib.h>
  32
  33 #ifdef emacs
  34 # include "lisp.h"
  35 # include "blockinput.h"
  36 # ifdef EMACS_FREE
  37 #  undef free
  38 #  define free EMACS_FREE
  39 # endif
  40 #else
  41 # define memory_full() abort ()
  42 #endif
  43
  44 /* If compiling with GCC or clang, this file is not needed.  */
  45 #if !(defined __GNUC__ || defined __clang__)
  46
  47 /* If someone has defined alloca as a macro,
  48    there must be some other way alloca is supposed to work.  */
  49 # ifndef alloca
  50
  51 #  ifdef emacs
  52 #   ifdef static
  53 /* actually, only want this if static is defined as ""
  54    -- this is for usg, in which emacs must undefine static
  55    in order to make unexec workable
  56    */
  57 #    ifndef STACK_DIRECTION
  58 you
  59 lose
  60 -- must know STACK_DIRECTION at compile-time
  61 /* Using #error here is not wise since this file should work for
  62    old and obscure compilers.  */
  63 #    endif /* STACK_DIRECTION undefined */
  64 #   endif /* static */
  65 #  endif /* emacs */
  66
  67 /* Define STACK_DIRECTION if you know the direction of stack
  68    growth for your system; otherwise it will be automatically
  69    deduced at run-time.
  70
  71    STACK_DIRECTION > 0 => grows toward higher addresses
  72    STACK_DIRECTION < 0 => grows toward lower addresses
  73    STACK_DIRECTION = 0 => direction of growth unknown  */
  74
  75 #  ifndef STACK_DIRECTION
  76 #   define STACK_DIRECTION      0       /* Direction unknown.  */
  77 #  endif
  78
  79 #  if STACK_DIRECTION != 0
  80
  81 #   define STACK_DIR    STACK_DIRECTION /* Known at compile-time.  */
  82
  83 #  else /* STACK_DIRECTION == 0; need run-time code.  */
  84
  85 static int stack_dir;           /* 1 or -1 once known.  */
  86 #   define STACK_DIR    stack_dir
  87
  88 static int
  89 find_stack_direction (int *addr, int depth)
  90 {
  91   int dir, dummy = 0;
  92   if (! addr)
  93     addr = &dummy;
  94   *addr = addr < &dummy ? 1 : addr == &dummy ? 0 : -1;
  95   dir = depth ? find_stack_direction (addr, depth - 1) : 0;
  96   return dir + dummy;
  97 }
  98
  99 #  endif /* STACK_DIRECTION == 0 */
 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 #  ifndef       ALIGN_SIZE
 109 #   define ALIGN_SIZE   sizeof(double)
 110 #  endif
 111
 112 typedef union hdr
 113 {
 114   char align[ALIGN_SIZE];       /* To force sizeof(header).  */
 115   struct
 116     {
 117       union hdr *next;          /* For chaining headers.  */
 118       char *deep;               /* For stack depth measure.  */
 119     } h;
 120 } header;
 121
 122 static header *last_alloca_header = NULL;       /* -> last alloca header.  */
 123
 124 /* Return a pointer to at least SIZE bytes of storage,
 125    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 void *
 132 alloca (size_t size)
 133 {
 134   auto char probe;              /* Probes stack depth: */
 135   register char *depth = &probe;
 136
 137 #  if STACK_DIRECTION == 0
 138   if (STACK_DIR == 0)           /* Unknown growth direction.  */
 139     STACK_DIR = find_stack_direction (NULL, (size & 1) + 20);
 140 #  endif
 141
 142   /* Reclaim garbage, defined as all alloca'd storage that
 143      was allocated from deeper in the stack than currently.  */
 144
 145   {
 146     register header *hp;        /* Traverses linked list.  */
 147
 148 #  ifdef emacs
 149     BLOCK_INPUT;
 150 #  endif
 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           free (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 #  ifdef emacs
 168     UNBLOCK_INPUT;
 169 #  endif
 170   }
 171
 172   if (size == 0)
 173     return NULL;                /* No allocation required.  */
 174
 175   /* Allocate combined header + user data storage.  */
 176
 177   {
 178     /* Address of header.  */
 179     register header *new;
 180
 181     size_t combined_size = sizeof (header) + size;
 182     if (combined_size < sizeof (header))
 183       memory_full ();
 184
 185     new = malloc (combined_size);
 186
 187     if (! new)
 188       memory_full ();
 189
 190     new->h.next = last_alloca_header;
 191     new->h.deep = depth;
 192
 193     last_alloca_header = new;
 194
 195     /* User storage begins just after header.  */
 196
 197     return (void *) (new + 1);
 198   }
 199 }
 200
 201 # endif /* no alloca */
 202 #endif /* not GCC || clang */