usr.bin/dc/stack.c

   1 /*      $OpenBSD: stack.c,v 1.13 2014/12/01 13:13:00 deraadt 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 <sys/cdefs.h>
  20 #include <err.h>
  21 #include <stdlib.h>
  22 #include <string.h>
  23
  24 #include "extern.h"
  25
  26 static __inline bool     stack_empty(const struct stack *);
  27 static void              stack_grow(struct stack *);
  28 static struct array     *array_new(void);
  29 static __inline void     array_free(struct array *);
  30 static struct array     *array_dup(const struct array *);
  31 static __inline void     array_grow(struct array *, size_t);
  32 static __inline void     array_assign(struct array *, size_t, const struct value *);
  33 static __inline struct value    *array_retrieve(const struct array *, size_t);
  34
  35 void
  36 stack_init(struct stack *stack)
  37 {
  38
  39         stack->size = 0;
  40         stack->sp = -1;
  41         stack->stack = NULL;
  42 }
  43
  44 static __inline bool
  45 stack_empty(const struct stack *stack)
  46 {
  47         bool empty = stack->sp == -1;
  48
  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
  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         array_free(v->array);
  70         v->array = NULL;
  71 }
  72
  73 /* Copy number or string content into already allocated target */
  74 struct value *
  75 stack_dup_value(const struct value *a, struct value *copy)
  76 {
  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
 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, &copy));
 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;
 137
 138         if (++stack->sp == stack->size) {
 139                 new_size = stack->size * 2 + 1;
 140                 stack->stack = breallocarray(stack->stack,
 141                     new_size, sizeof(*stack->stack));
 142                 stack->size = new_size;
 143         }
 144 }
 145
 146 void
 147 stack_pushnumber(struct stack *stack, struct number *b)
 148 {
 149
 150         stack_grow(stack);
 151         stack->stack[stack->sp].type = BCODE_NUMBER;
 152         stack->stack[stack->sp].u.num = b;
 153         stack->stack[stack->sp].array = NULL;
 154 }
 155
 156 void
 157 stack_pushstring(struct stack *stack, char *string)
 158 {
 159
 160         stack_grow(stack);
 161         stack->stack[stack->sp].type = BCODE_STRING;
 162         stack->stack[stack->sp].u.string = string;
 163         stack->stack[stack->sp].array = NULL;
 164 }
 165
 166 void
 167 stack_push(struct stack *stack, struct value *v)
 168 {
 169
 170         switch (v->type) {
 171         case BCODE_NONE:
 172                 stack_grow(stack);
 173                 stack->stack[stack->sp].type = BCODE_NONE;
 174                 break;
 175         case BCODE_NUMBER:
 176                 stack_pushnumber(stack, v->u.num);
 177                 break;
 178         case BCODE_STRING:
 179                 stack_pushstring(stack, v->u.string);
 180                 break;
 181         }
 182         stack->stack[stack->sp].array = v->array == NULL ?
 183             NULL : array_dup(v->array);
 184 }
 185
 186 struct value *
 187 stack_tos(const struct stack *stack)
 188 {
 189
 190         if (stack->sp == -1)
 191                 return (NULL);
 192         return &stack->stack[stack->sp];
 193 }
 194
 195 void
 196 stack_set_tos(struct stack *stack, struct value *v)
 197 {
 198
 199         if (stack->sp == -1)
 200                 stack_push(stack, v);
 201         else {
 202                 stack_free_value(&stack->stack[stack->sp]);
 203                 stack->stack[stack->sp] = *v;
 204                 stack->stack[stack->sp].array = v->array == NULL ?
 205                     NULL : array_dup(v->array);
 206         }
 207 }
 208
 209 struct value *
 210 stack_pop(struct stack *stack)
 211 {
 212
 213         if (stack_empty(stack))
 214                 return (NULL);
 215         return &stack->stack[stack->sp--];
 216 }
 217
 218 struct number *
 219 stack_popnumber(struct stack *stack)
 220 {
 221
 222         if (stack_empty(stack))
 223                 return (NULL);
 224         array_free(stack->stack[stack->sp].array);
 225         stack->stack[stack->sp].array = NULL;
 226         if (stack->stack[stack->sp].type != BCODE_NUMBER) {
 227                 warnx("not a number"); /* XXX remove */
 228                 return (NULL);
 229         }
 230         return stack->stack[stack->sp--].u.num;
 231 }
 232
 233 char *
 234 stack_popstring(struct stack *stack)
 235 {
 236
 237         if (stack_empty(stack))
 238                 return (NULL);
 239         array_free(stack->stack[stack->sp].array);
 240         stack->stack[stack->sp].array = NULL;
 241         if (stack->stack[stack->sp].type != BCODE_STRING) {
 242                 warnx("not a string"); /* XXX remove */
 243                 return (NULL);
 244         }
 245         return stack->stack[stack->sp--].u.string;
 246 }
 247
 248 void
 249 stack_clear(struct stack *stack)
 250 {
 251
 252         while (stack->sp >= 0)
 253                 stack_free_value(&stack->stack[stack->sp--]);
 254         free(stack->stack);
 255         stack_init(stack);
 256 }
 257
 258 void
 259 stack_print(FILE *f, const struct stack *stack, const char *prefix, u_int base)
 260 {
 261         ssize_t i;
 262
 263         for (i = stack->sp; i >= 0; i--) {
 264                 print_value(f, &stack->stack[i], prefix, base);
 265                 putc('\n', f);
 266         }
 267 }
 268
 269
 270 static struct array *
 271 array_new(void)
 272 {
 273         struct array *a;
 274
 275         a = bmalloc(sizeof(*a));
 276         a->data = NULL;
 277         a->size = 0;
 278         return a;
 279 }
 280
 281 static __inline void
 282 array_free(struct array *a)
 283 {
 284         size_t i;
 285
 286         if (a == NULL)
 287                 return;
 288         for (i = 0; i < a->size; i++)
 289                 stack_free_value(&a->data[i]);
 290         free(a->data);
 291         free(a);
 292 }
 293
 294 static struct array *
 295 array_dup(const struct array *a)
 296 {
 297         struct array *n;
 298         size_t i;
 299
 300         if (a == NULL)
 301                 return (NULL);
 302         n = array_new();
 303         array_grow(n, a->size);
 304         for (i = 0; i < a->size; i++)
 305                 stack_dup_value(&a->data[i], &n->data[i]);
 306         return (n);
 307 }
 308
 309 static __inline void
 310 array_grow(struct array *array, size_t newsize)
 311 {
 312         size_t i;
 313
 314         array->data = breallocarray(array->data, newsize, sizeof(*array->data));
 315         for (i = array->size; i < newsize; i++) {
 316                 array->data[i].type = BCODE_NONE;
 317                 array->data[i].array = NULL;
 318         }
 319         array->size = newsize;
 320 }
 321
 322 static __inline void
 323 array_assign(struct array *array, size_t i, const struct value *v)
 324 {
 325
 326         if (i >= array->size)
 327                 array_grow(array, i + 1);
 328         stack_free_value(&array->data[i]);
 329         array->data[i] = *v;
 330 }
 331
 332 static __inline struct value *
 333 array_retrieve(const struct array *array, size_t i)
 334 {
 335
 336         if (i >= array->size)
 337                 return (NULL);
 338         return &array->data[i];
 339 }
 340
 341 void
 342 frame_assign(struct stack *stack, size_t i, const struct value *v)
 343 {
 344         struct array *a;
 345         struct value n;
 346
 347         if (stack->sp == -1) {
 348                 n.type = BCODE_NONE;
 349                 n.array = NULL;
 350                 stack_push(stack, &n);
 351         }
 352
 353         a = stack->stack[stack->sp].array;
 354         if (a == NULL)
 355                 a = stack->stack[stack->sp].array = array_new();
 356         array_assign(a, i, v);
 357 }
 358
 359 struct value *
 360 frame_retrieve(const struct stack *stack, size_t i)
 361 {
 362         struct array *a;
 363
 364         if (stack->sp == -1)
 365                 return (NULL);
 366         a = stack->stack[stack->sp].array;
 367         if (a == NULL)
 368                 a = stack->stack[stack->sp].array = array_new();
 369         return array_retrieve(a, i);
 370 }