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