Annotation of src/usr.bin/dc/stack.c, Revision 1.15
1.15 ! otto 1: /* $OpenBSD: stack.c,v 1.14 2016/03/27 15:55:13 otto Exp $ */
1.1 otto 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:
25: static __inline bool stack_empty(const struct stack *);
26: static void stack_grow(struct stack *);
27: static struct array *array_new(void);
28: static __inline void array_free(struct array *);
29: static struct array * array_dup(const struct array *);
30: static __inline void array_grow(struct array *, size_t);
31: static __inline void array_assign(struct array *, size_t, const struct value *);
32: static __inline struct value *array_retrieve(const struct array *, size_t);
33:
34: void
35: stack_init(struct stack *stack)
36: {
37: stack->size = 0;
38: stack->sp = -1;
39: stack->stack = NULL;
40: }
41:
42: static __inline bool
1.7 deraadt 43: stack_empty(const struct stack *stack)
1.1 otto 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 */
52: void
53: stack_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: }
1.14 otto 65: array_free(v->array);
66: v->array = NULL;
1.1 otto 67: }
68:
69: /* Copy number or string content into already allocated target */
70: struct value *
71: stack_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:
1.15 ! otto 82: copy->u.string = bstrdup(a->u.string);
1.1 otto 83: break;
84: }
85:
86: copy->array = a->array == NULL ? NULL : array_dup(a->array);
87:
88: return copy;
89: }
90:
1.9 otto 91: size_t
1.7 deraadt 92: stack_size(const struct stack *stack)
1.1 otto 93: {
94: return stack->sp + 1;
95: }
96:
97: void
98: stack_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, ©));
1.5 otto 109: }
110:
111: void
112: stack_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;
1.1 otto 123: }
124:
125: static void
126: stack_grow(struct stack *stack)
127: {
1.12 otto 128: size_t new_size;
1.1 otto 129:
130: if (++stack->sp == stack->size) {
1.3 otto 131: new_size = stack->size * 2 + 1;
1.13 deraadt 132: stack->stack = breallocarray(stack->stack,
133: new_size, sizeof(*stack->stack));
1.3 otto 134: stack->size = new_size;
1.1 otto 135: }
136: }
137:
138: void
139: stack_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;
1.12 otto 144: stack->stack[stack->sp].array = NULL;
1.1 otto 145: }
146:
147: void
148: stack_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;
1.12 otto 153: stack->stack[stack->sp].array = NULL;
1.1 otto 154: }
155:
156: void
157: stack_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:
175: struct value *
176: stack_tos(const struct stack *stack)
177: {
178: if (stack->sp == -1)
179: return NULL;
180: return &stack->stack[stack->sp];
181: }
182:
183: void
184: stack_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 ?
1.7 deraadt 192: NULL : array_dup(v->array);
1.1 otto 193: }
194: }
195:
196: struct value *
197: stack_pop(struct stack *stack)
198: {
199: if (stack_empty(stack))
200: return NULL;
201: return &stack->stack[stack->sp--];
202: }
203:
204: struct number *
205: stack_popnumber(struct stack *stack)
206: {
207: if (stack_empty(stack))
208: return NULL;
1.14 otto 209: array_free(stack->stack[stack->sp].array);
210: stack->stack[stack->sp].array = NULL;
1.1 otto 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:
218: char *
219: stack_popstring(struct stack *stack)
220: {
221: if (stack_empty(stack))
222: return NULL;
1.14 otto 223: array_free(stack->stack[stack->sp].array);
224: stack->stack[stack->sp].array = NULL;
1.1 otto 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:
232: void
233: stack_clear(struct stack *stack)
234: {
1.14 otto 235: while (stack->sp >= 0)
1.1 otto 236: stack_free_value(&stack->stack[stack->sp--]);
237: free(stack->stack);
238: stack_init(stack);
239: }
240:
241: void
242: stack_print(FILE *f, const struct stack *stack, const char *prefix, u_int base)
243: {
1.9 otto 244: ssize_t i;
1.1 otto 245:
246: for (i = stack->sp; i >= 0; i--) {
247: print_value(f, &stack->stack[i], prefix, base);
1.8 otto 248: (void)putc('\n', f);
1.1 otto 249: }
250: }
251:
252:
253: static struct array *
254: array_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:
264: static __inline void
265: array_free(struct array *a)
266: {
1.9 otto 267: size_t i;
1.1 otto 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:
277: static struct array *
278: array_dup(const struct array *a)
279: {
280: struct array *n;
1.9 otto 281: size_t i;
1.1 otto 282:
283: if (a == NULL)
284: return NULL;
285: n = array_new();
286: array_grow(n, a->size);
1.2 deraadt 287: for (i = 0; i < a->size; i++)
1.8 otto 288: (void)stack_dup_value(&a->data[i], &n->data[i]);
1.1 otto 289: return n;
290: }
291:
292: static __inline void
293: array_grow(struct array *array, size_t newsize)
294: {
295: size_t i;
296:
1.13 deraadt 297: array->data = breallocarray(array->data, newsize, sizeof(*array->data));
1.10 otto 298: for (i = array->size; i < newsize; i++) {
299: array->data[i].type = BCODE_NONE;
1.1 otto 300: array->data[i].array = NULL;
1.10 otto 301: }
1.1 otto 302: array->size = newsize;
303: }
304:
305: static __inline void
306: array_assign(struct array *array, size_t index, const struct value *v)
307: {
308: if (index >= array->size)
309: array_grow(array, index+1);
1.10 otto 310: stack_free_value(&array->data[index]);
1.1 otto 311: array->data[index] = *v;
312: }
313:
314: static __inline struct value *
315: array_retrieve(const struct array *array, size_t index)
316: {
317: if (index >= array->size)
318: return NULL;
319: return &array->data[index];
320: }
321:
322: void
323: frame_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:
340: struct value *
341: frame_retrieve(const struct stack *stack, size_t index)
342: {
343: struct array *a;
344:
1.6 otto 345: if (stack->sp == -1)
346: return NULL;
1.1 otto 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: }