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