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