1/*	$OpenBSD: stack.c,v 1.13 2014/12/01 13:13:00 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#include <err.h>
21#include <stdlib.h>
22#include <string.h>
23
24#include "extern.h"
25
26static __inline bool	 stack_empty(const struct stack *);
27static void		 stack_grow(struct stack *);
28static struct array	*array_new(void);
29static __inline void	 array_free(struct array *);
30static struct array	*array_dup(const struct array *);
31static __inline void	 array_grow(struct array *, size_t);
32static __inline void	 array_assign(struct array *, size_t, const struct value *);
33static __inline struct value	*array_retrieve(const struct array *, size_t);
34
35void
36stack_init(struct stack *stack)
37{
38
39	stack->size = 0;
40	stack->sp = -1;
41	stack->stack = NULL;
42}
43
44static __inline bool
45stack_empty(const struct stack *stack)
46{
47	bool empty = stack->sp == -1;
48
49	if (empty)
50		warnx("stack empty");
51	return empty;
52}
53
54/* Clear number or string, but leave value itself */
55void
56stack_free_value(struct value *v)
57{
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	array_free(v->array);
70	v->array = NULL;
71}
72
73/* Copy number or string content into already allocated target */
74struct value *
75stack_dup_value(const struct value *a, struct value *copy)
76{
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
98size_t
99stack_size(const struct stack *stack)
100{
101
102	return (stack->sp + 1);
103}
104
105void
106stack_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
119void
120stack_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
133static void
134stack_grow(struct stack *stack)
135{
136	size_t new_size;
137
138	if (++stack->sp == stack->size) {
139		new_size = stack->size * 2 + 1;
140		stack->stack = breallocarray(stack->stack,
141		    new_size, sizeof(*stack->stack));
142		stack->size = new_size;
143	}
144}
145
146void
147stack_pushnumber(struct stack *stack, struct number *b)
148{
149
150	stack_grow(stack);
151	stack->stack[stack->sp].type = BCODE_NUMBER;
152	stack->stack[stack->sp].u.num = b;
153	stack->stack[stack->sp].array = NULL;
154}
155
156void
157stack_pushstring(struct stack *stack, char *string)
158{
159
160	stack_grow(stack);
161	stack->stack[stack->sp].type = BCODE_STRING;
162	stack->stack[stack->sp].u.string = string;
163	stack->stack[stack->sp].array = NULL;
164}
165
166void
167stack_push(struct stack *stack, struct value *v)
168{
169
170	switch (v->type) {
171	case BCODE_NONE:
172		stack_grow(stack);
173		stack->stack[stack->sp].type = BCODE_NONE;
174		break;
175	case BCODE_NUMBER:
176		stack_pushnumber(stack, v->u.num);
177		break;
178	case BCODE_STRING:
179		stack_pushstring(stack, v->u.string);
180		break;
181	}
182	stack->stack[stack->sp].array = v->array == NULL ?
183	    NULL : array_dup(v->array);
184}
185
186struct value *
187stack_tos(const struct stack *stack)
188{
189
190	if (stack->sp == -1)
191		return (NULL);
192	return &stack->stack[stack->sp];
193}
194
195void
196stack_set_tos(struct stack *stack, struct value *v)
197{
198
199	if (stack->sp == -1)
200		stack_push(stack, v);
201	else {
202		stack_free_value(&stack->stack[stack->sp]);
203		stack->stack[stack->sp] = *v;
204		stack->stack[stack->sp].array = v->array == NULL ?
205		    NULL : array_dup(v->array);
206	}
207}
208
209struct value *
210stack_pop(struct stack *stack)
211{
212
213	if (stack_empty(stack))
214		return (NULL);
215	return &stack->stack[stack->sp--];
216}
217
218struct number *
219stack_popnumber(struct stack *stack)
220{
221
222	if (stack_empty(stack))
223		return (NULL);
224	array_free(stack->stack[stack->sp].array);
225	stack->stack[stack->sp].array = NULL;
226	if (stack->stack[stack->sp].type != BCODE_NUMBER) {
227		warnx("not a number"); /* XXX remove */
228		return (NULL);
229	}
230	return stack->stack[stack->sp--].u.num;
231}
232
233char *
234stack_popstring(struct stack *stack)
235{
236
237	if (stack_empty(stack))
238		return (NULL);
239	array_free(stack->stack[stack->sp].array);
240	stack->stack[stack->sp].array = NULL;
241	if (stack->stack[stack->sp].type != BCODE_STRING) {
242		warnx("not a string"); /* XXX remove */
243		return (NULL);
244	}
245	return stack->stack[stack->sp--].u.string;
246}
247
248void
249stack_clear(struct stack *stack)
250{
251
252	while (stack->sp >= 0)
253		stack_free_value(&stack->stack[stack->sp--]);
254	free(stack->stack);
255	stack_init(stack);
256}
257
258void
259stack_print(FILE *f, const struct stack *stack, const char *prefix, u_int base)
260{
261	ssize_t i;
262
263	for (i = stack->sp; i >= 0; i--) {
264		print_value(f, &stack->stack[i], prefix, base);
265		putc('\n', f);
266	}
267}
268
269
270static struct array *
271array_new(void)
272{
273	struct array *a;
274
275	a = bmalloc(sizeof(*a));
276	a->data = NULL;
277	a->size = 0;
278	return a;
279}
280
281static __inline void
282array_free(struct array *a)
283{
284	size_t i;
285
286	if (a == NULL)
287		return;
288	for (i = 0; i < a->size; i++)
289		stack_free_value(&a->data[i]);
290	free(a->data);
291	free(a);
292}
293
294static struct array *
295array_dup(const struct array *a)
296{
297	struct array *n;
298	size_t i;
299
300	if (a == NULL)
301		return (NULL);
302	n = array_new();
303	array_grow(n, a->size);
304	for (i = 0; i < a->size; i++)
305		stack_dup_value(&a->data[i], &n->data[i]);
306	return (n);
307}
308
309static __inline void
310array_grow(struct array *array, size_t newsize)
311{
312	size_t i;
313
314	array->data = breallocarray(array->data, newsize, sizeof(*array->data));
315	for (i = array->size; i < newsize; i++) {
316		array->data[i].type = BCODE_NONE;
317		array->data[i].array = NULL;
318	}
319	array->size = newsize;
320}
321
322static __inline void
323array_assign(struct array *array, size_t i, const struct value *v)
324{
325
326	if (i >= array->size)
327		array_grow(array, i + 1);
328	stack_free_value(&array->data[i]);
329	array->data[i] = *v;
330}
331
332static __inline struct value *
333array_retrieve(const struct array *array, size_t i)
334{
335
336	if (i >= array->size)
337		return (NULL);
338	return &array->data[i];
339}
340
341void
342frame_assign(struct stack *stack, size_t i, const struct value *v)
343{
344	struct array *a;
345	struct value n;
346
347	if (stack->sp == -1) {
348		n.type = BCODE_NONE;
349		n.array = NULL;
350		stack_push(stack, &n);
351	}
352
353	a = stack->stack[stack->sp].array;
354	if (a == NULL)
355		a = stack->stack[stack->sp].array = array_new();
356	array_assign(a, i, v);
357}
358
359struct value *
360frame_retrieve(const struct stack *stack, size_t i)
361{
362	struct array *a;
363
364	if (stack->sp == -1)
365		return (NULL);
366	a = stack->stack[stack->sp].array;
367	if (a == NULL)
368		a = stack->stack[stack->sp].array = array_new();
369	return array_retrieve(a, i);
370}
371