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 26 static __inline bool stack_empty(const struct stack *); 27 static void stack_grow(struct stack *); 28 static struct array *array_new(void); 29 static __inline void array_free(struct array *); 30 static struct array *array_dup(const struct array *); 31 static __inline void array_grow(struct array *, size_t); 32 static __inline void array_assign(struct array *, size_t, const struct value *); 33 static __inline struct value *array_retrieve(const struct array *, size_t); 34 35 void 36 stack_init(struct stack *stack) 37 { 38 39 stack->size = 0; 40 stack->sp = -1; 41 stack->stack = NULL; 42 } 43 44 static __inline bool 45 stack_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 */ 55 void 56 stack_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 */ 74 struct value * 75 stack_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 98 size_t 99 stack_size(const struct stack *stack) 100 { 101 102 return (stack->sp + 1); 103 } 104 105 void 106 stack_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 119 void 120 stack_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 133 static void 134 stack_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 146 void 147 stack_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 156 void 157 stack_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 166 void 167 stack_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 186 struct value * 187 stack_tos(const struct stack *stack) 188 { 189 190 if (stack->sp == -1) 191 return (NULL); 192 return &stack->stack[stack->sp]; 193 } 194 195 void 196 stack_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 209 struct value * 210 stack_pop(struct stack *stack) 211 { 212 213 if (stack_empty(stack)) 214 return (NULL); 215 return &stack->stack[stack->sp--]; 216 } 217 218 struct number * 219 stack_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 233 char * 234 stack_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 248 void 249 stack_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 258 void 259 stack_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 270 static struct array * 271 array_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 281 static __inline void 282 array_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 294 static struct array * 295 array_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 309 static __inline void 310 array_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 322 static __inline void 323 array_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 332 static __inline struct value * 333 array_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 341 void 342 frame_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 359 struct value * 360 frame_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