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