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