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