Return to stack.c CVS log

Up to [local] / src / usr.bin / dc

rcsid[] and sccsid[] and copyright[] are essentially unmaintained (and
unmaintainable).  these days, people use source.  these id's do not provide
any benefit, and do hurt the small install media
(the 33,000 line diff is essentially mechanical)
ok with the idea millert, ok dms

/*	$OpenBSD: stack.c,v 1.11 2009/10/27 23:59:37 deraadt Exp $	*/

/*
 * Copyright (c) 2003, Otto Moerbeek <otto@drijf.net>
 *
 * Permission to use, copy, modify, and distribute this software for any
 * purpose with or without fee is hereby granted, provided that the above
 * copyright notice and this permission notice appear in all copies.
 *
 * THE SOFTWARE IS PROVIDED "AS IS" AND THE AUTHOR DISCLAIMS ALL WARRANTIES
 * WITH REGARD TO THIS SOFTWARE INCLUDING ALL IMPLIED WARRANTIES OF
 * MERCHANTABILITY AND FITNESS. IN NO EVENT SHALL THE AUTHOR BE LIABLE FOR
 * ANY SPECIAL, DIRECT, INDIRECT, OR CONSEQUENTIAL DAMAGES OR ANY DAMAGES
 * WHATSOEVER RESULTING FROM LOSS OF USE, DATA OR PROFITS, WHETHER IN AN
 * ACTION OF CONTRACT, NEGLIGENCE OR OTHER TORTIOUS ACTION, ARISING OUT OF
 * OR IN CONNECTION WITH THE USE OR PERFORMANCE OF THIS SOFTWARE.
 */

#include <err.h>
#include <stdlib.h>
#include <string.h>

#include "extern.h"

static __inline bool	stack_empty(const struct stack *);
static void		stack_grow(struct stack *);
static struct array	*array_new(void);
static __inline void	array_free(struct array *);
static struct array *	array_dup(const struct array *);
static __inline void	array_grow(struct array *, size_t);
static __inline void	array_assign(struct array *, size_t, const struct value *);
static __inline struct value	*array_retrieve(const struct array *, size_t);

void
stack_init(struct stack *stack)
{
	stack->size = 0;
	stack->sp = -1;
	stack->stack = NULL;
}

static __inline bool
stack_empty(const struct stack *stack)
{
	bool empty = stack->sp == -1;
	if (empty)
		warnx("stack empty");
	return empty;
}

/* Clear number or string, but leave value itself */
void
stack_free_value(struct value *v)
{
	switch (v->type) {
	case BCODE_NONE:
		break;
	case BCODE_NUMBER:
		free_number(v->u.num);
		break;
	case BCODE_STRING:
		free(v->u.string);
		break;
	}
	if (v->array != NULL) {
		array_free(v->array);
		v->array = NULL;
	}
}

/* Copy number or string content into already allocated target */
struct value *
stack_dup_value(const struct value *a, struct value *copy)
{
	copy->type = a->type;

	switch (a->type) {
	case BCODE_NONE:
		break;
	case BCODE_NUMBER:
		copy->u.num = dup_number(a->u.num);
		break;
	case BCODE_STRING:
		copy->u.string = strdup(a->u.string);
		if (copy->u.string == NULL)
			err(1, NULL);
		break;
	}

	copy->array = a->array == NULL ? NULL : array_dup(a->array);

	return copy;
}

size_t
stack_size(const struct stack *stack)
{
	return stack->sp + 1;
}

void
stack_dup(struct stack *stack)
{
	struct value	*value;
	struct value	copy;

	value = stack_tos(stack);
	if (value == NULL) {
		warnx("stack empty");
		return;
	}
	stack_push(stack, stack_dup_value(value, &copy));
}

void
stack_swap(struct stack *stack)
{
	struct value	copy;

	if (stack->sp < 1) {
		warnx("stack empty");
		return;
	}
	copy = stack->stack[stack->sp];
	stack->stack[stack->sp] = stack->stack[stack->sp-1];
	stack->stack[stack->sp-1] = copy;
}

static void
stack_grow(struct stack *stack)
{
	size_t new_size, i;

	if (++stack->sp == stack->size) {
		new_size = stack->size * 2 + 1;
		stack->stack = brealloc(stack->stack,
		    new_size * sizeof(*stack->stack));
		for (i = stack->size; i < new_size; i++)
			stack->stack[i].array = NULL;
		stack->size = new_size;
	}
}

void
stack_pushnumber(struct stack *stack, struct number *b)
{
	stack_grow(stack);
	stack->stack[stack->sp].type = BCODE_NUMBER;
	stack->stack[stack->sp].u.num = b;
}

void
stack_pushstring(struct stack *stack, char *string)
{
	stack_grow(stack);
	stack->stack[stack->sp].type = BCODE_STRING;
	stack->stack[stack->sp].u.string = string;
}

void
stack_push(struct stack *stack, struct value *v)
{
	switch (v->type) {
	case BCODE_NONE:
		stack_grow(stack);
		stack->stack[stack->sp].type = BCODE_NONE;
		break;
	case BCODE_NUMBER:
		stack_pushnumber(stack, v->u.num);
		break;
	case BCODE_STRING:
		stack_pushstring(stack, v->u.string);
		break;
	}
	stack->stack[stack->sp].array = v->array == NULL ?
	    NULL : array_dup(v->array);
}

struct value *
stack_tos(const struct stack *stack)
{
	if (stack->sp == -1)
		return NULL;
	return &stack->stack[stack->sp];
}

void
stack_set_tos(struct stack *stack, struct value *v)
{
	if (stack->sp == -1)
		stack_push(stack, v);
	else {
		stack_free_value(&stack->stack[stack->sp]);
		stack->stack[stack->sp] = *v;
		stack->stack[stack->sp].array = v->array == NULL ?
		    NULL : array_dup(v->array);
	}
}

struct value *
stack_pop(struct stack *stack)
{
	if (stack_empty(stack))
		return NULL;
	return &stack->stack[stack->sp--];
}

struct number *
stack_popnumber(struct stack *stack)
{
	if (stack_empty(stack))
		return NULL;
	if (stack->stack[stack->sp].array != NULL) {
		array_free(stack->stack[stack->sp].array);
		stack->stack[stack->sp].array = NULL;
	}
	if (stack->stack[stack->sp].type != BCODE_NUMBER) {
		warnx("not a number"); /* XXX remove */
		return NULL;
	}
	return stack->stack[stack->sp--].u.num;
}

char *
stack_popstring(struct stack *stack)
{
	if (stack_empty(stack))
		return NULL;
	if (stack->stack[stack->sp].array != NULL) {
		array_free(stack->stack[stack->sp].array);
		stack->stack[stack->sp].array = NULL;
	}
	if (stack->stack[stack->sp].type != BCODE_STRING) {
		warnx("not a string"); /* XXX remove */
		return NULL;
	}
	return stack->stack[stack->sp--].u.string;
}

void
stack_clear(struct stack *stack)
{
	while (stack->sp >= 0) {
		stack_free_value(&stack->stack[stack->sp--]);
	}
	free(stack->stack);
	stack_init(stack);
}

void
stack_print(FILE *f, const struct stack *stack, const char *prefix, u_int base)
{
	ssize_t i;

	for (i = stack->sp; i >= 0; i--) {
		print_value(f, &stack->stack[i], prefix, base);
		(void)putc('\n', f);
	}
}


static struct array *
array_new(void)
{
	struct array *a;

	a = bmalloc(sizeof(*a));
	a->data = NULL;
	a->size = 0;
	return a;
}

static __inline void
array_free(struct array *a)
{
	size_t i;

	if (a == NULL)
		return;
	for (i = 0; i < a->size; i++)
		stack_free_value(&a->data[i]);
	free(a->data);
	free(a);
}

static struct array *
array_dup(const struct array *a)
{
	struct array	*n;
	size_t		i;

	if (a == NULL)
		return NULL;
	n = array_new();
	array_grow(n, a->size);
	for (i = 0; i < a->size; i++)
		(void)stack_dup_value(&a->data[i], &n->data[i]);
	return n;
}

static __inline void
array_grow(struct array *array, size_t newsize)
{
	size_t i;

	array->data = brealloc(array->data, newsize * sizeof(*array->data));
	for (i = array->size; i < newsize; i++) {
		array->data[i].type = BCODE_NONE;
		array->data[i].array = NULL;
	}
	array->size = newsize;
}

static __inline void
array_assign(struct array *array, size_t index, const struct value *v)
{
	if (index >= array->size)
		array_grow(array, index+1);
	stack_free_value(&array->data[index]);
	array->data[index] = *v;
}

static __inline struct value *
array_retrieve(const struct array *array, size_t index)
{
	if (index >= array->size)
		return NULL;
	return &array->data[index];
}

void
frame_assign(struct stack *stack, size_t index, const struct value *v)
{
	struct array *a;
	struct value n;

	if (stack->sp == -1) {
		n.type = BCODE_NONE;
		n.array = NULL;
		stack_push(stack, &n);
	}

	a = stack->stack[stack->sp].array;
	if (a == NULL)
		a = stack->stack[stack->sp].array = array_new();
	array_assign(a, index, v);
}

struct value *
frame_retrieve(const struct stack *stack, size_t index)
{
	struct array *a;

	if (stack->sp == -1)
		return NULL;
	a = stack->stack[stack->sp].array;
	if (a == NULL)
		a = stack->stack[stack->sp].array = array_new();
	return array_retrieve(a, index);
}