1N/A/***********************************************************************
1N/A* *
1N/A* This software is part of the ast package *
1N/A* Copyright (c) 1985-2011 AT&T Intellectual Property *
1N/A* and is licensed under the *
1N/A* Common Public License, Version 1.0 *
1N/A* by AT&T Intellectual Property *
1N/A* *
1N/A* A copy of the License is available at *
1N/A* http://www.opensource.org/licenses/cpl1.0.txt *
1N/A* (with md5 checksum 059e8cd6165cb4c31e351f2b69388fd9) *
1N/A* *
1N/A* Information and Software Systems Research *
1N/A* AT&T Research *
1N/A* Florham Park NJ *
1N/A* *
1N/A* Glenn Fowler <gsf@research.att.com> *
1N/A* David Korn <dgk@research.att.com> *
1N/A* Phong Vo <kpv@research.att.com> *
1N/A* *
1N/A***********************************************************************/
1N/A#pragma prototyped
1N/A/*
1N/A * Routines to implement a stack-like storage library
1N/A *
1N/A * A stack consists of a link list of variable size frames
1N/A * The beginning of each frame is initialized with a frame structure
1N/A * that contains a pointer to the previous frame and a pointer to the
1N/A * end of the current frame.
1N/A *
1N/A * This is a rewrite of the stk library that uses sfio
1N/A *
1N/A * David Korn
1N/A * AT&T Research
1N/A * dgk@research.att.com
1N/A *
1N/A */
1N/A
1N/A#include <sfio_t.h>
1N/A#include <ast.h>
1N/A#include <align.h>
1N/A#include <stk.h>
1N/A
1N/A/*
1N/A * A stack is a header and a linked list of frames
1N/A * The first frame has structure
1N/A * Sfio_t
1N/A * Sfdisc_t
1N/A * struct stk
1N/A * Frames have structure
1N/A * struct frame
1N/A * data
1N/A */
1N/A
1N/A#define STK_ALIGN ALIGN_BOUND
1N/A#define STK_FSIZE (1024*sizeof(char*))
1N/A#define STK_HDRSIZE (sizeof(Sfio_t)+sizeof(Sfdisc_t))
1N/A
1N/Atypedef char* (*_stk_overflow_)(int);
1N/A
1N/Astatic int stkexcept(Sfio_t*,int,void*,Sfdisc_t*);
1N/Astatic Sfdisc_t stkdisc = { 0, 0, 0, stkexcept };
1N/A
1N/ASfio_t _Stak_data = SFNEW((char*)0,0,-1,SF_STATIC|SF_WRITE|SF_STRING,&stkdisc,0);
1N/A
1N/A__EXTERN__(Sfio_t, _Stak_data);
1N/A
1N/Astruct frame
1N/A{
1N/A char *prev; /* address of previous frame */
1N/A char *end; /* address of end this frame */
1N/A char **aliases; /* address aliases */
1N/A int nalias; /* number of aliases */
1N/A};
1N/A
1N/Astruct stk
1N/A{
1N/A _stk_overflow_ stkoverflow; /* called when malloc fails */
1N/A short stkref; /* reference count; */
1N/A short stkflags; /* stack attributes */
1N/A char *stkbase; /* beginning of current stack frame */
1N/A char *stkend; /* end of current stack frame */
1N/A};
1N/A
1N/Astatic int init; /* 1 when initialized */
1N/Astatic struct stk *stkcur; /* pointer to current stk */
1N/Astatic char *stkgrow(Sfio_t*, unsigned);
1N/A
1N/A#define stream2stk(stream) ((stream)==stkstd? stkcur:\
1N/A ((struct stk*)(((char*)(stream))+STK_HDRSIZE)))
1N/A#define stk2stream(sp) ((Sfio_t*)(((char*)(sp))-STK_HDRSIZE))
1N/A#define stkleft(stream) ((stream)->_endb-(stream)->_data)
1N/A
1N/A
1N/A#ifdef STKSTATS
1N/A static struct
1N/A {
1N/A int create;
1N/A int delete;
1N/A int install;
1N/A int alloc;
1N/A int copy;
1N/A int puts;
1N/A int seek;
1N/A int set;
1N/A int grow;
1N/A int addsize;
1N/A int delsize;
1N/A int movsize;
1N/A } _stkstats;
1N/A# define increment(x) (_stkstats.x++)
1N/A# define count(x,n) (_stkstats.x += (n))
1N/A#else
1N/A# define increment(x)
1N/A# define count(x,n)
1N/A#endif /* STKSTATS */
1N/A
1N/Astatic const char Omsg[] = "malloc failed while growing stack\n";
1N/A
1N/A/*
1N/A * default overflow exception
1N/A */
1N/Astatic char *overflow(int n)
1N/A{
1N/A NoP(n);
1N/A write(2,Omsg, sizeof(Omsg)-1);
1N/A exit(2);
1N/A /* NOTREACHED */
1N/A return(0);
1N/A}
1N/A
1N/A/*
1N/A * initialize stkstd, sfio operations may have already occcured
1N/A */
1N/Astatic void stkinit(int size)
1N/A{
1N/A register Sfio_t *sp;
1N/A init = size;
1N/A sp = stkopen(0);
1N/A init = 1;
1N/A stkinstall(sp,overflow);
1N/A}
1N/A
1N/Astatic int stkexcept(register Sfio_t *stream, int type, void* val, Sfdisc_t* dp)
1N/A{
1N/A NoP(dp);
1N/A NoP(val);
1N/A switch(type)
1N/A {
1N/A case SF_CLOSING:
1N/A {
1N/A register struct stk *sp = stream2stk(stream);
1N/A register char *cp = sp->stkbase;
1N/A register struct frame *fp;
1N/A if(--sp->stkref<=0)
1N/A {
1N/A increment(delete);
1N/A if(stream==stkstd)
1N/A stkset(stream,(char*)0,0);
1N/A else
1N/A {
1N/A while(1)
1N/A {
1N/A fp = (struct frame*)cp;
1N/A if(fp->prev)
1N/A {
1N/A cp = fp->prev;
1N/A free(fp);
1N/A }
1N/A else
1N/A {
1N/A free(fp);
1N/A break;
1N/A }
1N/A }
1N/A }
1N/A }
1N/A stream->_data = stream->_next = 0;
1N/A }
1N/A return(0);
1N/A case SF_FINAL:
1N/A free(stream);
1N/A return(1);
1N/A case SF_DPOP:
1N/A return(-1);
1N/A case SF_WRITE:
1N/A case SF_SEEK:
1N/A {
1N/A long size = sfvalue(stream);
1N/A if(init)
1N/A {
1N/A Sfio_t *old = 0;
1N/A if(stream!=stkstd)
1N/A old = stkinstall(stream,NiL);
1N/A if(!stkgrow(stkstd,size-(stkstd->_endb-stkstd->_data)))
1N/A return(-1);
1N/A if(old)
1N/A stkinstall(old,NiL);
1N/A }
1N/A else
1N/A stkinit(size);
1N/A }
1N/A return(1);
1N/A case SF_NEW:
1N/A return(-1);
1N/A }
1N/A return(0);
1N/A}
1N/A
1N/A/*
1N/A * create a stack
1N/A */
1N/ASfio_t *stkopen(int flags)
1N/A{
1N/A register int bsize;
1N/A register Sfio_t *stream;
1N/A register struct stk *sp;
1N/A register struct frame *fp;
1N/A register Sfdisc_t *dp;
1N/A register char *cp;
1N/A if(!(stream=newof((char*)0,Sfio_t, 1, sizeof(*dp)+sizeof(*sp))))
1N/A return(0);
1N/A increment(create);
1N/A count(addsize,sizeof(*stream)+sizeof(*dp)+sizeof(*sp));
1N/A dp = (Sfdisc_t*)(stream+1);
1N/A dp->exceptf = stkexcept;
1N/A sp = (struct stk*)(dp+1);
1N/A sp->stkref = 1;
1N/A sp->stkflags = (flags&STK_SMALL);
1N/A if(flags&STK_NULL) sp->stkoverflow = 0;
1N/A else sp->stkoverflow = stkcur?stkcur->stkoverflow:overflow;
1N/A bsize = init+sizeof(struct frame);
1N/A#ifndef USE_REALLOC
1N/A if(flags&STK_SMALL)
1N/A bsize = roundof(bsize,STK_FSIZE/16);
1N/A else
1N/A#endif /* USE_REALLOC */
1N/A bsize = roundof(bsize,STK_FSIZE);
1N/A bsize -= sizeof(struct frame);
1N/A if(!(fp=newof((char*)0,struct frame, 1,bsize)))
1N/A {
1N/A free(stream);
1N/A return(0);
1N/A }
1N/A count(addsize,sizeof(*fp)+bsize);
1N/A cp = (char*)(fp+1);
1N/A sp->stkbase = (char*)fp;
1N/A fp->prev = 0;
1N/A fp->nalias = 0;
1N/A fp->aliases = 0;
1N/A fp->end = sp->stkend = cp+bsize;
1N/A if(!sfnew(stream,cp,bsize,-1,SF_STRING|SF_WRITE|SF_STATIC|SF_EOF))
1N/A return((Sfio_t*)0);
1N/A sfdisc(stream,dp);
1N/A return(stream);
1N/A}
1N/A
1N/A/*
1N/A * return a pointer to the current stack
1N/A * if <stream> is not null, it becomes the new current stack
1N/A * <oflow> becomes the new overflow function
1N/A */
1N/ASfio_t *stkinstall(Sfio_t *stream, _stk_overflow_ oflow)
1N/A{
1N/A Sfio_t *old;
1N/A register struct stk *sp;
1N/A if(!init)
1N/A {
1N/A stkinit(1);
1N/A if(oflow)
1N/A stkcur->stkoverflow = oflow;
1N/A return((Sfio_t*)0);
1N/A }
1N/A increment(install);
1N/A old = stkcur?stk2stream(stkcur):0;
1N/A if(stream)
1N/A {
1N/A sp = stream2stk(stream);
1N/A while(sfstack(stkstd, SF_POPSTACK));
1N/A if(stream!=stkstd)
1N/A sfstack(stkstd,stream);
1N/A stkcur = sp;
1N/A#ifdef USE_REALLOC
1N/A /*** someday ***/
1N/A#endif /* USE_REALLOC */
1N/A }
1N/A else
1N/A sp = stkcur;
1N/A if(oflow)
1N/A sp->stkoverflow = oflow;
1N/A return(old);
1N/A}
1N/A
1N/A/*
1N/A * increase the reference count on the given <stack>
1N/A */
1N/Aint stklink(register Sfio_t* stream)
1N/A{
1N/A register struct stk *sp = stream2stk(stream);
1N/A return(sp->stkref++);
1N/A}
1N/A
1N/A/*
1N/A * terminate a stack and free up the space
1N/A * >0 returned if reference decremented but still > 0
1N/A * 0 returned on last close
1N/A * <0 returned on error
1N/A */
1N/Aint stkclose(Sfio_t* stream)
1N/A{
1N/A register struct stk *sp = stream2stk(stream);
1N/A if(sp->stkref>1)
1N/A {
1N/A sp->stkref--;
1N/A return(1);
1N/A }
1N/A return(sfclose(stream));
1N/A}
1N/A
1N/A/*
1N/A * returns 1 if <loc> is on this stack
1N/A */
1N/Aint stkon(register Sfio_t * stream, register char* loc)
1N/A{
1N/A register struct stk *sp = stream2stk(stream);
1N/A register struct frame *fp;
1N/A for(fp=(struct frame*)sp->stkbase; fp; fp=(struct frame*)fp->prev)
1N/A if(loc>=((char*)(fp+1)) && loc< fp->end)
1N/A return(1);
1N/A return(0);
1N/A}
1N/A/*
1N/A * reset the bottom of the current stack back to <loc>
1N/A * if <loc> is not in this stack, then the stack is reset to the beginning
1N/A * otherwise, the top of the stack is set to stkbot+<offset>
1N/A *
1N/A */
1N/Achar *stkset(register Sfio_t * stream, register char* loc, unsigned offset)
1N/A{
1N/A register struct stk *sp = stream2stk(stream);
1N/A register char *cp;
1N/A register struct frame *fp;
1N/A register int frames = 0;
1N/A int n;
1N/A if(!init)
1N/A stkinit(offset+1);
1N/A increment(set);
1N/A while(1)
1N/A {
1N/A fp = (struct frame*)sp->stkbase;
1N/A cp = sp->stkbase + roundof(sizeof(struct frame), STK_ALIGN);
1N/A n = fp->nalias;
1N/A while(n-->0)
1N/A {
1N/A if(loc==fp->aliases[n])
1N/A {
1N/A loc = cp;
1N/A break;
1N/A }
1N/A }
1N/A /* see whether <loc> is in current stack frame */
1N/A if(loc>=cp && loc<=sp->stkend)
1N/A {
1N/A if(frames)
1N/A sfsetbuf(stream,cp,sp->stkend-cp);
1N/A stream->_data = (unsigned char*)(cp + roundof(loc-cp,STK_ALIGN));
1N/A stream->_next = (unsigned char*)loc+offset;
1N/A goto found;
1N/A }
1N/A if(fp->prev)
1N/A {
1N/A sp->stkbase = fp->prev;
1N/A sp->stkend = ((struct frame*)(fp->prev))->end;
1N/A free((void*)fp);
1N/A }
1N/A else
1N/A break;
1N/A frames++;
1N/A }
1N/A /* set stack back to the beginning */
1N/A cp = (char*)(fp+1);
1N/A if(frames)
1N/A sfsetbuf(stream,cp,sp->stkend-cp);
1N/A else
1N/A stream->_data = stream->_next = (unsigned char*)cp;
1N/Afound:
1N/A return((char*)stream->_data);
1N/A}
1N/A
1N/A/*
1N/A * allocate <n> bytes on the current stack
1N/A */
1N/Achar *stkalloc(register Sfio_t *stream, register unsigned int n)
1N/A{
1N/A register unsigned char *old;
1N/A if(!init)
1N/A stkinit(n);
1N/A increment(alloc);
1N/A n = roundof(n,STK_ALIGN);
1N/A if(stkleft(stream) <= (int)n && !stkgrow(stream,n))
1N/A return(0);
1N/A old = stream->_data;
1N/A stream->_data = stream->_next = old+n;
1N/A return((char*)old);
1N/A}
1N/A
1N/A/*
1N/A * begin a new stack word of at least <n> bytes
1N/A */
1N/Achar *_stkseek(register Sfio_t *stream, register unsigned n)
1N/A{
1N/A if(!init)
1N/A stkinit(n);
1N/A increment(seek);
1N/A if(stkleft(stream) <= (int)n && !stkgrow(stream,n))
1N/A return(0);
1N/A stream->_next = stream->_data+n;
1N/A return((char*)stream->_data);
1N/A}
1N/A
1N/A/*
1N/A * advance the stack to the current top
1N/A * if extra is non-zero, first add a extra bytes and zero the first
1N/A */
1N/Achar *stkfreeze(register Sfio_t *stream, register unsigned extra)
1N/A{
1N/A register unsigned char *old, *top;
1N/A if(!init)
1N/A stkinit(extra);
1N/A old = stream->_data;
1N/A top = stream->_next;
1N/A if(extra)
1N/A {
1N/A if(extra > (stream->_endb-stream->_next))
1N/A {
1N/A if (!(top = (unsigned char*)stkgrow(stream,extra)))
1N/A return(0);
1N/A old = stream->_data;
1N/A }
1N/A *top = 0;
1N/A top += extra;
1N/A }
1N/A stream->_next = stream->_data += roundof(top-old,STK_ALIGN);
1N/A return((char*)old);
1N/A}
1N/A
1N/A/*
1N/A * copy string <str> onto the stack as a new stack word
1N/A */
1N/Achar *stkcopy(Sfio_t *stream, const char* str)
1N/A{
1N/A register unsigned char *cp = (unsigned char*)str;
1N/A register int n;
1N/A register int off=stktell(stream);
1N/A char buff[40], *tp=buff;
1N/A if(off)
1N/A {
1N/A if(off > sizeof(buff))
1N/A {
1N/A if(!(tp = malloc(off)))
1N/A {
1N/A struct stk *sp = stream2stk(stream);
1N/A if(!sp->stkoverflow || !(tp = (*sp->stkoverflow)(off)))
1N/A return(0);
1N/A }
1N/A }
1N/A memcpy(tp, stream->_data, off);
1N/A }
1N/A while(*cp++);
1N/A n = roundof(cp-(unsigned char*)str,STK_ALIGN);
1N/A if(!init)
1N/A stkinit(n);
1N/A increment(copy);
1N/A if(stkleft(stream) <= n && !stkgrow(stream,n))
1N/A return(0);
1N/A strcpy((char*)(cp=stream->_data),str);
1N/A stream->_data = stream->_next = cp+n;
1N/A if(off)
1N/A {
1N/A _stkseek(stream,off);
1N/A memcpy(stream->_data, tp, off);
1N/A if(tp!=buff)
1N/A free((void*)tp);
1N/A }
1N/A return((char*)cp);
1N/A}
1N/A
1N/A/*
1N/A * add a new stack frame of size >= <n> to the current stack.
1N/A * if <n> > 0, copy the bytes from stkbot to stktop to the new stack
1N/A * if <n> is zero, then copy the remainder of the stack frame from stkbot
1N/A * to the end is copied into the new stack frame
1N/A */
1N/A
1N/Astatic char *stkgrow(register Sfio_t *stream, unsigned size)
1N/A{
1N/A register int n = size;
1N/A register struct stk *sp = stream2stk(stream);
1N/A register struct frame *fp= (struct frame*)sp->stkbase;
1N/A register char *cp, *dp=0;
1N/A register unsigned m = stktell(stream);
1N/A int nn=0;
1N/A n += (m + sizeof(struct frame)+1);
1N/A if(sp->stkflags&STK_SMALL)
1N/A#ifndef USE_REALLOC
1N/A n = roundof(n,STK_FSIZE/16);
1N/A else
1N/A#endif /* !USE_REALLOC */
1N/A n = roundof(n,STK_FSIZE);
1N/A /* see whether current frame can be extended */
1N/A if(stkptr(stream,0)==sp->stkbase+sizeof(struct frame))
1N/A {
1N/A nn = fp->nalias+1;
1N/A dp=sp->stkbase;
1N/A sp->stkbase = ((struct frame*)dp)->prev;
1N/A }
1N/A cp = newof(dp, char, n, nn*sizeof(char*));
1N/A if(!cp && (!sp->stkoverflow || !(cp = (*sp->stkoverflow)(n))))
1N/A return(0);
1N/A increment(grow);
1N/A count(addsize,n - (dp?m:0));
1N/A if(dp && cp==dp)
1N/A nn--;
1N/A fp = (struct frame*)cp;
1N/A fp->prev = sp->stkbase;
1N/A sp->stkbase = cp;
1N/A sp->stkend = fp->end = cp+n;
1N/A cp = (char*)(fp+1);
1N/A cp = sp->stkbase + roundof((cp-sp->stkbase),STK_ALIGN);
1N/A if(fp->nalias=nn)
1N/A {
1N/A fp->aliases = (char**)fp->end;
1N/A fp->aliases[nn-1] = dp + roundof(sizeof(struct frame),STK_ALIGN);
1N/A }
1N/A if(m && !dp)
1N/A {
1N/A memcpy(cp,(char*)stream->_data,m);
1N/A count(movsize,m);
1N/A }
1N/A sfsetbuf(stream,cp,sp->stkend-cp);
1N/A return((char*)(stream->_next = stream->_data+m));
1N/A}