fatbase

portable OpenBSD tools
git clone git://git.2f30.org/fatbase
Log | Files | Refs

stack.c (7575B)

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