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