summaryrefslogtreecommitdiff
path: root/usr/src/lib/libast/common/misc/stk.c
diff options
context:
space:
mode:
Diffstat (limited to 'usr/src/lib/libast/common/misc/stk.c')
-rw-r--r--usr/src/lib/libast/common/misc/stk.c508
1 files changed, 508 insertions, 0 deletions
diff --git a/usr/src/lib/libast/common/misc/stk.c b/usr/src/lib/libast/common/misc/stk.c
new file mode 100644
index 0000000000..9688e4b6cd
--- /dev/null
+++ b/usr/src/lib/libast/common/misc/stk.c
@@ -0,0 +1,508 @@
+/***********************************************************************
+* *
+* This software is part of the ast package *
+* Copyright (c) 1985-2007 AT&T Knowledge Ventures *
+* and is licensed under the *
+* Common Public License, Version 1.0 *
+* by AT&T Knowledge Ventures *
+* *
+* 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(int))
+#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));
+}
+
+/*
+ * 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;
+ 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;
+ 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));
+}
generated by cgit v1.2.3 (git 2.39.1) at 2025-06-26 16:25:17 +0000