1 /* $NetBSD: stack.c,v 1.2 2017/04/10 16:37:48 christos Exp $ */ 2 /* $OpenBSD: stack.c,v 1.14 2016/03/27 15:55:13 otto Exp $ */ 3 4 /* 5 * Copyright (c) 2003, Otto Moerbeek <otto@drijf.net> 6 * 7 * Permission to use, copy, modify, and distribute this software for any 8 * purpose with or without fee is hereby granted, provided that the above 9 * copyright notice and this permission notice appear in all copies. 10 * 11 * THE SOFTWARE IS PROVIDED "AS IS" AND THE AUTHOR DISCLAIMS ALL WARRANTIES 12 * WITH REGARD TO THIS SOFTWARE INCLUDING ALL IMPLIED WARRANTIES OF 13 * MERCHANTABILITY AND FITNESS. IN NO EVENT SHALL THE AUTHOR BE LIABLE FOR 14 * ANY SPECIAL, DIRECT, INDIRECT, OR CONSEQUENTIAL DAMAGES OR ANY DAMAGES 15 * WHATSOEVER RESULTING FROM LOSS OF USE, DATA OR PROFITS, WHETHER IN AN 16 * ACTION OF CONTRACT, NEGLIGENCE OR OTHER TORTIOUS ACTION, ARISING OUT OF 17 * OR IN CONNECTION WITH THE USE OR PERFORMANCE OF THIS SOFTWARE. 18 */ 19 #include <sys/cdefs.h> 20 __RCSID("$NetBSD: stack.c,v 1.2 2017/04/10 16:37:48 christos Exp $"); 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 stack->size = 0; 41 stack->sp = -1; 42 stack->stack = NULL; 43 } 44 45 static __inline bool 46 stack_empty(const struct stack *stack) 47 { 48 bool empty = stack->sp == -1; 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 switch (v->type) { 59 case BCODE_NONE: 60 break; 61 case BCODE_NUMBER: 62 free_number(v->u.num); 63 break; 64 case BCODE_STRING: 65 free(v->u.string); 66 break; 67 } 68 array_free(v->array); 69 v->array = NULL; 70 } 71 72 /* Copy number or string content into already allocated target */ 73 struct value * 74 stack_dup_value(const struct value *a, struct value *copy) 75 { 76 copy->type = a->type; 77 78 switch (a->type) { 79 case BCODE_NONE: 80 break; 81 case BCODE_NUMBER: 82 copy->u.num = dup_number(a->u.num); 83 break; 84 case BCODE_STRING: 85 copy->u.string = strdup(a->u.string); 86 if (copy->u.string == NULL) 87 err(1, NULL); 88 break; 89 } 90 91 copy->array = a->array == NULL ? NULL : array_dup(a->array); 92 93 return copy; 94 } 95 96 size_t 97 stack_size(const struct stack *stack) 98 { 99 return (size_t)(stack->sp + 1); 100 } 101 102 void 103 stack_dup(struct stack *stack) 104 { 105 struct value *value; 106 struct value copy; 107 108 value = stack_tos(stack); 109 if (value == NULL) { 110 warnx("stack empty"); 111 return; 112 } 113 stack_push(stack, stack_dup_value(value, ©)); 114 } 115 116 void 117 stack_swap(struct stack *stack) 118 { 119 struct value copy; 120 121 if (stack->sp < 1) { 122 warnx("stack empty"); 123 return; 124 } 125 copy = stack->stack[stack->sp]; 126 stack->stack[stack->sp] = stack->stack[stack->sp-1]; 127 stack->stack[stack->sp-1] = copy; 128 } 129 130 static void 131 stack_grow(struct stack *stack) 132 { 133 size_t new_size; 134 135 if ((size_t)++stack->sp == stack->size) { 136 new_size = stack->size * 2 + 1; 137 stack->stack = breallocarray(stack->stack, 138 new_size, sizeof(*stack->stack)); 139 stack->size = new_size; 140 } 141 } 142 143 void 144 stack_pushnumber(struct stack *stack, struct number *b) 145 { 146 stack_grow(stack); 147 stack->stack[stack->sp].type = BCODE_NUMBER; 148 stack->stack[stack->sp].u.num = b; 149 stack->stack[stack->sp].array = NULL; 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 stack->stack[stack->sp].array = NULL; 159 } 160 161 void 162 stack_push(struct stack *stack, struct value *v) 163 { 164 switch (v->type) { 165 case BCODE_NONE: 166 stack_grow(stack); 167 stack->stack[stack->sp].type = BCODE_NONE; 168 break; 169 case BCODE_NUMBER: 170 stack_pushnumber(stack, v->u.num); 171 break; 172 case BCODE_STRING: 173 stack_pushstring(stack, v->u.string); 174 break; 175 } 176 stack->stack[stack->sp].array = v->array == NULL ? 177 NULL : array_dup(v->array); 178 } 179 180 struct value * 181 stack_tos(const struct stack *stack) 182 { 183 if (stack->sp == -1) 184 return NULL; 185 return &stack->stack[stack->sp]; 186 } 187 188 void 189 stack_set_tos(struct stack *stack, struct value *v) 190 { 191 if (stack->sp == -1) 192 stack_push(stack, v); 193 else { 194 stack_free_value(&stack->stack[stack->sp]); 195 stack->stack[stack->sp] = *v; 196 stack->stack[stack->sp].array = v->array == NULL ? 197 NULL : array_dup(v->array); 198 } 199 } 200 201 struct value * 202 stack_pop(struct stack *stack) 203 { 204 if (stack_empty(stack)) 205 return NULL; 206 return &stack->stack[stack->sp--]; 207 } 208 209 struct number * 210 stack_popnumber(struct stack *stack) 211 { 212 if (stack_empty(stack)) 213 return NULL; 214 array_free(stack->stack[stack->sp].array); 215 stack->stack[stack->sp].array = NULL; 216 if (stack->stack[stack->sp].type != BCODE_NUMBER) { 217 warnx("not a number"); /* XXX remove */ 218 return NULL; 219 } 220 return stack->stack[stack->sp--].u.num; 221 } 222 223 char * 224 stack_popstring(struct stack *stack) 225 { 226 if (stack_empty(stack)) 227 return NULL; 228 array_free(stack->stack[stack->sp].array); 229 stack->stack[stack->sp].array = NULL; 230 if (stack->stack[stack->sp].type != BCODE_STRING) { 231 warnx("not a string"); /* XXX remove */ 232 return NULL; 233 } 234 return stack->stack[stack->sp--].u.string; 235 } 236 237 void 238 stack_clear(struct stack *stack) 239 { 240 while (stack->sp >= 0) 241 stack_free_value(&stack->stack[stack->sp--]); 242 free(stack->stack); 243 stack_init(stack); 244 } 245 246 void 247 stack_print(FILE *f, const struct stack *stack, const char *prefix, u_int base) 248 { 249 ssize_t i; 250 251 for (i = stack->sp; i >= 0; i--) { 252 print_value(f, &stack->stack[i], prefix, base); 253 (void)putc('\n', f); 254 } 255 } 256 257 258 static struct array * 259 array_new(void) 260 { 261 struct array *a; 262 263 a = bmalloc(sizeof(*a)); 264 a->data = NULL; 265 a->size = 0; 266 return a; 267 } 268 269 static __inline void 270 array_free(struct array *a) 271 { 272 size_t i; 273 274 if (a == NULL) 275 return; 276 for (i = 0; i < a->size; i++) 277 stack_free_value(&a->data[i]); 278 free(a->data); 279 free(a); 280 } 281 282 static struct array * 283 array_dup(const struct array *a) 284 { 285 struct array *n; 286 size_t i; 287 288 if (a == NULL) 289 return NULL; 290 n = array_new(); 291 array_grow(n, a->size); 292 for (i = 0; i < a->size; i++) 293 (void)stack_dup_value(&a->data[i], &n->data[i]); 294 return n; 295 } 296 297 static __inline void 298 array_grow(struct array *array, size_t newsize) 299 { 300 size_t i; 301 302 array->data = breallocarray(array->data, newsize, sizeof(*array->data)); 303 for (i = array->size; i < newsize; i++) { 304 array->data[i].type = BCODE_NONE; 305 array->data[i].array = NULL; 306 } 307 array->size = newsize; 308 } 309 310 static __inline void 311 array_assign(struct array *array, size_t index, const struct value *v) 312 { 313 if (index >= array->size) 314 array_grow(array, index+1); 315 stack_free_value(&array->data[index]); 316 array->data[index] = *v; 317 } 318 319 static __inline struct value * 320 array_retrieve(const struct array *array, size_t index) 321 { 322 if (index >= array->size) 323 return NULL; 324 return &array->data[index]; 325 } 326 327 void 328 frame_assign(struct stack *stack, size_t index, const struct value *v) 329 { 330 struct array *a; 331 struct value n; 332 333 if (stack->sp == -1) { 334 n.type = BCODE_NONE; 335 n.array = NULL; 336 stack_push(stack, &n); 337 } 338 339 a = stack->stack[stack->sp].array; 340 if (a == NULL) 341 a = stack->stack[stack->sp].array = array_new(); 342 array_assign(a, index, v); 343 } 344 345 struct value * 346 frame_retrieve(const struct stack *stack, size_t index) 347 { 348 struct array *a; 349 350 if (stack->sp == -1) 351 return NULL; 352 a = stack->stack[stack->sp].array; 353 if (a == NULL) 354 a = stack->stack[stack->sp].array = array_new(); 355 return array_retrieve(a, index); 356 } 357