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