usr.bin/dc/stack.c

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