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