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 __FBSDID("$FreeBSD$"); 21 22 #include <err.h> 23 #include <stdlib.h> 24 #include <string.h> 25 26 #include "extern.h" 27 28 static __inline bool stack_empty(const struct stack *); 29 static void stack_grow(struct stack *); 30 static struct array *array_new(void); 31 static __inline void array_free(struct array *); 32 static struct array *array_dup(const struct array *); 33 static __inline void array_grow(struct array *, size_t); 34 static __inline void array_assign(struct array *, size_t, const struct value *); 35 static __inline struct value *array_retrieve(const struct array *, size_t); 36 37 void 38 stack_init(struct stack *stack) 39 { 40 41 stack->size = 0; 42 stack->sp = -1; 43 stack->stack = NULL; 44 } 45 46 static __inline bool 47 stack_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 */ 57 void 58 stack_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 */ 76 struct value * 77 stack_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 100 size_t 101 stack_size(const struct stack *stack) 102 { 103 104 return (stack->sp + 1); 105 } 106 107 void 108 stack_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 121 void 122 stack_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 135 static void 136 stack_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 = breallocarray(stack->stack, 143 new_size, sizeof(*stack->stack)); 144 stack->size = new_size; 145 } 146 } 147 148 void 149 stack_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 158 void 159 stack_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 168 void 169 stack_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 188 struct value * 189 stack_tos(const struct stack *stack) 190 { 191 192 if (stack->sp == -1) 193 return (NULL); 194 return &stack->stack[stack->sp]; 195 } 196 197 void 198 stack_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 211 struct value * 212 stack_pop(struct stack *stack) 213 { 214 215 if (stack_empty(stack)) 216 return (NULL); 217 return &stack->stack[stack->sp--]; 218 } 219 220 struct number * 221 stack_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 235 char * 236 stack_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 250 void 251 stack_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 260 void 261 stack_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 272 static struct array * 273 array_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 283 static __inline void 284 array_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 296 static struct array * 297 array_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 311 static __inline void 312 array_grow(struct array *array, size_t newsize) 313 { 314 size_t i; 315 316 array->data = breallocarray(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 324 static __inline void 325 array_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 334 static __inline struct value * 335 array_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 343 void 344 frame_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 361 struct value * 362 frame_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