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 HAVE_CONFIG_H
34 #include "config.h"
35 #endif
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
44 you
45 lose
46 -- must know STACK_DIRECTION at compile-time
47 #endif /* STACK_DIRECTION undefined */
48 #endif /* static */
49 #endif /* emacs */
50
51 #ifndef alloca /* If compiling with GCC, this file's not needed. */
52
53 #ifdef __STDC__
54 typedef void *pointer; /* generic pointer type */
55 #else
56 typedef char *pointer; /* generic pointer type */
57 #endif
58
59 #define NULL 0 /* null pointer constant */
60
61 extern void free();
62 extern pointer xmalloc();
63
64 /*
65 Define STACK_DIRECTION if you know the direction of stack
66 growth for your system; otherwise it will be automatically
67 deduced at run-time.
68
69 STACK_DIRECTION > 0 => grows toward higher addresses
70 STACK_DIRECTION < 0 => grows toward lower addresses
71 STACK_DIRECTION = 0 => direction of growth unknown
72 */
73
74 #ifndef STACK_DIRECTION
75 #define STACK_DIRECTION 0 /* direction unknown */
76 #endif
77
78 #if STACK_DIRECTION != 0
79
80 #define STACK_DIR STACK_DIRECTION /* known at compile-time */
81
82 #else /* STACK_DIRECTION == 0; need run-time code */
83
84 static int stack_dir; /* 1 or -1 once known */
85 #define STACK_DIR stack_dir
86
87 static void
find_stack_direction()88 find_stack_direction (/* void */)
89 {
90 static char *addr = NULL; /* address of first
91 `dummy', once known */
92 auto char dummy; /* to get stack address */
93
94 if (addr == NULL)
95 { /* initial entry */
96 addr = &dummy;
97
98 find_stack_direction (); /* recurse once */
99 }
100 else /* second entry */
101 if (&dummy > addr)
102 stack_dir = 1; /* stack grew upward */
103 else
104 stack_dir = -1; /* stack grew downward */
105 }
106
107 #endif /* STACK_DIRECTION == 0 */
108
109 /*
110 An "alloca header" is used to:
111 (a) chain together all alloca()ed blocks;
112 (b) keep track of stack depth.
113
114 It is very important that sizeof(header) agree with malloc()
115 alignment chunk size. The following default should work okay.
116 */
117
118 #ifndef ALIGN_SIZE
119 #define ALIGN_SIZE sizeof(double)
120 #endif
121
122 typedef union hdr
123 {
124 char align[ALIGN_SIZE]; /* to force sizeof(header) */
125 struct
126 {
127 union hdr *next; /* for chaining headers */
128 char *deep; /* for stack depth measure */
129 } h;
130 } header;
131
132 /*
133 alloca( size ) returns a pointer to at least `size' bytes of
134 storage which will be automatically reclaimed upon exit from
135 the procedure that called alloca(). Originally, this space
136 was supposed to be taken from the current stack frame of the
137 caller, but that method cannot be made to work for some
138 implementations of C, for example under Gould's UTX/32.
139 */
140
141 static header *last_alloca_header = NULL; /* -> last alloca header */
142
143 pointer
alloca(size)144 alloca (size) /* returns pointer to storage */
145 unsigned size; /* # bytes to allocate */
146 {
147 auto char probe; /* probes stack depth: */
148 register char *depth = &probe;
149
150 #if STACK_DIRECTION == 0
151 if (STACK_DIR == 0) /* unknown growth direction */
152 find_stack_direction ();
153 #endif
154
155 /* Reclaim garbage, defined as all alloca()ed storage that
156 was allocated from deeper in the stack than currently. */
157
158 {
159 register header *hp; /* traverses linked list */
160
161 for (hp = last_alloca_header; hp != NULL;)
162 if ((STACK_DIR > 0 && hp->h.deep > depth)
163 || (STACK_DIR < 0 && hp->h.deep < depth))
164 {
165 register header *np = hp->h.next;
166
167 free ((pointer) hp); /* collect garbage */
168
169 hp = np; /* -> next header */
170 }
171 else
172 break; /* rest are not deeper */
173
174 last_alloca_header = hp; /* -> last valid storage */
175 }
176
177 if (size == 0)
178 return NULL; /* no allocation required */
179
180 /* Allocate combined header + user data storage. */
181
182 {
183 register pointer new = xmalloc (sizeof (header) + size);
184 /* address of header */
185
186 ((header *)new)->h.next = last_alloca_header;
187 ((header *)new)->h.deep = depth;
188
189 last_alloca_header = (header *)new;
190
191 /* User storage begins just after header. */
192
193 return (pointer)((char *)new + sizeof(header));
194 }
195 }
196
197 #endif /* no alloca */
198