root/maint/gnulib/lib/alloca.c

/* [previous][next][first][last][top][bottom][index][help] */

DEFINITIONS

This source file includes following definitions.
  1. find_stack_direction
  2. alloca

   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)
     /* [previous][next][first][last][top][bottom][index][help] */
  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)
     /* [previous][next][first][last][top][bottom][index][help] */
 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 */

/* [previous][next][first][last][top][bottom][index][help] */