1 /* $OpenBSD: stack.c,v 1.13 2014/12/01 13:13:00 deraadt Exp $ */
2
3 /*
4 * Copyright (c) 2003, Otto Moerbeek <[email protected]>
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 array_free(v->array);
72 v->array = NULL;
73 }
74
75 /* Copy number or string content into already allocated target */
76 struct value *
stack_dup_value(const struct value * a,struct value * copy)77 stack_dup_value(const struct value *a, struct value *copy)
78 {
79
80 copy->type = a->type;
81
82 switch (a->type) {
83 case BCODE_NONE:
84 break;
85 case BCODE_NUMBER:
86 copy->u.num = dup_number(a->u.num);
87 break;
88 case BCODE_STRING:
89 copy->u.string = strdup(a->u.string);
90 if (copy->u.string == NULL)
91 err(1, NULL);
92 break;
93 }
94
95 copy->array = a->array == NULL ? NULL : array_dup(a->array);
96
97 return (copy);
98 }
99
100 size_t
stack_size(const struct stack * stack)101 stack_size(const struct stack *stack)
102 {
103
104 return (stack->sp + 1);
105 }
106
107 void
stack_dup(struct stack * stack)108 stack_dup(struct stack *stack)
109 {
110 struct value *value;
111 struct value copy;
112
113 value = stack_tos(stack);
114 if (value == NULL) {
115 warnx("stack empty");
116 return;
117 }
118 stack_push(stack, stack_dup_value(value, ©));
119 }
120
121 void
stack_swap(struct stack * stack)122 stack_swap(struct stack *stack)
123 {
124 struct value copy;
125
126 if (stack->sp < 1) {
127 warnx("stack empty");
128 return;
129 }
130 copy = stack->stack[stack->sp];
131 stack->stack[stack->sp] = stack->stack[stack->sp-1];
132 stack->stack[stack->sp-1] = copy;
133 }
134
135 static void
stack_grow(struct stack * stack)136 stack_grow(struct stack *stack)
137 {
138 size_t new_size;
139
140 if (++stack->sp == stack->size) {
141 new_size = stack->size * 2 + 1;
142 stack->stack = breallocarray(stack->stack,
143 new_size, sizeof(*stack->stack));
144 stack->size = new_size;
145 }
146 }
147
148 void
stack_pushnumber(struct stack * stack,struct number * b)149 stack_pushnumber(struct stack *stack, struct number *b)
150 {
151
152 stack_grow(stack);
153 stack->stack[stack->sp].type = BCODE_NUMBER;
154 stack->stack[stack->sp].u.num = b;
155 stack->stack[stack->sp].array = NULL;
156 }
157
158 void
stack_pushstring(struct stack * stack,char * string)159 stack_pushstring(struct stack *stack, char *string)
160 {
161
162 stack_grow(stack);
163 stack->stack[stack->sp].type = BCODE_STRING;
164 stack->stack[stack->sp].u.string = string;
165 stack->stack[stack->sp].array = NULL;
166 }
167
168 void
stack_push(struct stack * stack,struct value * v)169 stack_push(struct stack *stack, struct value *v)
170 {
171
172 switch (v->type) {
173 case BCODE_NONE:
174 stack_grow(stack);
175 stack->stack[stack->sp].type = BCODE_NONE;
176 break;
177 case BCODE_NUMBER:
178 stack_pushnumber(stack, v->u.num);
179 break;
180 case BCODE_STRING:
181 stack_pushstring(stack, v->u.string);
182 break;
183 }
184 stack->stack[stack->sp].array = v->array == NULL ?
185 NULL : array_dup(v->array);
186 }
187
188 struct value *
stack_tos(const struct stack * stack)189 stack_tos(const struct stack *stack)
190 {
191
192 if (stack->sp == -1)
193 return (NULL);
194 return &stack->stack[stack->sp];
195 }
196
197 void
stack_set_tos(struct stack * stack,struct value * v)198 stack_set_tos(struct stack *stack, struct value *v)
199 {
200
201 if (stack->sp == -1)
202 stack_push(stack, v);
203 else {
204 stack_free_value(&stack->stack[stack->sp]);
205 stack->stack[stack->sp] = *v;
206 stack->stack[stack->sp].array = v->array == NULL ?
207 NULL : array_dup(v->array);
208 }
209 }
210
211 struct value *
stack_pop(struct stack * stack)212 stack_pop(struct stack *stack)
213 {
214
215 if (stack_empty(stack))
216 return (NULL);
217 return &stack->stack[stack->sp--];
218 }
219
220 struct number *
stack_popnumber(struct stack * stack)221 stack_popnumber(struct stack *stack)
222 {
223
224 if (stack_empty(stack))
225 return (NULL);
226 array_free(stack->stack[stack->sp].array);
227 stack->stack[stack->sp].array = NULL;
228 if (stack->stack[stack->sp].type != BCODE_NUMBER) {
229 warnx("not a number"); /* XXX remove */
230 return (NULL);
231 }
232 return stack->stack[stack->sp--].u.num;
233 }
234
235 char *
stack_popstring(struct stack * stack)236 stack_popstring(struct stack *stack)
237 {
238
239 if (stack_empty(stack))
240 return (NULL);
241 array_free(stack->stack[stack->sp].array);
242 stack->stack[stack->sp].array = NULL;
243 if (stack->stack[stack->sp].type != BCODE_STRING) {
244 warnx("not a string"); /* XXX remove */
245 return (NULL);
246 }
247 return stack->stack[stack->sp--].u.string;
248 }
249
250 void
stack_clear(struct stack * stack)251 stack_clear(struct stack *stack)
252 {
253
254 while (stack->sp >= 0)
255 stack_free_value(&stack->stack[stack->sp--]);
256 free(stack->stack);
257 stack_init(stack);
258 }
259
260 void
stack_print(FILE * f,const struct stack * stack,const char * prefix,u_int base)261 stack_print(FILE *f, const struct stack *stack, const char *prefix, u_int base)
262 {
263 ssize_t i;
264
265 for (i = stack->sp; i >= 0; i--) {
266 print_value(f, &stack->stack[i], prefix, base);
267 putc('\n', f);
268 }
269 }
270
271
272 static struct array *
array_new(void)273 array_new(void)
274 {
275 struct array *a;
276
277 a = bmalloc(sizeof(*a));
278 a->data = NULL;
279 a->size = 0;
280 return a;
281 }
282
283 static __inline void
array_free(struct array * a)284 array_free(struct array *a)
285 {
286 size_t i;
287
288 if (a == NULL)
289 return;
290 for (i = 0; i < a->size; i++)
291 stack_free_value(&a->data[i]);
292 free(a->data);
293 free(a);
294 }
295
296 static struct array *
array_dup(const struct array * a)297 array_dup(const struct array *a)
298 {
299 struct array *n;
300 size_t i;
301
302 if (a == NULL)
303 return (NULL);
304 n = array_new();
305 array_grow(n, a->size);
306 for (i = 0; i < a->size; i++)
307 stack_dup_value(&a->data[i], &n->data[i]);
308 return (n);
309 }
310
311 static __inline void
array_grow(struct array * array,size_t newsize)312 array_grow(struct array *array, size_t newsize)
313 {
314 size_t i;
315
316 array->data = breallocarray(array->data, newsize, sizeof(*array->data));
317 for (i = array->size; i < newsize; i++) {
318 array->data[i].type = BCODE_NONE;
319 array->data[i].array = NULL;
320 }
321 array->size = newsize;
322 }
323
324 static __inline void
array_assign(struct array * array,size_t i,const struct value * v)325 array_assign(struct array *array, size_t i, const struct value *v)
326 {
327
328 if (i >= array->size)
329 array_grow(array, i + 1);
330 stack_free_value(&array->data[i]);
331 array->data[i] = *v;
332 }
333
334 static __inline struct value *
array_retrieve(const struct array * array,size_t i)335 array_retrieve(const struct array *array, size_t i)
336 {
337
338 if (i >= array->size)
339 return (NULL);
340 return &array->data[i];
341 }
342
343 void
frame_assign(struct stack * stack,size_t i,const struct value * v)344 frame_assign(struct stack *stack, size_t i, const struct value *v)
345 {
346 struct array *a;
347 struct value n;
348
349 if (stack->sp == -1) {
350 n.type = BCODE_NONE;
351 n.array = NULL;
352 stack_push(stack, &n);
353 }
354
355 a = stack->stack[stack->sp].array;
356 if (a == NULL)
357 a = stack->stack[stack->sp].array = array_new();
358 array_assign(a, i, v);
359 }
360
361 struct value *
frame_retrieve(const struct stack * stack,size_t i)362 frame_retrieve(const struct stack *stack, size_t i)
363 {
364 struct array *a;
365
366 if (stack->sp == -1)
367 return (NULL);
368 a = stack->stack[stack->sp].array;
369 if (a == NULL)
370 a = stack->stack[stack->sp].array = array_new();
371 return array_retrieve(a, i);
372 }
373