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