Ruby
2.0.0p247(2013-06-27revision41674)
|
00001 /* alloca -- (mostly) portable public-domain implementation -- D A Gwyn 00002 00003 last edit: 86/05/30 rms 00004 include config.h, since on VMS it renames some symbols. 00005 Use xmalloc instead of malloc. 00006 00007 This implementation of the PWB library alloca() function, 00008 which is used to allocate space off the run-time stack so 00009 that it is automatically reclaimed upon procedure exit, 00010 was inspired by discussions with J. Q. Johnson of Cornell. 00011 00012 It should work under any C implementation that uses an 00013 actual procedure stack (as opposed to a linked list of 00014 frames). There are some preprocessor constants that can 00015 be defined when compiling for your specific system, for 00016 improved efficiency; however, the defaults should be okay. 00017 00018 The general concept of this implementation is to keep 00019 track of all alloca()-allocated blocks, and reclaim any 00020 that are found to be deeper in the stack than the current 00021 invocation. This heuristic does not reclaim storage as 00022 soon as it becomes invalid, but it will do so eventually. 00023 00024 As a special case, alloca(0) reclaims storage without 00025 allocating any. It is a good idea to use alloca(0) in 00026 your main control loop, etc. to force garbage collection. 00027 */ 00028 #ifndef lint 00029 static char SCCSid[] = "@(#)alloca.c 1.1"; /* for the "what" utility */ 00030 #endif 00031 00032 #include "ruby/config.h" 00033 #define X3J11 1 /* config.h should contain void if needed */ 00034 00035 #ifdef C_ALLOCA 00036 00037 #ifdef emacs 00038 #ifdef static 00039 /* actually, only want this if static is defined as "" 00040 -- this is for usg, in which emacs must undefine static 00041 in order to make unexec workable 00042 */ 00043 #ifndef STACK_DIRECTION 00044 you 00045 lose 00046 -- must know STACK_DIRECTION at compile-time 00047 #endif /* STACK_DIRECTION undefined */ 00048 #endif /* static */ 00049 #endif /* emacs */ 00050 00051 #ifdef X3J11 00052 typedef void *pointer; /* generic pointer type */ 00053 #else 00054 typedef char *pointer; /* generic pointer type */ 00055 #endif /* X3J11 */ 00056 00057 #ifndef NULL 00058 #define NULL 0 /* null pointer constant */ 00059 #endif 00060 00061 #define xmalloc ruby_xmalloc 00062 #define xfree ruby_xfree 00063 00064 extern void xfree(); 00065 extern pointer xmalloc(); 00066 00067 /* 00068 Define STACK_DIRECTION if you know the direction of stack 00069 growth for your system; otherwise it will be automatically 00070 deduced at run-time. 00071 00072 STACK_DIRECTION > 0 => grows toward higher addresses 00073 STACK_DIRECTION < 0 => grows toward lower addresses 00074 STACK_DIRECTION = 0 => direction of growth unknown 00075 */ 00076 00077 #ifndef STACK_DIRECTION 00078 #define STACK_DIRECTION 0 /* direction unknown */ 00079 #endif 00080 00081 #if STACK_DIRECTION != 0 00082 00083 #define STACK_DIR STACK_DIRECTION /* known at compile-time */ 00084 00085 #else /* STACK_DIRECTION == 0; need run-time code */ 00086 00087 static int stack_dir; /* 1 or -1 once known */ 00088 #define STACK_DIR stack_dir 00089 00090 static void 00091 find_stack_direction (/* void */) 00092 { 00093 static char *addr = NULL; /* address of first 00094 `dummy', once known */ 00095 auto char dummy; /* to get stack address */ 00096 00097 if (addr == NULL) 00098 { /* initial entry */ 00099 addr = &dummy; 00100 00101 find_stack_direction (); /* recurse once */ 00102 } 00103 else /* second entry */ 00104 if (&dummy > addr) 00105 stack_dir = 1; /* stack grew upward */ 00106 else 00107 stack_dir = -1; /* stack grew downward */ 00108 } 00109 00110 #endif /* STACK_DIRECTION == 0 */ 00111 00112 /* 00113 An "alloca header" is used to: 00114 (a) chain together all alloca()ed blocks; 00115 (b) keep track of stack depth. 00116 00117 It is very important that sizeof(header) agree with malloc() 00118 alignment chunk size. The following default should work okay. 00119 */ 00120 00121 #ifndef ALIGN_SIZE 00122 #define ALIGN_SIZE sizeof(double) 00123 #endif 00124 00125 typedef union hdr 00126 { 00127 char align[ALIGN_SIZE]; /* to force sizeof(header) */ 00128 struct 00129 { 00130 union hdr *next; /* for chaining headers */ 00131 char *deep; /* for stack depth measure */ 00132 } h; 00133 } header; 00134 00135 /* 00136 alloca( size ) returns a pointer to at least `size' bytes of 00137 storage which will be automatically reclaimed upon exit from 00138 the procedure that called alloca(). Originally, this space 00139 was supposed to be taken from the current stack frame of the 00140 caller, but that method cannot be made to work for some 00141 implementations of C, for example under Gould's UTX/32. 00142 */ 00143 00144 static header *last_alloca_header = NULL; /* -> last alloca header */ 00145 00146 pointer 00147 alloca (size) /* returns pointer to storage */ 00148 unsigned size; /* # bytes to allocate */ 00149 { 00150 auto char probe; /* probes stack depth: */ 00151 register char *depth = &probe; 00152 00153 #if STACK_DIRECTION == 0 00154 if (STACK_DIR == 0) /* unknown growth direction */ 00155 find_stack_direction (); 00156 #endif 00157 00158 /* Reclaim garbage, defined as all alloca()ed storage that 00159 was allocated from deeper in the stack than currently. */ 00160 { 00161 register header *hp; /* traverses linked list */ 00162 00163 for (hp = last_alloca_header; hp != NULL;) 00164 if (STACK_DIR > 0 && hp->h.deep > depth 00165 || STACK_DIR < 0 && hp->h.deep < depth) 00166 { 00167 register header *np = hp->h.next; 00168 00169 xfree ((pointer) hp); /* collect garbage */ 00170 00171 hp = np; /* -> next header */ 00172 } 00173 else 00174 break; /* rest are not deeper */ 00175 00176 last_alloca_header = hp; /* -> last valid storage */ 00177 } 00178 00179 if (size == 0) 00180 return NULL; /* no allocation required */ 00181 00182 /* Allocate combined header + user data storage. */ 00183 00184 { 00185 register pointer new = xmalloc (sizeof (header) + size); 00186 /* address of header */ 00187 00188 ((header *)new)->h.next = last_alloca_header; 00189 ((header *)new)->h.deep = depth; 00190 00191 last_alloca_header = (header *)new; 00192 00193 /* User storage begins just after header. */ 00194 00195 return (pointer)((char *)new + sizeof(header)); 00196 } 00197 } 00198 00199 #endif 00200