1314445Spfg/* $OpenBSD: stack.c,v 1.12 2014/11/26 15:05:51 otto Exp $ */ 2202719Sgabor 3202719Sgabor/* 4202719Sgabor * Copyright (c) 2003, Otto Moerbeek <otto@drijf.net> 5202719Sgabor * 6202719Sgabor * Permission to use, copy, modify, and distribute this software for any 7202719Sgabor * purpose with or without fee is hereby granted, provided that the above 8202719Sgabor * copyright notice and this permission notice appear in all copies. 9202719Sgabor * 10202719Sgabor * THE SOFTWARE IS PROVIDED "AS IS" AND THE AUTHOR DISCLAIMS ALL WARRANTIES 11202719Sgabor * WITH REGARD TO THIS SOFTWARE INCLUDING ALL IMPLIED WARRANTIES OF 12202719Sgabor * MERCHANTABILITY AND FITNESS. IN NO EVENT SHALL THE AUTHOR BE LIABLE FOR 13202719Sgabor * ANY SPECIAL, DIRECT, INDIRECT, OR CONSEQUENTIAL DAMAGES OR ANY DAMAGES 14202719Sgabor * WHATSOEVER RESULTING FROM LOSS OF USE, DATA OR PROFITS, WHETHER IN AN 15202719Sgabor * ACTION OF CONTRACT, NEGLIGENCE OR OTHER TORTIOUS ACTION, ARISING OUT OF 16202719Sgabor * OR IN CONNECTION WITH THE USE OR PERFORMANCE OF THIS SOFTWARE. 17202719Sgabor */ 18202719Sgabor 19202719Sgabor#include <sys/cdefs.h> 20202719Sgabor__FBSDID("$FreeBSD: stable/10/usr.bin/dc/stack.c 315135 2017-03-12 05:36:31Z pfg $"); 21202719Sgabor 22202719Sgabor#include <err.h> 23202719Sgabor#include <stdlib.h> 24202719Sgabor#include <string.h> 25202719Sgabor 26202719Sgabor#include "extern.h" 27202719Sgabor 28202719Sgaborstatic __inline bool stack_empty(const struct stack *); 29202719Sgaborstatic void stack_grow(struct stack *); 30202719Sgaborstatic struct array *array_new(void); 31202719Sgaborstatic __inline void array_free(struct array *); 32202719Sgaborstatic struct array *array_dup(const struct array *); 33202719Sgaborstatic __inline void array_grow(struct array *, size_t); 34202719Sgaborstatic __inline void array_assign(struct array *, size_t, const struct value *); 35202719Sgaborstatic __inline struct value *array_retrieve(const struct array *, size_t); 36202719Sgabor 37202719Sgaborvoid 38202719Sgaborstack_init(struct stack *stack) 39202719Sgabor{ 40202719Sgabor 41202719Sgabor stack->size = 0; 42202719Sgabor stack->sp = -1; 43202719Sgabor stack->stack = NULL; 44202719Sgabor} 45202719Sgabor 46202719Sgaborstatic __inline bool 47202719Sgaborstack_empty(const struct stack *stack) 48202719Sgabor{ 49203443Sgabor bool empty = stack->sp == -1; 50202719Sgabor 51202719Sgabor if (empty) 52202719Sgabor warnx("stack empty"); 53202719Sgabor return empty; 54202719Sgabor} 55202719Sgabor 56202719Sgabor/* Clear number or string, but leave value itself */ 57202719Sgaborvoid 58202719Sgaborstack_free_value(struct value *v) 59202719Sgabor{ 60202719Sgabor 61202719Sgabor switch (v->type) { 62202719Sgabor case BCODE_NONE: 63202719Sgabor break; 64202719Sgabor case BCODE_NUMBER: 65202719Sgabor free_number(v->u.num); 66202719Sgabor break; 67202719Sgabor case BCODE_STRING: 68202719Sgabor free(v->u.string); 69202719Sgabor break; 70202719Sgabor } 71315135Spfg array_free(v->array); 72315135Spfg v->array = NULL; 73202719Sgabor} 74202719Sgabor 75202719Sgabor/* Copy number or string content into already allocated target */ 76202719Sgaborstruct value * 77202719Sgaborstack_dup_value(const struct value *a, struct value *copy) 78202719Sgabor{ 79202719Sgabor 80202719Sgabor copy->type = a->type; 81202719Sgabor 82202719Sgabor switch (a->type) { 83202719Sgabor case BCODE_NONE: 84202719Sgabor break; 85202719Sgabor case BCODE_NUMBER: 86202719Sgabor copy->u.num = dup_number(a->u.num); 87202719Sgabor break; 88202719Sgabor case BCODE_STRING: 89202719Sgabor copy->u.string = strdup(a->u.string); 90202719Sgabor if (copy->u.string == NULL) 91202719Sgabor err(1, NULL); 92202719Sgabor break; 93202719Sgabor } 94202719Sgabor 95202719Sgabor copy->array = a->array == NULL ? NULL : array_dup(a->array); 96202719Sgabor 97202719Sgabor return (copy); 98202719Sgabor} 99202719Sgabor 100202719Sgaborsize_t 101202719Sgaborstack_size(const struct stack *stack) 102202719Sgabor{ 103202719Sgabor 104202719Sgabor return (stack->sp + 1); 105202719Sgabor} 106202719Sgabor 107202719Sgaborvoid 108202719Sgaborstack_dup(struct stack *stack) 109202719Sgabor{ 110203443Sgabor struct value *value; 111203443Sgabor struct value copy; 112202719Sgabor 113202719Sgabor value = stack_tos(stack); 114202719Sgabor if (value == NULL) { 115202719Sgabor warnx("stack empty"); 116202719Sgabor return; 117202719Sgabor } 118202719Sgabor stack_push(stack, stack_dup_value(value, ©)); 119202719Sgabor} 120202719Sgabor 121202719Sgaborvoid 122202719Sgaborstack_swap(struct stack *stack) 123202719Sgabor{ 124203443Sgabor struct value copy; 125202719Sgabor 126202719Sgabor if (stack->sp < 1) { 127202719Sgabor warnx("stack empty"); 128202719Sgabor return; 129202719Sgabor } 130202719Sgabor copy = stack->stack[stack->sp]; 131202719Sgabor stack->stack[stack->sp] = stack->stack[stack->sp-1]; 132202719Sgabor stack->stack[stack->sp-1] = copy; 133202719Sgabor} 134202719Sgabor 135202719Sgaborstatic void 136202719Sgaborstack_grow(struct stack *stack) 137202719Sgabor{ 138275348Skevlo size_t new_size; 139202719Sgabor 140202719Sgabor if (++stack->sp == stack->size) { 141202719Sgabor new_size = stack->size * 2 + 1; 142202719Sgabor stack->stack = brealloc(stack->stack, 143202719Sgabor new_size * sizeof(*stack->stack)); 144202719Sgabor stack->size = new_size; 145202719Sgabor } 146202719Sgabor} 147202719Sgabor 148202719Sgaborvoid 149202719Sgaborstack_pushnumber(struct stack *stack, struct number *b) 150202719Sgabor{ 151202719Sgabor 152202719Sgabor stack_grow(stack); 153202719Sgabor stack->stack[stack->sp].type = BCODE_NUMBER; 154202719Sgabor stack->stack[stack->sp].u.num = b; 155275348Skevlo stack->stack[stack->sp].array = NULL; 156202719Sgabor} 157202719Sgabor 158202719Sgaborvoid 159202719Sgaborstack_pushstring(struct stack *stack, char *string) 160202719Sgabor{ 161202719Sgabor 162202719Sgabor stack_grow(stack); 163202719Sgabor stack->stack[stack->sp].type = BCODE_STRING; 164202719Sgabor stack->stack[stack->sp].u.string = string; 165275348Skevlo stack->stack[stack->sp].array = NULL; 166202719Sgabor} 167202719Sgabor 168202719Sgaborvoid 169202719Sgaborstack_push(struct stack *stack, struct value *v) 170202719Sgabor{ 171202719Sgabor 172202719Sgabor switch (v->type) { 173202719Sgabor case BCODE_NONE: 174202719Sgabor stack_grow(stack); 175202719Sgabor stack->stack[stack->sp].type = BCODE_NONE; 176202719Sgabor break; 177202719Sgabor case BCODE_NUMBER: 178202719Sgabor stack_pushnumber(stack, v->u.num); 179202719Sgabor break; 180202719Sgabor case BCODE_STRING: 181202719Sgabor stack_pushstring(stack, v->u.string); 182202719Sgabor break; 183202719Sgabor } 184202719Sgabor stack->stack[stack->sp].array = v->array == NULL ? 185202719Sgabor NULL : array_dup(v->array); 186202719Sgabor} 187202719Sgabor 188202719Sgaborstruct value * 189202719Sgaborstack_tos(const struct stack *stack) 190202719Sgabor{ 191202719Sgabor 192202719Sgabor if (stack->sp == -1) 193202719Sgabor return (NULL); 194202719Sgabor return &stack->stack[stack->sp]; 195202719Sgabor} 196202719Sgabor 197202719Sgaborvoid 198202719Sgaborstack_set_tos(struct stack *stack, struct value *v) 199202719Sgabor{ 200202719Sgabor 201202719Sgabor if (stack->sp == -1) 202202719Sgabor stack_push(stack, v); 203202719Sgabor else { 204202719Sgabor stack_free_value(&stack->stack[stack->sp]); 205202719Sgabor stack->stack[stack->sp] = *v; 206202719Sgabor stack->stack[stack->sp].array = v->array == NULL ? 207202719Sgabor NULL : array_dup(v->array); 208202719Sgabor } 209202719Sgabor} 210202719Sgabor 211202719Sgaborstruct value * 212202719Sgaborstack_pop(struct stack *stack) 213202719Sgabor{ 214202719Sgabor 215202719Sgabor if (stack_empty(stack)) 216202719Sgabor return (NULL); 217202719Sgabor return &stack->stack[stack->sp--]; 218202719Sgabor} 219202719Sgabor 220202719Sgaborstruct number * 221202719Sgaborstack_popnumber(struct stack *stack) 222202719Sgabor{ 223202719Sgabor 224202719Sgabor if (stack_empty(stack)) 225202719Sgabor return (NULL); 226315135Spfg array_free(stack->stack[stack->sp].array); 227315135Spfg stack->stack[stack->sp].array = NULL; 228202719Sgabor if (stack->stack[stack->sp].type != BCODE_NUMBER) { 229202719Sgabor warnx("not a number"); /* XXX remove */ 230202719Sgabor return (NULL); 231202719Sgabor } 232202719Sgabor return stack->stack[stack->sp--].u.num; 233202719Sgabor} 234202719Sgabor 235202719Sgaborchar * 236202719Sgaborstack_popstring(struct stack *stack) 237202719Sgabor{ 238202719Sgabor 239202719Sgabor if (stack_empty(stack)) 240202719Sgabor return (NULL); 241315135Spfg array_free(stack->stack[stack->sp].array); 242315135Spfg stack->stack[stack->sp].array = NULL; 243202719Sgabor if (stack->stack[stack->sp].type != BCODE_STRING) { 244202719Sgabor warnx("not a string"); /* XXX remove */ 245202719Sgabor return (NULL); 246202719Sgabor } 247202719Sgabor return stack->stack[stack->sp--].u.string; 248202719Sgabor} 249202719Sgabor 250202719Sgaborvoid 251202719Sgaborstack_clear(struct stack *stack) 252202719Sgabor{ 253202719Sgabor 254315135Spfg while (stack->sp >= 0) 255202719Sgabor stack_free_value(&stack->stack[stack->sp--]); 256202719Sgabor free(stack->stack); 257202719Sgabor stack_init(stack); 258202719Sgabor} 259202719Sgabor 260202719Sgaborvoid 261202719Sgaborstack_print(FILE *f, const struct stack *stack, const char *prefix, u_int base) 262202719Sgabor{ 263203443Sgabor ssize_t i; 264202719Sgabor 265202719Sgabor for (i = stack->sp; i >= 0; i--) { 266202719Sgabor print_value(f, &stack->stack[i], prefix, base); 267202719Sgabor putc('\n', f); 268202719Sgabor } 269202719Sgabor} 270202719Sgabor 271202719Sgabor 272202719Sgaborstatic struct array * 273202719Sgaborarray_new(void) 274202719Sgabor{ 275203443Sgabor struct array *a; 276202719Sgabor 277202719Sgabor a = bmalloc(sizeof(*a)); 278202719Sgabor a->data = NULL; 279202719Sgabor a->size = 0; 280202719Sgabor return a; 281202719Sgabor} 282202719Sgabor 283202719Sgaborstatic __inline void 284202719Sgaborarray_free(struct array *a) 285202719Sgabor{ 286203443Sgabor size_t i; 287202719Sgabor 288202719Sgabor if (a == NULL) 289202719Sgabor return; 290202719Sgabor for (i = 0; i < a->size; i++) 291202719Sgabor stack_free_value(&a->data[i]); 292202719Sgabor free(a->data); 293202719Sgabor free(a); 294202719Sgabor} 295202719Sgabor 296202719Sgaborstatic struct array * 297202719Sgaborarray_dup(const struct array *a) 298202719Sgabor{ 299203443Sgabor struct array *n; 300203443Sgabor size_t i; 301202719Sgabor 302202719Sgabor if (a == NULL) 303202719Sgabor return (NULL); 304202719Sgabor n = array_new(); 305202719Sgabor array_grow(n, a->size); 306202719Sgabor for (i = 0; i < a->size; i++) 307202719Sgabor stack_dup_value(&a->data[i], &n->data[i]); 308202719Sgabor return (n); 309202719Sgabor} 310202719Sgabor 311202719Sgaborstatic __inline void 312202719Sgaborarray_grow(struct array *array, size_t newsize) 313202719Sgabor{ 314203443Sgabor size_t i; 315202719Sgabor 316202719Sgabor array->data = brealloc(array->data, newsize * sizeof(*array->data)); 317202719Sgabor for (i = array->size; i < newsize; i++) { 318202719Sgabor array->data[i].type = BCODE_NONE; 319202719Sgabor array->data[i].array = NULL; 320202719Sgabor } 321202719Sgabor array->size = newsize; 322202719Sgabor} 323202719Sgabor 324202719Sgaborstatic __inline void 325202719Sgaborarray_assign(struct array *array, size_t i, const struct value *v) 326202719Sgabor{ 327202719Sgabor 328202719Sgabor if (i >= array->size) 329202719Sgabor array_grow(array, i + 1); 330202719Sgabor stack_free_value(&array->data[i]); 331202719Sgabor array->data[i] = *v; 332202719Sgabor} 333202719Sgabor 334202719Sgaborstatic __inline struct value * 335202719Sgaborarray_retrieve(const struct array *array, size_t i) 336202719Sgabor{ 337202719Sgabor 338202719Sgabor if (i >= array->size) 339202719Sgabor return (NULL); 340202719Sgabor return &array->data[i]; 341202719Sgabor} 342202719Sgabor 343202719Sgaborvoid 344202719Sgaborframe_assign(struct stack *stack, size_t i, const struct value *v) 345202719Sgabor{ 346203443Sgabor struct array *a; 347203443Sgabor struct value n; 348202719Sgabor 349202719Sgabor if (stack->sp == -1) { 350202719Sgabor n.type = BCODE_NONE; 351202719Sgabor n.array = NULL; 352202719Sgabor stack_push(stack, &n); 353202719Sgabor } 354202719Sgabor 355202719Sgabor a = stack->stack[stack->sp].array; 356202719Sgabor if (a == NULL) 357202719Sgabor a = stack->stack[stack->sp].array = array_new(); 358202719Sgabor array_assign(a, i, v); 359202719Sgabor} 360202719Sgabor 361202719Sgaborstruct value * 362202719Sgaborframe_retrieve(const struct stack *stack, size_t i) 363202719Sgabor{ 364203443Sgabor struct array *a; 365202719Sgabor 366202719Sgabor if (stack->sp == -1) 367202719Sgabor return (NULL); 368202719Sgabor a = stack->stack[stack->sp].array; 369202719Sgabor if (a == NULL) 370202719Sgabor a = stack->stack[stack->sp].array = array_new(); 371202719Sgabor return array_retrieve(a, i); 372202719Sgabor} 373