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