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