xref: /dragonfly/usr.bin/dc/stack.c (revision cfd1aba3) 
1 /*
2  * $OpenBSD: stack.c,v 1.11 2009/10/27 23:59:37 deraadt 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
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
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
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 *
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
99 stack_size(const struct stack *stack)
100 {
101 	return stack->sp + 1;
102 }
103 
104 void
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, &copy));
116 }
117 
118 void
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
133 stack_grow(struct stack *stack)
134 {
135 	size_t new_size, i;
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 		for (i = stack->size; i < new_size; i++)
142 			stack->stack[i].array = NULL;
143 		stack->size = new_size;
144 	}
145 }
146 
147 void
148 stack_pushnumber(struct stack *stack, struct number *b)
149 {
150 	stack_grow(stack);
151 	stack->stack[stack->sp].type = BCODE_NUMBER;
152 	stack->stack[stack->sp].u.num = b;
153 }
154 
155 void
156 stack_pushstring(struct stack *stack, char *string)
157 {
158 	stack_grow(stack);
159 	stack->stack[stack->sp].type = BCODE_STRING;
160 	stack->stack[stack->sp].u.string = string;
161 }
162 
163 void
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 *
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
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 *
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 *
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 *
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
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
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 *
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
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 *
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
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
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 *
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
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 *
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