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
28static __inline bool	 stack_empty(const struct stack *);
29static void		 stack_grow(struct stack *);
30static struct array	*array_new(void);
31static __inline void	 array_free(struct array *);
32static struct array	*array_dup(const struct array *);
33static __inline void	 array_grow(struct array *, size_t);
34static __inline void	 array_assign(struct array *, size_t, const struct value *);
35static __inline struct value	*array_retrieve(const struct array *, size_t);
36
37void
38stack_init(struct stack *stack)
39{
40
41	stack->size = 0;
42	stack->sp = -1;
43	stack->stack = NULL;
44}
45
46static __inline bool
47stack_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 */
57void
58stack_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 */
78struct value *
79stack_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
102size_t
103stack_size(const struct stack *stack)
104{
105
106	return (stack->sp + 1);
107}
108
109void
110stack_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
123void
124stack_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
137static void
138stack_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
152void
153stack_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
161void
162stack_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
170void
171stack_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
190struct value *
191stack_tos(const struct stack *stack)
192{
193
194	if (stack->sp == -1)
195		return (NULL);
196	return &stack->stack[stack->sp];
197}
198
199void
200stack_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
213struct value *
214stack_pop(struct stack *stack)
215{
216
217	if (stack_empty(stack))
218		return (NULL);
219	return &stack->stack[stack->sp--];
220}
221
222struct number *
223stack_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
239char *
240stack_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
256void
257stack_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
267void
268stack_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
279static struct array *
280array_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
290static __inline void
291array_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
303static struct array *
304array_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
318static __inline void
319array_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
331static __inline void
332array_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
341static __inline struct value *
342array_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
350void
351frame_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
368struct value *
369frame_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