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