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, ©)); 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