usr.bin/dc/stack.c

   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, &copy));
 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 }