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