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