1/*	$NetBSD: stack.c,v 1.2 2017/04/10 16:37:48 christos Exp $	*/
2/*	$OpenBSD: stack.c,v 1.14 2016/03/27 15:55:13 otto Exp $	*/
3
4/*
5 * Copyright (c) 2003, Otto Moerbeek <otto@drijf.net>
6 *
7 * Permission to use, copy, modify, and distribute this software for any
8 * purpose with or without fee is hereby granted, provided that the above
9 * copyright notice and this permission notice appear in all copies.
10 *
11 * THE SOFTWARE IS PROVIDED "AS IS" AND THE AUTHOR DISCLAIMS ALL WARRANTIES
12 * WITH REGARD TO THIS SOFTWARE INCLUDING ALL IMPLIED WARRANTIES OF
13 * MERCHANTABILITY AND FITNESS. IN NO EVENT SHALL THE AUTHOR BE LIABLE FOR
14 * ANY SPECIAL, DIRECT, INDIRECT, OR CONSEQUENTIAL DAMAGES OR ANY DAMAGES
15 * WHATSOEVER RESULTING FROM LOSS OF USE, DATA OR PROFITS, WHETHER IN AN
16 * ACTION OF CONTRACT, NEGLIGENCE OR OTHER TORTIOUS ACTION, ARISING OUT OF
17 * OR IN CONNECTION WITH THE USE OR PERFORMANCE OF THIS SOFTWARE.
18 */
19#include <sys/cdefs.h>
20__RCSID("$NetBSD: stack.c,v 1.2 2017/04/10 16:37:48 christos Exp $");
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	stack->size = 0;
41	stack->sp = -1;
42	stack->stack = NULL;
43}
44
45static __inline bool
46stack_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 */
55void
56stack_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	array_free(v->array);
69	v->array = NULL;
70}
71
72/* Copy number or string content into already allocated target */
73struct value *
74stack_dup_value(const struct value *a, struct value *copy)
75{
76	copy->type = a->type;
77
78	switch (a->type) {
79	case BCODE_NONE:
80		break;
81	case BCODE_NUMBER:
82		copy->u.num = dup_number(a->u.num);
83		break;
84	case BCODE_STRING:
85		copy->u.string = strdup(a->u.string);
86		if (copy->u.string == NULL)
87			err(1, NULL);
88		break;
89	}
90
91	copy->array = a->array == NULL ? NULL : array_dup(a->array);
92
93	return copy;
94}
95
96size_t
97stack_size(const struct stack *stack)
98{
99	return (size_t)(stack->sp + 1);
100}
101
102void
103stack_dup(struct stack *stack)
104{
105	struct value	*value;
106	struct value	copy;
107
108	value = stack_tos(stack);
109	if (value == NULL) {
110		warnx("stack empty");
111		return;
112	}
113	stack_push(stack, stack_dup_value(value, &copy));
114}
115
116void
117stack_swap(struct stack *stack)
118{
119	struct value	copy;
120
121	if (stack->sp < 1) {
122		warnx("stack empty");
123		return;
124	}
125	copy = stack->stack[stack->sp];
126	stack->stack[stack->sp] = stack->stack[stack->sp-1];
127	stack->stack[stack->sp-1] = copy;
128}
129
130static void
131stack_grow(struct stack *stack)
132{
133	size_t new_size;
134
135	if ((size_t)++stack->sp == stack->size) {
136		new_size = stack->size * 2 + 1;
137		stack->stack = breallocarray(stack->stack,
138		    new_size, sizeof(*stack->stack));
139		stack->size = new_size;
140	}
141}
142
143void
144stack_pushnumber(struct stack *stack, struct number *b)
145{
146	stack_grow(stack);
147	stack->stack[stack->sp].type = BCODE_NUMBER;
148	stack->stack[stack->sp].u.num = b;
149	stack->stack[stack->sp].array = NULL;
150}
151
152void
153stack_pushstring(struct stack *stack, char *string)
154{
155	stack_grow(stack);
156	stack->stack[stack->sp].type = BCODE_STRING;
157	stack->stack[stack->sp].u.string = string;
158	stack->stack[stack->sp].array = NULL;
159}
160
161void
162stack_push(struct stack *stack, struct value *v)
163{
164	switch (v->type) {
165	case BCODE_NONE:
166		stack_grow(stack);
167		stack->stack[stack->sp].type = BCODE_NONE;
168		break;
169	case BCODE_NUMBER:
170		stack_pushnumber(stack, v->u.num);
171		break;
172	case BCODE_STRING:
173		stack_pushstring(stack, v->u.string);
174		break;
175	}
176	stack->stack[stack->sp].array = v->array == NULL ?
177	    NULL : array_dup(v->array);
178}
179
180struct value *
181stack_tos(const struct stack *stack)
182{
183	if (stack->sp == -1)
184		return NULL;
185	return &stack->stack[stack->sp];
186}
187
188void
189stack_set_tos(struct stack *stack, struct value *v)
190{
191	if (stack->sp == -1)
192		stack_push(stack, v);
193	else {
194		stack_free_value(&stack->stack[stack->sp]);
195		stack->stack[stack->sp] = *v;
196		stack->stack[stack->sp].array = v->array == NULL ?
197		    NULL : array_dup(v->array);
198	}
199}
200
201struct value *
202stack_pop(struct stack *stack)
203{
204	if (stack_empty(stack))
205		return NULL;
206	return &stack->stack[stack->sp--];
207}
208
209struct number *
210stack_popnumber(struct stack *stack)
211{
212	if (stack_empty(stack))
213		return NULL;
214	array_free(stack->stack[stack->sp].array);
215	stack->stack[stack->sp].array = NULL;
216	if (stack->stack[stack->sp].type != BCODE_NUMBER) {
217		warnx("not a number"); /* XXX remove */
218		return NULL;
219	}
220	return stack->stack[stack->sp--].u.num;
221}
222
223char *
224stack_popstring(struct stack *stack)
225{
226	if (stack_empty(stack))
227		return NULL;
228	array_free(stack->stack[stack->sp].array);
229	stack->stack[stack->sp].array = NULL;
230	if (stack->stack[stack->sp].type != BCODE_STRING) {
231		warnx("not a string"); /* XXX remove */
232		return NULL;
233	}
234	return stack->stack[stack->sp--].u.string;
235}
236
237void
238stack_clear(struct stack *stack)
239{
240	while (stack->sp >= 0)
241		stack_free_value(&stack->stack[stack->sp--]);
242	free(stack->stack);
243	stack_init(stack);
244}
245
246void
247stack_print(FILE *f, const struct stack *stack, const char *prefix, u_int base)
248{
249	ssize_t i;
250
251	for (i = stack->sp; i >= 0; i--) {
252		print_value(f, &stack->stack[i], prefix, base);
253		(void)putc('\n', f);
254	}
255}
256
257
258static struct array *
259array_new(void)
260{
261	struct array *a;
262
263	a = bmalloc(sizeof(*a));
264	a->data = NULL;
265	a->size = 0;
266	return a;
267}
268
269static __inline void
270array_free(struct array *a)
271{
272	size_t i;
273
274	if (a == NULL)
275		return;
276	for (i = 0; i < a->size; i++)
277		stack_free_value(&a->data[i]);
278	free(a->data);
279	free(a);
280}
281
282static struct array *
283array_dup(const struct array *a)
284{
285	struct array	*n;
286	size_t		i;
287
288	if (a == NULL)
289		return NULL;
290	n = array_new();
291	array_grow(n, a->size);
292	for (i = 0; i < a->size; i++)
293		(void)stack_dup_value(&a->data[i], &n->data[i]);
294	return n;
295}
296
297static __inline void
298array_grow(struct array *array, size_t newsize)
299{
300	size_t i;
301
302	array->data = breallocarray(array->data, newsize, sizeof(*array->data));
303	for (i = array->size; i < newsize; i++) {
304		array->data[i].type = BCODE_NONE;
305		array->data[i].array = NULL;
306	}
307	array->size = newsize;
308}
309
310static __inline void
311array_assign(struct array *array, size_t index, const struct value *v)
312{
313	if (index >= array->size)
314		array_grow(array, index+1);
315	stack_free_value(&array->data[index]);
316	array->data[index] = *v;
317}
318
319static __inline struct value *
320array_retrieve(const struct array *array, size_t index)
321{
322	if (index >= array->size)
323		return NULL;
324	return &array->data[index];
325}
326
327void
328frame_assign(struct stack *stack, size_t index, const struct value *v)
329{
330	struct array *a;
331	struct value n;
332
333	if (stack->sp == -1) {
334		n.type = BCODE_NONE;
335		n.array = NULL;
336		stack_push(stack, &n);
337	}
338
339	a = stack->stack[stack->sp].array;
340	if (a == NULL)
341		a = stack->stack[stack->sp].array = array_new();
342	array_assign(a, index, v);
343}
344
345struct value *
346frame_retrieve(const struct stack *stack, size_t index)
347{
348	struct array *a;
349
350	if (stack->sp == -1)
351		return NULL;
352	a = stack->stack[stack->sp].array;
353	if (a == NULL)
354		a = stack->stack[stack->sp].array = array_new();
355	return array_retrieve(a, index);
356}
357