1202719Sgabor/* $OpenBSD: stack.c,v 1.11 2009/10/27 23:59:37 deraadt 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$"); 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 } 71202719Sgabor if (v->array != NULL) { 72202719Sgabor array_free(v->array); 73202719Sgabor v->array = NULL; 74202719Sgabor } 75202719Sgabor} 76202719Sgabor 77202719Sgabor/* Copy number or string content into already allocated target */ 78202719Sgaborstruct value * 79202719Sgaborstack_dup_value(const struct value *a, struct value *copy) 80202719Sgabor{ 81202719Sgabor 82202719Sgabor copy->type = a->type; 83202719Sgabor 84202719Sgabor switch (a->type) { 85202719Sgabor case BCODE_NONE: 86202719Sgabor break; 87202719Sgabor case BCODE_NUMBER: 88202719Sgabor copy->u.num = dup_number(a->u.num); 89202719Sgabor break; 90202719Sgabor case BCODE_STRING: 91202719Sgabor copy->u.string = strdup(a->u.string); 92202719Sgabor if (copy->u.string == NULL) 93202719Sgabor err(1, NULL); 94202719Sgabor break; 95202719Sgabor } 96202719Sgabor 97202719Sgabor copy->array = a->array == NULL ? NULL : array_dup(a->array); 98202719Sgabor 99202719Sgabor return (copy); 100202719Sgabor} 101202719Sgabor 102202719Sgaborsize_t 103202719Sgaborstack_size(const struct stack *stack) 104202719Sgabor{ 105202719Sgabor 106202719Sgabor return (stack->sp + 1); 107202719Sgabor} 108202719Sgabor 109202719Sgaborvoid 110202719Sgaborstack_dup(struct stack *stack) 111202719Sgabor{ 112203443Sgabor struct value *value; 113203443Sgabor struct value copy; 114202719Sgabor 115202719Sgabor value = stack_tos(stack); 116202719Sgabor if (value == NULL) { 117202719Sgabor warnx("stack empty"); 118202719Sgabor return; 119202719Sgabor } 120202719Sgabor stack_push(stack, stack_dup_value(value, ©)); 121202719Sgabor} 122202719Sgabor 123202719Sgaborvoid 124202719Sgaborstack_swap(struct stack *stack) 125202719Sgabor{ 126203443Sgabor struct value copy; 127202719Sgabor 128202719Sgabor if (stack->sp < 1) { 129202719Sgabor warnx("stack empty"); 130202719Sgabor return; 131202719Sgabor } 132202719Sgabor copy = stack->stack[stack->sp]; 133202719Sgabor stack->stack[stack->sp] = stack->stack[stack->sp-1]; 134202719Sgabor stack->stack[stack->sp-1] = copy; 135202719Sgabor} 136202719Sgabor 137202719Sgaborstatic void 138202719Sgaborstack_grow(struct stack *stack) 139202719Sgabor{ 140203443Sgabor size_t i, new_size; 141202719Sgabor 142202719Sgabor if (++stack->sp == stack->size) { 143202719Sgabor new_size = stack->size * 2 + 1; 144202719Sgabor stack->stack = brealloc(stack->stack, 145202719Sgabor new_size * sizeof(*stack->stack)); 146202719Sgabor for (i = stack->size; i < new_size; i++) 147202719Sgabor stack->stack[i].array = NULL; 148202719Sgabor stack->size = new_size; 149202719Sgabor } 150202719Sgabor} 151202719Sgabor 152202719Sgaborvoid 153202719Sgaborstack_pushnumber(struct stack *stack, struct number *b) 154202719Sgabor{ 155202719Sgabor 156202719Sgabor stack_grow(stack); 157202719Sgabor stack->stack[stack->sp].type = BCODE_NUMBER; 158202719Sgabor stack->stack[stack->sp].u.num = b; 159202719Sgabor} 160202719Sgabor 161202719Sgaborvoid 162202719Sgaborstack_pushstring(struct stack *stack, char *string) 163202719Sgabor{ 164202719Sgabor 165202719Sgabor stack_grow(stack); 166202719Sgabor stack->stack[stack->sp].type = BCODE_STRING; 167202719Sgabor stack->stack[stack->sp].u.string = string; 168202719Sgabor} 169202719Sgabor 170202719Sgaborvoid 171202719Sgaborstack_push(struct stack *stack, struct value *v) 172202719Sgabor{ 173202719Sgabor 174202719Sgabor switch (v->type) { 175202719Sgabor case BCODE_NONE: 176202719Sgabor stack_grow(stack); 177202719Sgabor stack->stack[stack->sp].type = BCODE_NONE; 178202719Sgabor break; 179202719Sgabor case BCODE_NUMBER: 180202719Sgabor stack_pushnumber(stack, v->u.num); 181202719Sgabor break; 182202719Sgabor case BCODE_STRING: 183202719Sgabor stack_pushstring(stack, v->u.string); 184202719Sgabor break; 185202719Sgabor } 186202719Sgabor stack->stack[stack->sp].array = v->array == NULL ? 187202719Sgabor NULL : array_dup(v->array); 188202719Sgabor} 189202719Sgabor 190202719Sgaborstruct value * 191202719Sgaborstack_tos(const struct stack *stack) 192202719Sgabor{ 193202719Sgabor 194202719Sgabor if (stack->sp == -1) 195202719Sgabor return (NULL); 196202719Sgabor return &stack->stack[stack->sp]; 197202719Sgabor} 198202719Sgabor 199202719Sgaborvoid 200202719Sgaborstack_set_tos(struct stack *stack, struct value *v) 201202719Sgabor{ 202202719Sgabor 203202719Sgabor if (stack->sp == -1) 204202719Sgabor stack_push(stack, v); 205202719Sgabor else { 206202719Sgabor stack_free_value(&stack->stack[stack->sp]); 207202719Sgabor stack->stack[stack->sp] = *v; 208202719Sgabor stack->stack[stack->sp].array = v->array == NULL ? 209202719Sgabor NULL : array_dup(v->array); 210202719Sgabor } 211202719Sgabor} 212202719Sgabor 213202719Sgaborstruct value * 214202719Sgaborstack_pop(struct stack *stack) 215202719Sgabor{ 216202719Sgabor 217202719Sgabor if (stack_empty(stack)) 218202719Sgabor return (NULL); 219202719Sgabor return &stack->stack[stack->sp--]; 220202719Sgabor} 221202719Sgabor 222202719Sgaborstruct number * 223202719Sgaborstack_popnumber(struct stack *stack) 224202719Sgabor{ 225202719Sgabor 226202719Sgabor if (stack_empty(stack)) 227202719Sgabor return (NULL); 228202719Sgabor if (stack->stack[stack->sp].array != NULL) { 229202719Sgabor array_free(stack->stack[stack->sp].array); 230202719Sgabor stack->stack[stack->sp].array = NULL; 231202719Sgabor } 232202719Sgabor if (stack->stack[stack->sp].type != BCODE_NUMBER) { 233202719Sgabor warnx("not a number"); /* XXX remove */ 234202719Sgabor return (NULL); 235202719Sgabor } 236202719Sgabor return stack->stack[stack->sp--].u.num; 237202719Sgabor} 238202719Sgabor 239202719Sgaborchar * 240202719Sgaborstack_popstring(struct stack *stack) 241202719Sgabor{ 242202719Sgabor 243202719Sgabor if (stack_empty(stack)) 244202719Sgabor return (NULL); 245202719Sgabor if (stack->stack[stack->sp].array != NULL) { 246202719Sgabor array_free(stack->stack[stack->sp].array); 247202719Sgabor stack->stack[stack->sp].array = NULL; 248202719Sgabor } 249202719Sgabor if (stack->stack[stack->sp].type != BCODE_STRING) { 250202719Sgabor warnx("not a string"); /* XXX remove */ 251202719Sgabor return (NULL); 252202719Sgabor } 253202719Sgabor return stack->stack[stack->sp--].u.string; 254202719Sgabor} 255202719Sgabor 256202719Sgaborvoid 257202719Sgaborstack_clear(struct stack *stack) 258202719Sgabor{ 259202719Sgabor 260202719Sgabor while (stack->sp >= 0) { 261202719Sgabor stack_free_value(&stack->stack[stack->sp--]); 262202719Sgabor } 263202719Sgabor free(stack->stack); 264202719Sgabor stack_init(stack); 265202719Sgabor} 266202719Sgabor 267202719Sgaborvoid 268202719Sgaborstack_print(FILE *f, const struct stack *stack, const char *prefix, u_int base) 269202719Sgabor{ 270203443Sgabor ssize_t i; 271202719Sgabor 272202719Sgabor for (i = stack->sp; i >= 0; i--) { 273202719Sgabor print_value(f, &stack->stack[i], prefix, base); 274202719Sgabor putc('\n', f); 275202719Sgabor } 276202719Sgabor} 277202719Sgabor 278202719Sgabor 279202719Sgaborstatic struct array * 280202719Sgaborarray_new(void) 281202719Sgabor{ 282203443Sgabor struct array *a; 283202719Sgabor 284202719Sgabor a = bmalloc(sizeof(*a)); 285202719Sgabor a->data = NULL; 286202719Sgabor a->size = 0; 287202719Sgabor return a; 288202719Sgabor} 289202719Sgabor 290202719Sgaborstatic __inline void 291202719Sgaborarray_free(struct array *a) 292202719Sgabor{ 293203443Sgabor size_t i; 294202719Sgabor 295202719Sgabor if (a == NULL) 296202719Sgabor return; 297202719Sgabor for (i = 0; i < a->size; i++) 298202719Sgabor stack_free_value(&a->data[i]); 299202719Sgabor free(a->data); 300202719Sgabor free(a); 301202719Sgabor} 302202719Sgabor 303202719Sgaborstatic struct array * 304202719Sgaborarray_dup(const struct array *a) 305202719Sgabor{ 306203443Sgabor struct array *n; 307203443Sgabor size_t i; 308202719Sgabor 309202719Sgabor if (a == NULL) 310202719Sgabor return (NULL); 311202719Sgabor n = array_new(); 312202719Sgabor array_grow(n, a->size); 313202719Sgabor for (i = 0; i < a->size; i++) 314202719Sgabor stack_dup_value(&a->data[i], &n->data[i]); 315202719Sgabor return (n); 316202719Sgabor} 317202719Sgabor 318202719Sgaborstatic __inline void 319202719Sgaborarray_grow(struct array *array, size_t newsize) 320202719Sgabor{ 321203443Sgabor size_t i; 322202719Sgabor 323202719Sgabor array->data = brealloc(array->data, newsize * sizeof(*array->data)); 324202719Sgabor for (i = array->size; i < newsize; i++) { 325202719Sgabor array->data[i].type = BCODE_NONE; 326202719Sgabor array->data[i].array = NULL; 327202719Sgabor } 328202719Sgabor array->size = newsize; 329202719Sgabor} 330202719Sgabor 331202719Sgaborstatic __inline void 332202719Sgaborarray_assign(struct array *array, size_t i, const struct value *v) 333202719Sgabor{ 334202719Sgabor 335202719Sgabor if (i >= array->size) 336202719Sgabor array_grow(array, i + 1); 337202719Sgabor stack_free_value(&array->data[i]); 338202719Sgabor array->data[i] = *v; 339202719Sgabor} 340202719Sgabor 341202719Sgaborstatic __inline struct value * 342202719Sgaborarray_retrieve(const struct array *array, size_t i) 343202719Sgabor{ 344202719Sgabor 345202719Sgabor if (i >= array->size) 346202719Sgabor return (NULL); 347202719Sgabor return &array->data[i]; 348202719Sgabor} 349202719Sgabor 350202719Sgaborvoid 351202719Sgaborframe_assign(struct stack *stack, size_t i, const struct value *v) 352202719Sgabor{ 353203443Sgabor struct array *a; 354203443Sgabor struct value n; 355202719Sgabor 356202719Sgabor if (stack->sp == -1) { 357202719Sgabor n.type = BCODE_NONE; 358202719Sgabor n.array = NULL; 359202719Sgabor stack_push(stack, &n); 360202719Sgabor } 361202719Sgabor 362202719Sgabor a = stack->stack[stack->sp].array; 363202719Sgabor if (a == NULL) 364202719Sgabor a = stack->stack[stack->sp].array = array_new(); 365202719Sgabor array_assign(a, i, v); 366202719Sgabor} 367202719Sgabor 368202719Sgaborstruct value * 369202719Sgaborframe_retrieve(const struct stack *stack, size_t i) 370202719Sgabor{ 371203443Sgabor struct array *a; 372202719Sgabor 373202719Sgabor if (stack->sp == -1) 374202719Sgabor return (NULL); 375202719Sgabor a = stack->stack[stack->sp].array; 376202719Sgabor if (a == NULL) 377202719Sgabor a = stack->stack[stack->sp].array = array_new(); 378202719Sgabor return array_retrieve(a, i); 379202719Sgabor} 380