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