da2e3ebdc1edfbc5028edf1354e7dd2fa69a7968chin/***********************************************************************
da2e3ebdc1edfbc5028edf1354e7dd2fa69a7968chin* *
da2e3ebdc1edfbc5028edf1354e7dd2fa69a7968chin* This software is part of the ast package *
3e14f97f673e8a630f076077de35afdd43dc1587Roger A. Faulkner* Copyright (c) 1985-2010 AT&T Intellectual Property *
da2e3ebdc1edfbc5028edf1354e7dd2fa69a7968chin* and is licensed under the *
da2e3ebdc1edfbc5028edf1354e7dd2fa69a7968chin* Common Public License, Version 1.0 *
7c2fbfb345896881c631598ee3852ce9ce33fb07April Chin* by AT&T Intellectual Property *
da2e3ebdc1edfbc5028edf1354e7dd2fa69a7968chin* *
da2e3ebdc1edfbc5028edf1354e7dd2fa69a7968chin* A copy of the License is available at *
da2e3ebdc1edfbc5028edf1354e7dd2fa69a7968chin* http://www.opensource.org/licenses/cpl1.0.txt *
da2e3ebdc1edfbc5028edf1354e7dd2fa69a7968chin* (with md5 checksum 059e8cd6165cb4c31e351f2b69388fd9) *
da2e3ebdc1edfbc5028edf1354e7dd2fa69a7968chin* *
da2e3ebdc1edfbc5028edf1354e7dd2fa69a7968chin* Information and Software Systems Research *
da2e3ebdc1edfbc5028edf1354e7dd2fa69a7968chin* AT&T Research *
da2e3ebdc1edfbc5028edf1354e7dd2fa69a7968chin* Florham Park NJ *
da2e3ebdc1edfbc5028edf1354e7dd2fa69a7968chin* *
da2e3ebdc1edfbc5028edf1354e7dd2fa69a7968chin* Glenn Fowler <gsf@research.att.com> *
da2e3ebdc1edfbc5028edf1354e7dd2fa69a7968chin* David Korn <dgk@research.att.com> *
da2e3ebdc1edfbc5028edf1354e7dd2fa69a7968chin* Phong Vo <kpv@research.att.com> *
da2e3ebdc1edfbc5028edf1354e7dd2fa69a7968chin* *
da2e3ebdc1edfbc5028edf1354e7dd2fa69a7968chin***********************************************************************/
da2e3ebdc1edfbc5028edf1354e7dd2fa69a7968chin#pragma prototyped
da2e3ebdc1edfbc5028edf1354e7dd2fa69a7968chin/*
da2e3ebdc1edfbc5028edf1354e7dd2fa69a7968chin * pointer stack routines
da2e3ebdc1edfbc5028edf1354e7dd2fa69a7968chin */
da2e3ebdc1edfbc5028edf1354e7dd2fa69a7968chin
da2e3ebdc1edfbc5028edf1354e7dd2fa69a7968chinstatic const char id_stack[] = "\n@(#)$Id: stack (AT&T Bell Laboratories) 1984-05-01 $\0\n";
da2e3ebdc1edfbc5028edf1354e7dd2fa69a7968chin
da2e3ebdc1edfbc5028edf1354e7dd2fa69a7968chin#include <ast.h>
da2e3ebdc1edfbc5028edf1354e7dd2fa69a7968chin#include <stack.h>
da2e3ebdc1edfbc5028edf1354e7dd2fa69a7968chin
da2e3ebdc1edfbc5028edf1354e7dd2fa69a7968chin/*
da2e3ebdc1edfbc5028edf1354e7dd2fa69a7968chin * create a new stack
da2e3ebdc1edfbc5028edf1354e7dd2fa69a7968chin */
da2e3ebdc1edfbc5028edf1354e7dd2fa69a7968chin
da2e3ebdc1edfbc5028edf1354e7dd2fa69a7968chinSTACK
da2e3ebdc1edfbc5028edf1354e7dd2fa69a7968chinstackalloc(register int size, void* error)
da2e3ebdc1edfbc5028edf1354e7dd2fa69a7968chin{
da2e3ebdc1edfbc5028edf1354e7dd2fa69a7968chin register STACK stack;
da2e3ebdc1edfbc5028edf1354e7dd2fa69a7968chin register struct stackblock *b;
da2e3ebdc1edfbc5028edf1354e7dd2fa69a7968chin
da2e3ebdc1edfbc5028edf1354e7dd2fa69a7968chin if (size <= 0) size = 100;
da2e3ebdc1edfbc5028edf1354e7dd2fa69a7968chin if (!(stack = newof(0, struct stacktable, 1, 0))) return(0);
da2e3ebdc1edfbc5028edf1354e7dd2fa69a7968chin if (!(b = newof(0, struct stackblock, 1, 0)))
da2e3ebdc1edfbc5028edf1354e7dd2fa69a7968chin {
da2e3ebdc1edfbc5028edf1354e7dd2fa69a7968chin free(stack);
da2e3ebdc1edfbc5028edf1354e7dd2fa69a7968chin return(0);
da2e3ebdc1edfbc5028edf1354e7dd2fa69a7968chin }
da2e3ebdc1edfbc5028edf1354e7dd2fa69a7968chin if (!(b->stack = newof(0, void*, size, 0)))
da2e3ebdc1edfbc5028edf1354e7dd2fa69a7968chin {
da2e3ebdc1edfbc5028edf1354e7dd2fa69a7968chin free(b);
da2e3ebdc1edfbc5028edf1354e7dd2fa69a7968chin free(stack);
da2e3ebdc1edfbc5028edf1354e7dd2fa69a7968chin return(0);
da2e3ebdc1edfbc5028edf1354e7dd2fa69a7968chin }
da2e3ebdc1edfbc5028edf1354e7dd2fa69a7968chin stack->blocks = b;
da2e3ebdc1edfbc5028edf1354e7dd2fa69a7968chin stack->size = size;
da2e3ebdc1edfbc5028edf1354e7dd2fa69a7968chin stack->error = error;
da2e3ebdc1edfbc5028edf1354e7dd2fa69a7968chin stack->position.block = b;
da2e3ebdc1edfbc5028edf1354e7dd2fa69a7968chin stack->position.index = -1;
da2e3ebdc1edfbc5028edf1354e7dd2fa69a7968chin b->next = 0;
da2e3ebdc1edfbc5028edf1354e7dd2fa69a7968chin b->prev = 0;
da2e3ebdc1edfbc5028edf1354e7dd2fa69a7968chin return(stack);
da2e3ebdc1edfbc5028edf1354e7dd2fa69a7968chin}
da2e3ebdc1edfbc5028edf1354e7dd2fa69a7968chin
da2e3ebdc1edfbc5028edf1354e7dd2fa69a7968chin/*
da2e3ebdc1edfbc5028edf1354e7dd2fa69a7968chin * remove a stack
da2e3ebdc1edfbc5028edf1354e7dd2fa69a7968chin */
da2e3ebdc1edfbc5028edf1354e7dd2fa69a7968chin
da2e3ebdc1edfbc5028edf1354e7dd2fa69a7968chinvoid
da2e3ebdc1edfbc5028edf1354e7dd2fa69a7968chinstackfree(register STACK stack)
da2e3ebdc1edfbc5028edf1354e7dd2fa69a7968chin{
da2e3ebdc1edfbc5028edf1354e7dd2fa69a7968chin register struct stackblock* b;
da2e3ebdc1edfbc5028edf1354e7dd2fa69a7968chin register struct stackblock* p;
da2e3ebdc1edfbc5028edf1354e7dd2fa69a7968chin
da2e3ebdc1edfbc5028edf1354e7dd2fa69a7968chin b = stack->blocks;
da2e3ebdc1edfbc5028edf1354e7dd2fa69a7968chin while (p = b)
da2e3ebdc1edfbc5028edf1354e7dd2fa69a7968chin {
da2e3ebdc1edfbc5028edf1354e7dd2fa69a7968chin b = p->next;
da2e3ebdc1edfbc5028edf1354e7dd2fa69a7968chin free(p->stack);
da2e3ebdc1edfbc5028edf1354e7dd2fa69a7968chin free(p);
da2e3ebdc1edfbc5028edf1354e7dd2fa69a7968chin }
da2e3ebdc1edfbc5028edf1354e7dd2fa69a7968chin free(stack);
da2e3ebdc1edfbc5028edf1354e7dd2fa69a7968chin}
da2e3ebdc1edfbc5028edf1354e7dd2fa69a7968chin
da2e3ebdc1edfbc5028edf1354e7dd2fa69a7968chin/*
da2e3ebdc1edfbc5028edf1354e7dd2fa69a7968chin * clear stack
da2e3ebdc1edfbc5028edf1354e7dd2fa69a7968chin */
da2e3ebdc1edfbc5028edf1354e7dd2fa69a7968chin
da2e3ebdc1edfbc5028edf1354e7dd2fa69a7968chinvoid
da2e3ebdc1edfbc5028edf1354e7dd2fa69a7968chinstackclear(register STACK stack)
da2e3ebdc1edfbc5028edf1354e7dd2fa69a7968chin{
da2e3ebdc1edfbc5028edf1354e7dd2fa69a7968chin stack->position.block = stack->blocks;
da2e3ebdc1edfbc5028edf1354e7dd2fa69a7968chin stack->position.index = -1;
da2e3ebdc1edfbc5028edf1354e7dd2fa69a7968chin}
da2e3ebdc1edfbc5028edf1354e7dd2fa69a7968chin
da2e3ebdc1edfbc5028edf1354e7dd2fa69a7968chin/*
da2e3ebdc1edfbc5028edf1354e7dd2fa69a7968chin * get value on top of stack
da2e3ebdc1edfbc5028edf1354e7dd2fa69a7968chin */
da2e3ebdc1edfbc5028edf1354e7dd2fa69a7968chin
da2e3ebdc1edfbc5028edf1354e7dd2fa69a7968chinvoid*
da2e3ebdc1edfbc5028edf1354e7dd2fa69a7968chinstackget(register STACK stack)
da2e3ebdc1edfbc5028edf1354e7dd2fa69a7968chin{
da2e3ebdc1edfbc5028edf1354e7dd2fa69a7968chin if (stack->position.index < 0) return(stack->error);
da2e3ebdc1edfbc5028edf1354e7dd2fa69a7968chin else return(stack->position.block->stack[stack->position.index]);
da2e3ebdc1edfbc5028edf1354e7dd2fa69a7968chin}
da2e3ebdc1edfbc5028edf1354e7dd2fa69a7968chin
da2e3ebdc1edfbc5028edf1354e7dd2fa69a7968chin/*
da2e3ebdc1edfbc5028edf1354e7dd2fa69a7968chin * push value on to stack
da2e3ebdc1edfbc5028edf1354e7dd2fa69a7968chin */
da2e3ebdc1edfbc5028edf1354e7dd2fa69a7968chin
da2e3ebdc1edfbc5028edf1354e7dd2fa69a7968chinint
da2e3ebdc1edfbc5028edf1354e7dd2fa69a7968chinstackpush(register STACK stack, void* value)
da2e3ebdc1edfbc5028edf1354e7dd2fa69a7968chin{
da2e3ebdc1edfbc5028edf1354e7dd2fa69a7968chin register struct stackblock *b;
da2e3ebdc1edfbc5028edf1354e7dd2fa69a7968chin
da2e3ebdc1edfbc5028edf1354e7dd2fa69a7968chin if (++stack->position.index >= stack->size)
da2e3ebdc1edfbc5028edf1354e7dd2fa69a7968chin {
da2e3ebdc1edfbc5028edf1354e7dd2fa69a7968chin b = stack->position.block;
da2e3ebdc1edfbc5028edf1354e7dd2fa69a7968chin if (b->next) b = b->next;
da2e3ebdc1edfbc5028edf1354e7dd2fa69a7968chin else
da2e3ebdc1edfbc5028edf1354e7dd2fa69a7968chin {
da2e3ebdc1edfbc5028edf1354e7dd2fa69a7968chin if (!(b->next = newof(0, struct stackblock, 1, 0)))
da2e3ebdc1edfbc5028edf1354e7dd2fa69a7968chin return(-1);
da2e3ebdc1edfbc5028edf1354e7dd2fa69a7968chin b = b->next;
da2e3ebdc1edfbc5028edf1354e7dd2fa69a7968chin if (!(b->stack = newof(0, void*, stack->size, 0)))
da2e3ebdc1edfbc5028edf1354e7dd2fa69a7968chin return(-1);
da2e3ebdc1edfbc5028edf1354e7dd2fa69a7968chin b->prev = stack->position.block;
da2e3ebdc1edfbc5028edf1354e7dd2fa69a7968chin b->next = 0;
da2e3ebdc1edfbc5028edf1354e7dd2fa69a7968chin }
da2e3ebdc1edfbc5028edf1354e7dd2fa69a7968chin stack->position.block = b;
da2e3ebdc1edfbc5028edf1354e7dd2fa69a7968chin stack->position.index = 0;
da2e3ebdc1edfbc5028edf1354e7dd2fa69a7968chin }
da2e3ebdc1edfbc5028edf1354e7dd2fa69a7968chin stack->position.block->stack[stack->position.index] = value;
da2e3ebdc1edfbc5028edf1354e7dd2fa69a7968chin return(0);
da2e3ebdc1edfbc5028edf1354e7dd2fa69a7968chin}
da2e3ebdc1edfbc5028edf1354e7dd2fa69a7968chin
da2e3ebdc1edfbc5028edf1354e7dd2fa69a7968chin/*
da2e3ebdc1edfbc5028edf1354e7dd2fa69a7968chin * pop value off stack
da2e3ebdc1edfbc5028edf1354e7dd2fa69a7968chin */
da2e3ebdc1edfbc5028edf1354e7dd2fa69a7968chin
da2e3ebdc1edfbc5028edf1354e7dd2fa69a7968chinint
da2e3ebdc1edfbc5028edf1354e7dd2fa69a7968chinstackpop(register STACK stack)
da2e3ebdc1edfbc5028edf1354e7dd2fa69a7968chin{
da2e3ebdc1edfbc5028edf1354e7dd2fa69a7968chin /*
da2e3ebdc1edfbc5028edf1354e7dd2fa69a7968chin * return:
da2e3ebdc1edfbc5028edf1354e7dd2fa69a7968chin *
da2e3ebdc1edfbc5028edf1354e7dd2fa69a7968chin * -1 if stack empty before pop
da2e3ebdc1edfbc5028edf1354e7dd2fa69a7968chin * 0 if stack empty after pop
da2e3ebdc1edfbc5028edf1354e7dd2fa69a7968chin * 1 if stack not empty before & after pop
da2e3ebdc1edfbc5028edf1354e7dd2fa69a7968chin */
da2e3ebdc1edfbc5028edf1354e7dd2fa69a7968chin
da2e3ebdc1edfbc5028edf1354e7dd2fa69a7968chin if (stack->position.index < 0) return(-1);
da2e3ebdc1edfbc5028edf1354e7dd2fa69a7968chin else if (--stack->position.index < 0)
da2e3ebdc1edfbc5028edf1354e7dd2fa69a7968chin {
da2e3ebdc1edfbc5028edf1354e7dd2fa69a7968chin if (!stack->position.block->prev) return(0);
da2e3ebdc1edfbc5028edf1354e7dd2fa69a7968chin stack->position.block = stack->position.block->prev;
da2e3ebdc1edfbc5028edf1354e7dd2fa69a7968chin stack->position.index = stack->size - 1;
da2e3ebdc1edfbc5028edf1354e7dd2fa69a7968chin return(1);
da2e3ebdc1edfbc5028edf1354e7dd2fa69a7968chin }
da2e3ebdc1edfbc5028edf1354e7dd2fa69a7968chin else return(1);
da2e3ebdc1edfbc5028edf1354e7dd2fa69a7968chin}
da2e3ebdc1edfbc5028edf1354e7dd2fa69a7968chin
da2e3ebdc1edfbc5028edf1354e7dd2fa69a7968chin/*
da2e3ebdc1edfbc5028edf1354e7dd2fa69a7968chin * set|get stack position
da2e3ebdc1edfbc5028edf1354e7dd2fa69a7968chin */
da2e3ebdc1edfbc5028edf1354e7dd2fa69a7968chin
da2e3ebdc1edfbc5028edf1354e7dd2fa69a7968chinvoid
da2e3ebdc1edfbc5028edf1354e7dd2fa69a7968chinstacktell(register STACK stack, int set, STACKPOS* position)
da2e3ebdc1edfbc5028edf1354e7dd2fa69a7968chin{
da2e3ebdc1edfbc5028edf1354e7dd2fa69a7968chin if (set) stack->position = *position;
da2e3ebdc1edfbc5028edf1354e7dd2fa69a7968chin else *position = stack->position;
da2e3ebdc1edfbc5028edf1354e7dd2fa69a7968chin}