common/misc/stk.c

/***********************************************************************
*                                                                      *
*               This software is part of the ast package               *
*          Copyright (c) 1985-2010 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(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));
}

/*
 * 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));
}