1 /* $OpenBSD: stack.c,v 1.11 2009/10/27 23:59:37 deraadt Exp $ */
2
3 /*
4 * Copyright (c) 2003, Otto Moerbeek <otto@drijf.net>
5 *
6 * Permission to use, copy, modify, and distribute this software for any
7 * purpose with or without fee is hereby granted, provided that the above
8 * copyright notice and this permission notice appear in all copies.
9 *
10 * THE SOFTWARE IS PROVIDED "AS IS" AND THE AUTHOR DISCLAIMS ALL WARRANTIES
11 * WITH REGARD TO THIS SOFTWARE INCLUDING ALL IMPLIED WARRANTIES OF
12 * MERCHANTABILITY AND FITNESS. IN NO EVENT SHALL THE AUTHOR BE LIABLE FOR
13 * ANY SPECIAL, DIRECT, INDIRECT, OR CONSEQUENTIAL DAMAGES OR ANY DAMAGES
14 * WHATSOEVER RESULTING FROM LOSS OF USE, DATA OR PROFITS, WHETHER IN AN
15 * ACTION OF CONTRACT, NEGLIGENCE OR OTHER TORTIOUS ACTION, ARISING OUT OF
16 * OR IN CONNECTION WITH THE USE OR PERFORMANCE OF THIS SOFTWARE.
17 */
18
19 #include <sys/cdefs.h>
20 __FBSDID("$FreeBSD$");
21
22 #include <err.h>
23 #include <stdlib.h>
24 #include <string.h>
25
26 #include "extern.h"
27
28 static __inline bool stack_empty(const struct stack *);
29 static void stack_grow(struct stack *);
30 static struct array *array_new(void);
31 static __inline void array_free(struct array *);
32 static struct array *array_dup(const struct array *);
33 static __inline void array_grow(struct array *, size_t);
34 static __inline void array_assign(struct array *, size_t, const struct value *);
35 static __inline struct value *array_retrieve(const struct array *, size_t);
36
37 void
stack_init(struct stack * stack)38 stack_init(struct stack *stack)
39 {
40
41 stack->size = 0;
42 stack->sp = -1;
43 stack->stack = NULL;
44 }
45
46 static __inline bool
stack_empty(const struct stack * stack)47 stack_empty(const struct stack *stack)
48 {
49 bool empty = stack->sp == -1;
50
51 if (empty)
52 warnx("stack empty");
53 return empty;
54 }
55
56 /* Clear number or string, but leave value itself */
57 void
stack_free_value(struct value * v)58 stack_free_value(struct value *v)
59 {
60
61 switch (v->type) {
62 case BCODE_NONE:
63 break;
64 case BCODE_NUMBER:
65 free_number(v->u.num);
66 break;
67 case BCODE_STRING:
68 free(v->u.string);
69 break;
70 }
71 if (v->array != NULL) {
72 array_free(v->array);
73 v->array = NULL;
74 }
75 }
76
77 /* Copy number or string content into already allocated target */
78 struct value *
stack_dup_value(const struct value * a,struct value * copy)79 stack_dup_value(const struct value *a, struct value *copy)
80 {
81
82 copy->type = a->type;
83
84 switch (a->type) {
85 case BCODE_NONE:
86 break;
87 case BCODE_NUMBER:
88 copy->u.num = dup_number(a->u.num);
89 break;
90 case BCODE_STRING:
91 copy->u.string = strdup(a->u.string);
92 if (copy->u.string == NULL)
93 err(1, NULL);
94 break;
95 }
96
97 copy->array = a->array == NULL ? NULL : array_dup(a->array);
98
99 return (copy);
100 }
101
102 size_t
stack_size(const struct stack * stack)103 stack_size(const struct stack *stack)
104 {
105
106 return (stack->sp + 1);
107 }
108
109 void
stack_dup(struct stack * stack)110 stack_dup(struct stack *stack)
111 {
112 struct value *value;
113 struct value copy;
114
115 value = stack_tos(stack);
116 if (value == NULL) {
117 warnx("stack empty");
118 return;
119 }
120 stack_push(stack, stack_dup_value(value, ©));
121 }
122
123 void
stack_swap(struct stack * stack)124 stack_swap(struct stack *stack)
125 {
126 struct value copy;
127
128 if (stack->sp < 1) {
129 warnx("stack empty");
130 return;
131 }
132 copy = stack->stack[stack->sp];
133 stack->stack[stack->sp] = stack->stack[stack->sp-1];
134 stack->stack[stack->sp-1] = copy;
135 }
136
137 static void
stack_grow(struct stack * stack)138 stack_grow(struct stack *stack)
139 {
140 size_t new_size;
141
142 if (++stack->sp == stack->size) {
143 new_size = stack->size * 2 + 1;
144 stack->stack = brealloc(stack->stack,
145 new_size * sizeof(*stack->stack));
146 stack->size = new_size;
147 }
148 }
149
150 void
stack_pushnumber(struct stack * stack,struct number * b)151 stack_pushnumber(struct stack *stack, struct number *b)
152 {
153
154 stack_grow(stack);
155 stack->stack[stack->sp].type = BCODE_NUMBER;
156 stack->stack[stack->sp].u.num = b;
157 stack->stack[stack->sp].array = NULL;
158 }
159
160 void
stack_pushstring(struct stack * stack,char * string)161 stack_pushstring(struct stack *stack, char *string)
162 {
163
164 stack_grow(stack);
165 stack->stack[stack->sp].type = BCODE_STRING;
166 stack->stack[stack->sp].u.string = string;
167 stack->stack[stack->sp].array = NULL;
168 }
169
170 void
stack_push(struct stack * stack,struct value * v)171 stack_push(struct stack *stack, struct value *v)
172 {
173
174 switch (v->type) {
175 case BCODE_NONE:
176 stack_grow(stack);
177 stack->stack[stack->sp].type = BCODE_NONE;
178 break;
179 case BCODE_NUMBER:
180 stack_pushnumber(stack, v->u.num);
181 break;
182 case BCODE_STRING:
183 stack_pushstring(stack, v->u.string);
184 break;
185 }
186 stack->stack[stack->sp].array = v->array == NULL ?
187 NULL : array_dup(v->array);
188 }
189
190 struct value *
stack_tos(const struct stack * stack)191 stack_tos(const struct stack *stack)
192 {
193
194 if (stack->sp == -1)
195 return (NULL);
196 return &stack->stack[stack->sp];
197 }
198
199 void
stack_set_tos(struct stack * stack,struct value * v)200 stack_set_tos(struct stack *stack, struct value *v)
201 {
202
203 if (stack->sp == -1)
204 stack_push(stack, v);
205 else {
206 stack_free_value(&stack->stack[stack->sp]);
207 stack->stack[stack->sp] = *v;
208 stack->stack[stack->sp].array = v->array == NULL ?
209 NULL : array_dup(v->array);
210 }
211 }
212
213 struct value *
stack_pop(struct stack * stack)214 stack_pop(struct stack *stack)
215 {
216
217 if (stack_empty(stack))
218 return (NULL);
219 return &stack->stack[stack->sp--];
220 }
221
222 struct number *
stack_popnumber(struct stack * stack)223 stack_popnumber(struct stack *stack)
224 {
225
226 if (stack_empty(stack))
227 return (NULL);
228 if (stack->stack[stack->sp].array != NULL) {
229 array_free(stack->stack[stack->sp].array);
230 stack->stack[stack->sp].array = NULL;
231 }
232 if (stack->stack[stack->sp].type != BCODE_NUMBER) {
233 warnx("not a number"); /* XXX remove */
234 return (NULL);
235 }
236 return stack->stack[stack->sp--].u.num;
237 }
238
239 char *
stack_popstring(struct stack * stack)240 stack_popstring(struct stack *stack)
241 {
242
243 if (stack_empty(stack))
244 return (NULL);
245 if (stack->stack[stack->sp].array != NULL) {
246 array_free(stack->stack[stack->sp].array);
247 stack->stack[stack->sp].array = NULL;
248 }
249 if (stack->stack[stack->sp].type != BCODE_STRING) {
250 warnx("not a string"); /* XXX remove */
251 return (NULL);
252 }
253 return stack->stack[stack->sp--].u.string;
254 }
255
256 void
stack_clear(struct stack * stack)257 stack_clear(struct stack *stack)
258 {
259
260 while (stack->sp >= 0) {
261 stack_free_value(&stack->stack[stack->sp--]);
262 }
263 free(stack->stack);
264 stack_init(stack);
265 }
266
267 void
stack_print(FILE * f,const struct stack * stack,const char * prefix,u_int base)268 stack_print(FILE *f, const struct stack *stack, const char *prefix, u_int base)
269 {
270 ssize_t i;
271
272 for (i = stack->sp; i >= 0; i--) {
273 print_value(f, &stack->stack[i], prefix, base);
274 putc('\n', f);
275 }
276 }
277
278
279 static struct array *
array_new(void)280 array_new(void)
281 {
282 struct array *a;
283
284 a = bmalloc(sizeof(*a));
285 a->data = NULL;
286 a->size = 0;
287 return a;
288 }
289
290 static __inline void
array_free(struct array * a)291 array_free(struct array *a)
292 {
293 size_t i;
294
295 if (a == NULL)
296 return;
297 for (i = 0; i < a->size; i++)
298 stack_free_value(&a->data[i]);
299 free(a->data);
300 free(a);
301 }
302
303 static struct array *
array_dup(const struct array * a)304 array_dup(const struct array *a)
305 {
306 struct array *n;
307 size_t i;
308
309 if (a == NULL)
310 return (NULL);
311 n = array_new();
312 array_grow(n, a->size);
313 for (i = 0; i < a->size; i++)
314 stack_dup_value(&a->data[i], &n->data[i]);
315 return (n);
316 }
317
318 static __inline void
array_grow(struct array * array,size_t newsize)319 array_grow(struct array *array, size_t newsize)
320 {
321 size_t i;
322
323 array->data = brealloc(array->data, newsize * sizeof(*array->data));
324 for (i = array->size; i < newsize; i++) {
325 array->data[i].type = BCODE_NONE;
326 array->data[i].array = NULL;
327 }
328 array->size = newsize;
329 }
330
331 static __inline void
array_assign(struct array * array,size_t i,const struct value * v)332 array_assign(struct array *array, size_t i, const struct value *v)
333 {
334
335 if (i >= array->size)
336 array_grow(array, i + 1);
337 stack_free_value(&array->data[i]);
338 array->data[i] = *v;
339 }
340
341 static __inline struct value *
array_retrieve(const struct array * array,size_t i)342 array_retrieve(const struct array *array, size_t i)
343 {
344
345 if (i >= array->size)
346 return (NULL);
347 return &array->data[i];
348 }
349
350 void
frame_assign(struct stack * stack,size_t i,const struct value * v)351 frame_assign(struct stack *stack, size_t i, const struct value *v)
352 {
353 struct array *a;
354 struct value n;
355
356 if (stack->sp == -1) {
357 n.type = BCODE_NONE;
358 n.array = NULL;
359 stack_push(stack, &n);
360 }
361
362 a = stack->stack[stack->sp].array;
363 if (a == NULL)
364 a = stack->stack[stack->sp].array = array_new();
365 array_assign(a, i, v);
366 }
367
368 struct value *
frame_retrieve(const struct stack * stack,size_t i)369 frame_retrieve(const struct stack *stack, size_t i)
370 {
371 struct array *a;
372
373 if (stack->sp == -1)
374 return (NULL);
375 a = stack->stack[stack->sp].array;
376 if (a == NULL)
377 a = stack->stack[stack->sp].array = array_new();
378 return array_retrieve(a, i);
379 }
380