1/* $OpenBSD: stack.c,v 1.13 2014/12/01 13:13:00 deraadt 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#include <err.h> 21#include <stdlib.h> 22#include <string.h> 23 24#include "extern.h" 25 26static __inline bool stack_empty(const struct stack *); 27static void stack_grow(struct stack *); 28static struct array *array_new(void); 29static __inline void array_free(struct array *); 30static struct array *array_dup(const struct array *); 31static __inline void array_grow(struct array *, size_t); 32static __inline void array_assign(struct array *, size_t, const struct value *); 33static __inline struct value *array_retrieve(const struct array *, size_t); 34 35void 36stack_init(struct stack *stack) 37{ 38 39 stack->size = 0; 40 stack->sp = -1; 41 stack->stack = NULL; 42} 43 44static __inline bool 45stack_empty(const struct stack *stack) 46{ 47 bool empty = stack->sp == -1; 48 49 if (empty) 50 warnx("stack empty"); 51 return empty; 52} 53 54/* Clear number or string, but leave value itself */ 55void 56stack_free_value(struct value *v) 57{ 58 59 switch (v->type) { 60 case BCODE_NONE: 61 break; 62 case BCODE_NUMBER: 63 free_number(v->u.num); 64 break; 65 case BCODE_STRING: 66 free(v->u.string); 67 break; 68 } 69 array_free(v->array); 70 v->array = NULL; 71} 72 73/* Copy number or string content into already allocated target */ 74struct value * 75stack_dup_value(const struct value *a, struct value *copy) 76{ 77 78 copy->type = a->type; 79 80 switch (a->type) { 81 case BCODE_NONE: 82 break; 83 case BCODE_NUMBER: 84 copy->u.num = dup_number(a->u.num); 85 break; 86 case BCODE_STRING: 87 copy->u.string = strdup(a->u.string); 88 if (copy->u.string == NULL) 89 err(1, NULL); 90 break; 91 } 92 93 copy->array = a->array == NULL ? NULL : array_dup(a->array); 94 95 return (copy); 96} 97 98size_t 99stack_size(const struct stack *stack) 100{ 101 102 return (stack->sp + 1); 103} 104 105void 106stack_dup(struct stack *stack) 107{ 108 struct value *value; 109 struct value copy; 110 111 value = stack_tos(stack); 112 if (value == NULL) { 113 warnx("stack empty"); 114 return; 115 } 116 stack_push(stack, stack_dup_value(value, ©)); 117} 118 119void 120stack_swap(struct stack *stack) 121{ 122 struct value copy; 123 124 if (stack->sp < 1) { 125 warnx("stack empty"); 126 return; 127 } 128 copy = stack->stack[stack->sp]; 129 stack->stack[stack->sp] = stack->stack[stack->sp-1]; 130 stack->stack[stack->sp-1] = copy; 131} 132 133static void 134stack_grow(struct stack *stack) 135{ 136 size_t new_size; 137 138 if (++stack->sp == stack->size) { 139 new_size = stack->size * 2 + 1; 140 stack->stack = breallocarray(stack->stack, 141 new_size, sizeof(*stack->stack)); 142 stack->size = new_size; 143 } 144} 145 146void 147stack_pushnumber(struct stack *stack, struct number *b) 148{ 149 150 stack_grow(stack); 151 stack->stack[stack->sp].type = BCODE_NUMBER; 152 stack->stack[stack->sp].u.num = b; 153 stack->stack[stack->sp].array = NULL; 154} 155 156void 157stack_pushstring(struct stack *stack, char *string) 158{ 159 160 stack_grow(stack); 161 stack->stack[stack->sp].type = BCODE_STRING; 162 stack->stack[stack->sp].u.string = string; 163 stack->stack[stack->sp].array = NULL; 164} 165 166void 167stack_push(struct stack *stack, struct value *v) 168{ 169 170 switch (v->type) { 171 case BCODE_NONE: 172 stack_grow(stack); 173 stack->stack[stack->sp].type = BCODE_NONE; 174 break; 175 case BCODE_NUMBER: 176 stack_pushnumber(stack, v->u.num); 177 break; 178 case BCODE_STRING: 179 stack_pushstring(stack, v->u.string); 180 break; 181 } 182 stack->stack[stack->sp].array = v->array == NULL ? 183 NULL : array_dup(v->array); 184} 185 186struct value * 187stack_tos(const struct stack *stack) 188{ 189 190 if (stack->sp == -1) 191 return (NULL); 192 return &stack->stack[stack->sp]; 193} 194 195void 196stack_set_tos(struct stack *stack, struct value *v) 197{ 198 199 if (stack->sp == -1) 200 stack_push(stack, v); 201 else { 202 stack_free_value(&stack->stack[stack->sp]); 203 stack->stack[stack->sp] = *v; 204 stack->stack[stack->sp].array = v->array == NULL ? 205 NULL : array_dup(v->array); 206 } 207} 208 209struct value * 210stack_pop(struct stack *stack) 211{ 212 213 if (stack_empty(stack)) 214 return (NULL); 215 return &stack->stack[stack->sp--]; 216} 217 218struct number * 219stack_popnumber(struct stack *stack) 220{ 221 222 if (stack_empty(stack)) 223 return (NULL); 224 array_free(stack->stack[stack->sp].array); 225 stack->stack[stack->sp].array = NULL; 226 if (stack->stack[stack->sp].type != BCODE_NUMBER) { 227 warnx("not a number"); /* XXX remove */ 228 return (NULL); 229 } 230 return stack->stack[stack->sp--].u.num; 231} 232 233char * 234stack_popstring(struct stack *stack) 235{ 236 237 if (stack_empty(stack)) 238 return (NULL); 239 array_free(stack->stack[stack->sp].array); 240 stack->stack[stack->sp].array = NULL; 241 if (stack->stack[stack->sp].type != BCODE_STRING) { 242 warnx("not a string"); /* XXX remove */ 243 return (NULL); 244 } 245 return stack->stack[stack->sp--].u.string; 246} 247 248void 249stack_clear(struct stack *stack) 250{ 251 252 while (stack->sp >= 0) 253 stack_free_value(&stack->stack[stack->sp--]); 254 free(stack->stack); 255 stack_init(stack); 256} 257 258void 259stack_print(FILE *f, const struct stack *stack, const char *prefix, u_int base) 260{ 261 ssize_t i; 262 263 for (i = stack->sp; i >= 0; i--) { 264 print_value(f, &stack->stack[i], prefix, base); 265 putc('\n', f); 266 } 267} 268 269 270static struct array * 271array_new(void) 272{ 273 struct array *a; 274 275 a = bmalloc(sizeof(*a)); 276 a->data = NULL; 277 a->size = 0; 278 return a; 279} 280 281static __inline void 282array_free(struct array *a) 283{ 284 size_t i; 285 286 if (a == NULL) 287 return; 288 for (i = 0; i < a->size; i++) 289 stack_free_value(&a->data[i]); 290 free(a->data); 291 free(a); 292} 293 294static struct array * 295array_dup(const struct array *a) 296{ 297 struct array *n; 298 size_t i; 299 300 if (a == NULL) 301 return (NULL); 302 n = array_new(); 303 array_grow(n, a->size); 304 for (i = 0; i < a->size; i++) 305 stack_dup_value(&a->data[i], &n->data[i]); 306 return (n); 307} 308 309static __inline void 310array_grow(struct array *array, size_t newsize) 311{ 312 size_t i; 313 314 array->data = breallocarray(array->data, newsize, sizeof(*array->data)); 315 for (i = array->size; i < newsize; i++) { 316 array->data[i].type = BCODE_NONE; 317 array->data[i].array = NULL; 318 } 319 array->size = newsize; 320} 321 322static __inline void 323array_assign(struct array *array, size_t i, const struct value *v) 324{ 325 326 if (i >= array->size) 327 array_grow(array, i + 1); 328 stack_free_value(&array->data[i]); 329 array->data[i] = *v; 330} 331 332static __inline struct value * 333array_retrieve(const struct array *array, size_t i) 334{ 335 336 if (i >= array->size) 337 return (NULL); 338 return &array->data[i]; 339} 340 341void 342frame_assign(struct stack *stack, size_t i, const struct value *v) 343{ 344 struct array *a; 345 struct value n; 346 347 if (stack->sp == -1) { 348 n.type = BCODE_NONE; 349 n.array = NULL; 350 stack_push(stack, &n); 351 } 352 353 a = stack->stack[stack->sp].array; 354 if (a == NULL) 355 a = stack->stack[stack->sp].array = array_new(); 356 array_assign(a, i, v); 357} 358 359struct value * 360frame_retrieve(const struct stack *stack, size_t i) 361{ 362 struct array *a; 363 364 if (stack->sp == -1) 365 return (NULL); 366 a = stack->stack[stack->sp].array; 367 if (a == NULL) 368 a = stack->stack[stack->sp].array = array_new(); 369 return array_retrieve(a, i); 370} 371