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
find_stack_direction()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
alloca(size)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