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