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