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