stk.c   [plain text]

/***********************************************************************
*                                                                      *
*               This software is part of the ast package               *
*          Copyright (c) 1985-2011 AT&T Intellectual Property          *
*                      and is licensed under the                       *
*                  Common Public License, Version 1.0                  *
*                    by AT&T Intellectual Property                     *
*                                                                      *
*                A copy of the License is available at                 *
*            http://www.opensource.org/licenses/cpl1.0.txt             *
*         (with md5 checksum 059e8cd6165cb4c31e351f2b69388fd9)         *
*                                                                      *
*              Information and Software Systems Research               *
*                            AT&T Research                             *
*                           Florham Park NJ                            *
*                                                                      *
*                 Glenn Fowler <gsf@research.att.com>                  *
*                  David Korn <dgk@research.att.com>                   *
*                   Phong Vo <kpv@research.att.com>                    *
*                                                                      *
***********************************************************************/
#pragma prototyped
/*
 *   Routines to implement a stack-like storage library
 *   
 *   A stack consists of a link list of variable size frames
 *   The beginning of each frame is initialized with a frame structure
 *   that contains a pointer to the previous frame and a pointer to the
 *   end of the current frame.
 *
 *   This is a rewrite of the stk library that uses sfio
 *
 *   David Korn
 *   AT&T Research
 *   dgk@research.att.com
 *
 */

#include	<sfio_t.h>
#include	<ast.h>
#include	<align.h>
#include	<stk.h>

/*
 *  A stack is a header and a linked list of frames
 *  The first frame has structure
 *	Sfio_t
 *	Sfdisc_t
 *	struct stk
 * Frames have structure
 *	struct frame
 *	data
 */

#define STK_ALIGN	ALIGN_BOUND
#define STK_FSIZE	(1024*sizeof(char*))
#define STK_HDRSIZE	(sizeof(Sfio_t)+sizeof(Sfdisc_t))

typedef char* (*_stk_overflow_)(int);

static int stkexcept(Sfio_t*,int,void*,Sfdisc_t*);
static Sfdisc_t stkdisc = { 0, 0, 0, stkexcept };

Sfio_t _Stak_data = SFNEW((char*)0,0,-1,SF_STATIC|SF_WRITE|SF_STRING,&stkdisc,0);

__EXTERN__(Sfio_t, _Stak_data);

struct frame
{
	char	*prev;		/* address of previous frame */
	char	*end;		/* address of end this frame */
	char	**aliases;	/* address aliases */
	int	nalias;		/* number of aliases */
};

struct stk
{
	_stk_overflow_	stkoverflow;	/* called when malloc fails */
	short		stkref;	/* reference count; */
	short		stkflags;	/* stack attributes */
	char		*stkbase;	/* beginning of current stack frame */
	char		*stkend;	/* end of current stack frame */
};

static int		init;		/* 1 when initialized */
static struct stk	*stkcur;	/* pointer to current stk */
static char		*stkgrow(Sfio_t*, unsigned);

#define stream2stk(stream)	((stream)==stkstd? stkcur:\
				 ((struct stk*)(((char*)(stream))+STK_HDRSIZE)))
#define stk2stream(sp)		((Sfio_t*)(((char*)(sp))-STK_HDRSIZE))
#define stkleft(stream)		((stream)->_endb-(stream)->_data)
	

#ifdef STKSTATS
    static struct
    {
	int	create;
	int	delete;
	int	install;
	int	alloc;
	int	copy;
	int	puts;
	int	seek;
	int	set;
	int	grow;
	int	addsize;
	int	delsize;
	int	movsize;
    } _stkstats;
#   define increment(x)	(_stkstats.x++)
#   define count(x,n)	(_stkstats.x += (n))
#else
#   define increment(x)
#   define count(x,n)
#endif /* STKSTATS */

static const char Omsg[] = "malloc failed while growing stack\n";

/*
 * default overflow exception
 */
static char *overflow(int n)
{
	NoP(n);
	write(2,Omsg, sizeof(Omsg)-1);
	exit(2);
	/* NOTREACHED */
	return(0);
}

/*
 * initialize stkstd, sfio operations may have already occcured
 */
static void stkinit(int size)
{
	register Sfio_t *sp;
	init = size;
	sp = stkopen(0);
	init = 1;
	stkinstall(sp,overflow);
}

static int stkexcept(register Sfio_t *stream, int type, void* val, Sfdisc_t* dp)
{
	NoP(dp);
	NoP(val);
	switch(type)
	{
	    case SF_CLOSING:
		{
			register struct stk *sp = stream2stk(stream); 
			register char *cp = sp->stkbase;
			register struct frame *fp;
			if(--sp->stkref<=0)
			{
				increment(delete);
				if(stream==stkstd)
					stkset(stream,(char*)0,0);
				else
				{
					while(1)
					{
						fp = (struct frame*)cp;
						if(fp->prev)
						{
							cp = fp->prev;
							free(fp);
						}
						else
						{
							free(fp);
							break;
						}
					}
				}
			}
			stream->_data = stream->_next = 0;
		}
		return(0);
	    case SF_FINAL:
		free(stream);
		return(1);
	    case SF_DPOP:
		return(-1);
	    case SF_WRITE:
	    case SF_SEEK:
		{
			long size = sfvalue(stream);
			if(init)
			{
				Sfio_t *old = 0;
				if(stream!=stkstd)
					old = stkinstall(stream,NiL);
				if(!stkgrow(stkstd,size-(stkstd->_endb-stkstd->_data)))
					return(-1);
				if(old)
					stkinstall(old,NiL);
			}
			else
				stkinit(size);
		}
		return(1);
	    case SF_NEW:
		return(-1);
	}
	return(0);
}

/*
 * create a stack
 */
Sfio_t *stkopen(int flags)
{
	register int bsize;
	register Sfio_t *stream;
	register struct stk *sp;
	register struct frame *fp;
	register Sfdisc_t *dp;
	register char *cp;
	if(!(stream=newof((char*)0,Sfio_t, 1, sizeof(*dp)+sizeof(*sp))))
		return(0);
	increment(create);
	count(addsize,sizeof(*stream)+sizeof(*dp)+sizeof(*sp));
	dp = (Sfdisc_t*)(stream+1);
	dp->exceptf = stkexcept;
	sp = (struct stk*)(dp+1);
	sp->stkref = 1;
	sp->stkflags = (flags&STK_SMALL);
	if(flags&STK_NULL) sp->stkoverflow = 0;
	else sp->stkoverflow = stkcur?stkcur->stkoverflow:overflow;
	bsize = init+sizeof(struct frame);
#ifndef USE_REALLOC
	if(flags&STK_SMALL)
		bsize = roundof(bsize,STK_FSIZE/16);
	else
#endif /* USE_REALLOC */
		bsize = roundof(bsize,STK_FSIZE);
	bsize -= sizeof(struct frame);
	if(!(fp=newof((char*)0,struct frame, 1,bsize)))
	{
		free(stream);
		return(0);
	}
	count(addsize,sizeof(*fp)+bsize);
	cp = (char*)(fp+1);
	sp->stkbase = (char*)fp;
	fp->prev = 0;
	fp->nalias = 0;
	fp->aliases = 0;
	fp->end = sp->stkend = cp+bsize;
	if(!sfnew(stream,cp,bsize,-1,SF_STRING|SF_WRITE|SF_STATIC|SF_EOF))
		return((Sfio_t*)0);
	sfdisc(stream,dp);
	return(stream);
}

/*
 * return a pointer to the current stack
 * if <stream> is not null, it becomes the new current stack
 * <oflow> becomes the new overflow function
 */
Sfio_t *stkinstall(Sfio_t *stream, _stk_overflow_ oflow)
{
	Sfio_t *old;
	register struct stk *sp;
	if(!init)
	{
		stkinit(1);
		if(oflow)
			stkcur->stkoverflow = oflow;
		return((Sfio_t*)0);
	}
	increment(install);
	old = stkcur?stk2stream(stkcur):0;
	if(stream)
	{
		sp = stream2stk(stream);
		while(sfstack(stkstd, SF_POPSTACK));
		if(stream!=stkstd)
			sfstack(stkstd,stream);
		stkcur = sp;
#ifdef USE_REALLOC
		/*** someday ***/
#endif /* USE_REALLOC */
	}
	else
		sp = stkcur;
	if(oflow)
		sp->stkoverflow = oflow;
	return(old);
}

/*
 * increase the reference count on the given <stack>
 */
int stklink(register Sfio_t* stream)
{
	register struct stk *sp = stream2stk(stream);
	return(sp->stkref++);
}

/*
 * terminate a stack and free up the space
 * >0 returned if reference decremented but still > 0
 *  0 returned on last close
 * <0 returned on error
 */
int stkclose(Sfio_t* stream)
{
	register struct stk *sp = stream2stk(stream); 
	if(sp->stkref>1)
	{
		sp->stkref--;
		return(1);
	}
	return(sfclose(stream));
}

/*
 * returns 1 if <loc> is on this stack
 */
int stkon(register Sfio_t * stream, register char* loc)
{
	register struct stk *sp = stream2stk(stream); 
	register struct frame *fp;
	for(fp=(struct frame*)sp->stkbase; fp; fp=(struct frame*)fp->prev)
		if(loc>=((char*)(fp+1)) && loc< fp->end)
			return(1);
	return(0);
}
/*
 * reset the bottom of the current stack back to <loc>
 * if <loc> is not in this stack, then the stack is reset to the beginning
 * otherwise, the top of the stack is set to stkbot+<offset>
 *
 */
char *stkset(register Sfio_t * stream, register char* loc, unsigned offset)
{
	register struct stk *sp = stream2stk(stream); 
	register char *cp;
	register struct frame *fp;
	register int frames = 0;
	int n;
	if(!init)
		stkinit(offset+1);
	increment(set);
	while(1)
	{
		fp = (struct frame*)sp->stkbase;
		cp  = sp->stkbase + roundof(sizeof(struct frame), STK_ALIGN);
		n = fp->nalias;
		while(n-->0)
		{
			if(loc==fp->aliases[n])
			{
				loc = cp;
				break;
			}
		}
		/* see whether <loc> is in current stack frame */
		if(loc>=cp && loc<=sp->stkend)
		{
			if(frames)
				sfsetbuf(stream,cp,sp->stkend-cp);
			stream->_data = (unsigned char*)(cp + roundof(loc-cp,STK_ALIGN));
			stream->_next = (unsigned char*)loc+offset;
			goto found;
		}
		if(fp->prev)
		{
			sp->stkbase = fp->prev;
			sp->stkend = ((struct frame*)(fp->prev))->end;
			free((void*)fp);
		}
		else
			break;
		frames++;
	}
	/* set stack back to the beginning */
	cp = (char*)(fp+1);
	if(frames)
		sfsetbuf(stream,cp,sp->stkend-cp);
	else
		stream->_data = stream->_next = (unsigned char*)cp;
found:
	return((char*)stream->_data);
}

/*
 * allocate <n> bytes on the current stack
 */
char *stkalloc(register Sfio_t *stream, register unsigned int n)
{
	register unsigned char *old;
	if(!init)
		stkinit(n);
	increment(alloc);
	n = roundof(n,STK_ALIGN);
	if(stkleft(stream) <= (int)n && !stkgrow(stream,n))
		return(0);
	old = stream->_data;
	stream->_data = stream->_next = old+n;
	return((char*)old);
}

/*
 * begin a new stack word of at least <n> bytes
 */
char *_stkseek(register Sfio_t *stream, register unsigned n)
{
	if(!init)
		stkinit(n);
	increment(seek);
	if(stkleft(stream) <= (int)n && !stkgrow(stream,n))
		return(0);
	stream->_next = stream->_data+n;
	return((char*)stream->_data);
}

/*
 * advance the stack to the current top
 * if extra is non-zero, first add a extra bytes and zero the first
 */
char	*stkfreeze(register Sfio_t *stream, register unsigned extra)
{
	register unsigned char *old, *top;
	if(!init)
		stkinit(extra);
	old = stream->_data;
	top = stream->_next;
	if(extra)
	{
		if(extra > (stream->_endb-stream->_next))
		{
			if (!(top = (unsigned char*)stkgrow(stream,extra)))
				return(0);
			old = stream->_data;
		}
		*top = 0;
		top += extra;
	}
	stream->_next = stream->_data += roundof(top-old,STK_ALIGN);
	return((char*)old);
}

/*
 * copy string <str> onto the stack as a new stack word
 */
char	*stkcopy(Sfio_t *stream, const char* str)
{
	register unsigned char *cp = (unsigned char*)str;
	register int n;
	register int off=stktell(stream);
	char buff[40], *tp=buff;
	if(off)
	{
		if(off > sizeof(buff))
		{
			if(!(tp = malloc(off)))
			{
				struct stk *sp = stream2stk(stream);
				if(!sp->stkoverflow || !(tp = (*sp->stkoverflow)(off)))
					return(0);
			}
		}
		memcpy(tp, stream->_data, off);
	}
	while(*cp++);
	n = roundof(cp-(unsigned char*)str,STK_ALIGN);
	if(!init)
		stkinit(n);
	increment(copy);
	if(stkleft(stream) <= n && !stkgrow(stream,n))
		return(0);
	strcpy((char*)(cp=stream->_data),str);
	stream->_data = stream->_next = cp+n;
	if(off)
	{
		_stkseek(stream,off);
		memcpy(stream->_data, tp, off);
		if(tp!=buff)
			free((void*)tp);
	}
	return((char*)cp);
}

/*
 * add a new stack frame of size >= <n> to the current stack.
 * if <n> > 0, copy the bytes from stkbot to stktop to the new stack
 * if <n> is zero, then copy the remainder of the stack frame from stkbot
 * to the end is copied into the new stack frame
 */

static char *stkgrow(register Sfio_t *stream, unsigned size)
{
	register int n = size;
	register struct stk *sp = stream2stk(stream);
	register struct frame *fp= (struct frame*)sp->stkbase;
	register char *cp, *dp=0;
	register unsigned m = stktell(stream);
	int nn=0;
	n += (m + sizeof(struct frame)+1);
	if(sp->stkflags&STK_SMALL)
#ifndef USE_REALLOC
		n = roundof(n,STK_FSIZE/16);
	else
#endif /* !USE_REALLOC */
		n = roundof(n,STK_FSIZE);
	/* see whether current frame can be extended */
	if(stkptr(stream,0)==sp->stkbase+sizeof(struct frame))
	{
		nn = fp->nalias+1;
		dp=sp->stkbase;
		sp->stkbase = ((struct frame*)dp)->prev;
	}
	cp = newof(dp, char, n, nn*sizeof(char*));
	if(!cp && (!sp->stkoverflow || !(cp = (*sp->stkoverflow)(n))))
		return(0);
	increment(grow);
	count(addsize,n - (dp?m:0));
	if(dp && cp==dp)
		nn--;
	fp = (struct frame*)cp;
	fp->prev = sp->stkbase;
	sp->stkbase = cp;
	sp->stkend = fp->end = cp+n;
	cp = (char*)(fp+1);
	cp = sp->stkbase + roundof((cp-sp->stkbase),STK_ALIGN);
	if(fp->nalias=nn)
	{
		fp->aliases = (char**)fp->end;
		fp->aliases[nn-1] =  dp + roundof(sizeof(struct frame),STK_ALIGN);
	}
	if(m && !dp)
	{
		memcpy(cp,(char*)stream->_data,m);
		count(movsize,m);
	}
	sfsetbuf(stream,cp,sp->stkend-cp);
	return((char*)(stream->_next = stream->_data+m));
}