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