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