4.3BSD - /usr/src/new/emacs/src/alloca.c

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

Defined functions

Defined variables

Defined union's

Defined typedef's

Defined macros