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