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