usr/src/lib/libast/common/misc/stk.c

   1 /***********************************************************************
   2 *                                                                      *
   3 *               This software is part of the ast package               *
   4 *          Copyright (c) 1985-2010 AT&T Intellectual Property          *
   5 *                      and is licensed under the                       *
   6 *                  Common Public License, Version 1.0                  *
   7 *                    by AT&T Intellectual Property                     *
   8 *                                                                      *
   9 *                A copy of the License is available at                 *
  10 *            http://www.opensource.org/licenses/cpl1.0.txt             *
  11 *         (with md5 checksum 059e8cd6165cb4c31e351f2b69388fd9)         *
  12 *                                                                      *
  13 *              Information and Software Systems Research               *
  14 *                            AT&T Research                             *
  15 *                           Florham Park NJ                            *
  16 *                                                                      *
  17 *                 Glenn Fowler <gsf@research.att.com>                  *
  18 *                  David Korn <dgk@research.att.com>                   *
  19 *                   Phong Vo <kpv@research.att.com>                    *
  20 *                                                                      *
  21 ***********************************************************************/
  22 #pragma prototyped
  23 /*
  24  *   Routines to implement a stack-like storage library
  25  *
  26  *   A stack consists of a link list of variable size frames
  27  *   The beginning of each frame is initialized with a frame structure
  28  *   that contains a pointer to the previous frame and a pointer to the
  29  *   end of the current frame.
  30  *
  31  *   This is a rewrite of the stk library that uses sfio
  32  *
  33  *   David Korn
  34  *   AT&T Research
  35  *   dgk@research.att.com
  36  *
  37  */
  38
  39 #include        <sfio_t.h>
  40 #include        <ast.h>
  41 #include        <align.h>
  42 #include        <stk.h>
  43
  44 /*
  45  *  A stack is a header and a linked list of frames
  46  *  The first frame has structure
  47  *      Sfio_t
  48  *      Sfdisc_t
  49  *      struct stk
  50  * Frames have structure
  51  *      struct frame
  52  *      data
  53  */
  54
  55 #define STK_ALIGN       ALIGN_BOUND
  56 #define STK_FSIZE       (1024*sizeof(int))
  57 #define STK_HDRSIZE     (sizeof(Sfio_t)+sizeof(Sfdisc_t))
  58
  59 typedef char* (*_stk_overflow_)(int);
  60
  61 static int stkexcept(Sfio_t*,int,void*,Sfdisc_t*);
  62 static Sfdisc_t stkdisc = { 0, 0, 0, stkexcept };
  63
  64 Sfio_t _Stak_data = SFNEW((char*)0,0,-1,SF_STATIC|SF_WRITE|SF_STRING,&stkdisc,0);
  65
  66 __EXTERN__(Sfio_t, _Stak_data);
  67
  68 struct frame
  69 {
  70         char    *prev;          /* address of previous frame */
  71         char    *end;           /* address of end this frame */
  72         char    **aliases;      /* address aliases */
  73         int     nalias;         /* number of aliases */
  74 };
  75
  76 struct stk
  77 {
  78         _stk_overflow_  stkoverflow;    /* called when malloc fails */
  79         short           stkref; /* reference count; */
  80         short           stkflags;       /* stack attributes */
  81         char            *stkbase;       /* beginning of current stack frame */
  82         char            *stkend;        /* end of current stack frame */
  83 };
  84
  85 static int              init;           /* 1 when initialized */
  86 static struct stk       *stkcur;        /* pointer to current stk */
  87 static char             *stkgrow(Sfio_t*, unsigned);
  88
  89 #define stream2stk(stream)      ((stream)==stkstd? stkcur:\
  90                                  ((struct stk*)(((char*)(stream))+STK_HDRSIZE)))
  91 #define stk2stream(sp)          ((Sfio_t*)(((char*)(sp))-STK_HDRSIZE))
  92 #define stkleft(stream)         ((stream)->_endb-(stream)->_data)
  93
  94
  95 #ifdef STKSTATS
  96     static struct
  97     {
  98         int     create;
  99         int     delete;
 100         int     install;
 101         int     alloc;
 102         int     copy;
 103         int     puts;
 104         int     seek;
 105         int     set;
 106         int     grow;
 107         int     addsize;
 108         int     delsize;
 109         int     movsize;
 110     } _stkstats;
 111 #   define increment(x) (_stkstats.x++)
 112 #   define count(x,n)   (_stkstats.x += (n))
 113 #else
 114 #   define increment(x)
 115 #   define count(x,n)
 116 #endif /* STKSTATS */
 117
 118 static const char Omsg[] = "malloc failed while growing stack\n";
 119
 120 /*
 121  * default overflow exception
 122  */
 123 static char *overflow(int n)
 124 {
 125         NoP(n);
 126         write(2,Omsg, sizeof(Omsg)-1);
 127         exit(2);
 128         /* NOTREACHED */
 129         return(0);
 130 }
 131
 132 /*
 133  * initialize stkstd, sfio operations may have already occcured
 134  */
 135 static void stkinit(int size)
 136 {
 137         register Sfio_t *sp;
 138         init = size;
 139         sp = stkopen(0);
 140         init = 1;
 141         stkinstall(sp,overflow);
 142 }
 143
 144 static int stkexcept(register Sfio_t *stream, int type, void* val, Sfdisc_t* dp)
 145 {
 146         NoP(dp);
 147         NoP(val);
 148         switch(type)
 149         {
 150             case SF_CLOSING:
 151                 {
 152                         register struct stk *sp = stream2stk(stream);
 153                         register char *cp = sp->stkbase;
 154                         register struct frame *fp;
 155                         if(--sp->stkref<=0)
 156                         {
 157                                 increment(delete);
 158                                 if(stream==stkstd)
 159                                         stkset(stream,(char*)0,0);
 160                                 else
 161                                 {
 162                                         while(1)
 163                                         {
 164                                                 fp = (struct frame*)cp;
 165                                                 if(fp->prev)
 166                                                 {
 167                                                         cp = fp->prev;
 168                                                         free(fp);
 169                                                 }
 170                                                 else
 171                                                 {
 172                                                         free(fp);
 173                                                         break;
 174                                                 }
 175                                         }
 176                                 }
 177                         }
 178                         stream->_data = stream->_next = 0;
 179                 }
 180                 return(0);
 181             case SF_FINAL:
 182                 free(stream);
 183                 return(1);
 184             case SF_DPOP:
 185                 return(-1);
 186             case SF_WRITE:
 187             case SF_SEEK:
 188                 {
 189                         long size = sfvalue(stream);
 190                         if(init)
 191                         {
 192                                 Sfio_t *old = 0;
 193                                 if(stream!=stkstd)
 194                                         old = stkinstall(stream,NiL);
 195                                 if(!stkgrow(stkstd,size-(stkstd->_endb-stkstd->_data)))
 196                                         return(-1);
 197                                 if(old)
 198                                         stkinstall(old,NiL);
 199                         }
 200                         else
 201                                 stkinit(size);
 202                 }
 203                 return(1);
 204             case SF_NEW:
 205                 return(-1);
 206         }
 207         return(0);
 208 }
 209
 210 /*
 211  * create a stack
 212  */
 213 Sfio_t *stkopen(int flags)
 214 {
 215         register int bsize;
 216         register Sfio_t *stream;
 217         register struct stk *sp;
 218         register struct frame *fp;
 219         register Sfdisc_t *dp;
 220         register char *cp;
 221         if(!(stream=newof((char*)0,Sfio_t, 1, sizeof(*dp)+sizeof(*sp))))
 222                 return(0);
 223         increment(create);
 224         count(addsize,sizeof(*stream)+sizeof(*dp)+sizeof(*sp));
 225         dp = (Sfdisc_t*)(stream+1);
 226         dp->exceptf = stkexcept;
 227         sp = (struct stk*)(dp+1);
 228         sp->stkref = 1;
 229         sp->stkflags = (flags&STK_SMALL);
 230         if(flags&STK_NULL) sp->stkoverflow = 0;
 231         else sp->stkoverflow = stkcur?stkcur->stkoverflow:overflow;
 232         bsize = init+sizeof(struct frame);
 233 #ifndef USE_REALLOC
 234         if(flags&STK_SMALL)
 235                 bsize = roundof(bsize,STK_FSIZE/16);
 236         else
 237 #endif /* USE_REALLOC */
 238                 bsize = roundof(bsize,STK_FSIZE);
 239         bsize -= sizeof(struct frame);
 240         if(!(fp=newof((char*)0,struct frame, 1,bsize)))
 241         {
 242                 free(stream);
 243                 return(0);
 244         }
 245         count(addsize,sizeof(*fp)+bsize);
 246         cp = (char*)(fp+1);
 247         sp->stkbase = (char*)fp;
 248         fp->prev = 0;
 249         fp->nalias = 0;
 250         fp->aliases = 0;
 251         fp->end = sp->stkend = cp+bsize;
 252         if(!sfnew(stream,cp,bsize,-1,SF_STRING|SF_WRITE|SF_STATIC|SF_EOF))
 253                 return((Sfio_t*)0);
 254         sfdisc(stream,dp);
 255         return(stream);
 256 }
 257
 258 /*
 259  * return a pointer to the current stack
 260  * if <stream> is not null, it becomes the new current stack
 261  * <oflow> becomes the new overflow function
 262  */
 263 Sfio_t *stkinstall(Sfio_t *stream, _stk_overflow_ oflow)
 264 {
 265         Sfio_t *old;
 266         register struct stk *sp;
 267         if(!init)
 268         {
 269                 stkinit(1);
 270                 if(oflow)
 271                         stkcur->stkoverflow = oflow;
 272                 return((Sfio_t*)0);
 273         }
 274         increment(install);
 275         old = stkcur?stk2stream(stkcur):0;
 276         if(stream)
 277         {
 278                 sp = stream2stk(stream);
 279                 while(sfstack(stkstd, SF_POPSTACK));
 280                 if(stream!=stkstd)
 281                         sfstack(stkstd,stream);
 282                 stkcur = sp;
 283 #ifdef USE_REALLOC
 284                 /*** someday ***/
 285 #endif /* USE_REALLOC */
 286         }
 287         else
 288                 sp = stkcur;
 289         if(oflow)
 290                 sp->stkoverflow = oflow;
 291         return(old);
 292 }
 293
 294 /*
 295  * increase the reference count on the given <stack>
 296  */
 297 int stklink(register Sfio_t* stream)
 298 {
 299         register struct stk *sp = stream2stk(stream);
 300         return(sp->stkref++);
 301 }
 302
 303 /*
 304  * terminate a stack and free up the space
 305  * >0 returned if reference decremented but still > 0
 306  *  0 returned on last close
 307  * <0 returned on error
 308  */
 309 int stkclose(Sfio_t* stream)
 310 {
 311         register struct stk *sp = stream2stk(stream);
 312         if(sp->stkref>1)
 313         {
 314                 sp->stkref--;
 315                 return(1);
 316         }
 317         return(sfclose(stream));
 318 }
 319
 320 /*
 321  * returns 1 if <loc> is on this stack
 322  */
 323 int stkon(register Sfio_t * stream, register char* loc)
 324 {
 325         register struct stk *sp = stream2stk(stream);
 326         register struct frame *fp;
 327         for(fp=(struct frame*)sp->stkbase; fp; fp=(struct frame*)fp->prev)
 328                 if(loc>=((char*)(fp+1)) && loc< fp->end)
 329                         return(1);
 330         return(0);
 331 }
 332 /*
 333  * reset the bottom of the current stack back to <loc>
 334  * if <loc> is not in this stack, then the stack is reset to the beginning
 335  * otherwise, the top of the stack is set to stkbot+<offset>
 336  *
 337  */
 338 char *stkset(register Sfio_t * stream, register char* loc, unsigned offset)
 339 {
 340         register struct stk *sp = stream2stk(stream);
 341         register char *cp;
 342         register struct frame *fp;
 343         register int frames = 0;
 344         int n;
 345         if(!init)
 346                 stkinit(offset+1);
 347         increment(set);
 348         while(1)
 349         {
 350                 fp = (struct frame*)sp->stkbase;
 351                 cp  = sp->stkbase + roundof(sizeof(struct frame), STK_ALIGN);
 352                 n = fp->nalias;
 353                 while(n-->0)
 354                 {
 355                         if(loc==fp->aliases[n])
 356                         {
 357                                 loc = cp;
 358                                 break;
 359                         }
 360                 }
 361                 /* see whether <loc> is in current stack frame */
 362                 if(loc>=cp && loc<=sp->stkend)
 363                 {
 364                         if(frames)
 365                                 sfsetbuf(stream,cp,sp->stkend-cp);
 366                         stream->_data = (unsigned char*)(cp + roundof(loc-cp,STK_ALIGN));
 367                         stream->_next = (unsigned char*)loc+offset;
 368                         goto found;
 369                 }
 370                 if(fp->prev)
 371                 {
 372                         sp->stkbase = fp->prev;
 373                         sp->stkend = ((struct frame*)(fp->prev))->end;
 374                         free((void*)fp);
 375                 }
 376                 else
 377                         break;
 378                 frames++;
 379         }
 380         /* set stack back to the beginning */
 381         cp = (char*)(fp+1);
 382         if(frames)
 383                 sfsetbuf(stream,cp,sp->stkend-cp);
 384         else
 385                 stream->_data = stream->_next = (unsigned char*)cp;
 386 found:
 387         return((char*)stream->_data);
 388 }
 389
 390 /*
 391  * allocate <n> bytes on the current stack
 392  */
 393 char *stkalloc(register Sfio_t *stream, register unsigned int n)
 394 {
 395         register unsigned char *old;
 396         if(!init)
 397                 stkinit(n);
 398         increment(alloc);
 399         n = roundof(n,STK_ALIGN);
 400         if(stkleft(stream) <= (int)n && !stkgrow(stream,n))
 401                 return(0);
 402         old = stream->_data;
 403         stream->_data = stream->_next = old+n;
 404         return((char*)old);
 405 }
 406
 407 /*
 408  * begin a new stack word of at least <n> bytes
 409  */
 410 char *_stkseek(register Sfio_t *stream, register unsigned n)
 411 {
 412         if(!init)
 413                 stkinit(n);
 414         increment(seek);
 415         if(stkleft(stream) <= (int)n && !stkgrow(stream,n))
 416                 return(0);
 417         stream->_next = stream->_data+n;
 418         return((char*)stream->_data);
 419 }
 420
 421 /*
 422  * advance the stack to the current top
 423  * if extra is non-zero, first add a extra bytes and zero the first
 424  */
 425 char    *stkfreeze(register Sfio_t *stream, register unsigned extra)
 426 {
 427         register unsigned char *old, *top;
 428         if(!init)
 429                 stkinit(extra);
 430         old = stream->_data;
 431         top = stream->_next;
 432         if(extra)
 433         {
 434                 if(extra > (stream->_endb-stream->_next))
 435                 {
 436                         if (!(top = (unsigned char*)stkgrow(stream,extra)))
 437                                 return(0);
 438                         old = stream->_data;
 439                 }
 440                 *top = 0;
 441                 top += extra;
 442         }
 443         stream->_next = stream->_data += roundof(top-old,STK_ALIGN);
 444         return((char*)old);
 445 }
 446
 447 /*
 448  * copy string <str> onto the stack as a new stack word
 449  */
 450 char    *stkcopy(Sfio_t *stream, const char* str)
 451 {
 452         register unsigned char *cp = (unsigned char*)str;
 453         register int n;
 454         register int off=stktell(stream);
 455         char buff[40], *tp=buff;
 456         if(off)
 457         {
 458                 if(off > sizeof(buff))
 459                 {
 460                         if(!(tp = malloc(off)))
 461                         {
 462                                 struct stk *sp = stream2stk(stream);
 463                                 if(!sp->stkoverflow || !(tp = (*sp->stkoverflow)(off)))
 464                                         return(0);
 465                         }
 466                 }
 467                 memcpy(tp, stream->_data, off);
 468         }
 469         while(*cp++);
 470         n = roundof(cp-(unsigned char*)str,STK_ALIGN);
 471         if(!init)
 472                 stkinit(n);
 473         increment(copy);
 474         if(stkleft(stream) <= n && !stkgrow(stream,n))
 475                 return(0);
 476         strcpy((char*)(cp=stream->_data),str);
 477         stream->_data = stream->_next = cp+n;
 478         if(off)
 479         {
 480                 _stkseek(stream,off);
 481                 memcpy(stream->_data, tp, off);
 482                 if(tp!=buff)
 483                         free((void*)tp);
 484         }
 485         return((char*)cp);
 486 }
 487
 488 /*
 489  * add a new stack frame of size >= <n> to the current stack.
 490  * if <n> > 0, copy the bytes from stkbot to stktop to the new stack
 491  * if <n> is zero, then copy the remainder of the stack frame from stkbot
 492  * to the end is copied into the new stack frame
 493  */
 494
 495 static char *stkgrow(register Sfio_t *stream, unsigned size)
 496 {
 497         register int n = size;
 498         register struct stk *sp = stream2stk(stream);
 499         register struct frame *fp= (struct frame*)sp->stkbase;
 500         register char *cp, *dp=0;
 501         register unsigned m = stktell(stream);
 502         int nn=0;
 503         n += (m + sizeof(struct frame)+1);
 504         if(sp->stkflags&STK_SMALL)
 505 #ifndef USE_REALLOC
 506                 n = roundof(n,STK_FSIZE/16);
 507         else
 508 #endif /* !USE_REALLOC */
 509                 n = roundof(n,STK_FSIZE);
 510         /* see whether current frame can be extended */
 511         if(stkptr(stream,0)==sp->stkbase+sizeof(struct frame))
 512         {
 513                 nn = fp->nalias+1;
 514                 dp=sp->stkbase;
 515                 sp->stkbase = ((struct frame*)dp)->prev;
 516         }
 517         cp = newof(dp, char, n, nn*sizeof(char*));
 518         if(!cp && (!sp->stkoverflow || !(cp = (*sp->stkoverflow)(n))))
 519                 return(0);
 520         increment(grow);
 521         count(addsize,n - (dp?m:0));
 522         if(dp && cp==dp)
 523                 nn--;
 524         fp = (struct frame*)cp;
 525         fp->prev = sp->stkbase;
 526         sp->stkbase = cp;
 527         sp->stkend = fp->end = cp+n;
 528         cp = (char*)(fp+1);
 529         cp = sp->stkbase + roundof((cp-sp->stkbase),STK_ALIGN);
 530         if(fp->nalias=nn)
 531         {
 532                 fp->aliases = (char**)fp->end;
 533                 fp->aliases[nn-1] =  dp + roundof(sizeof(struct frame),STK_ALIGN);
 534         }
 535         if(m && !dp)
 536         {
 537                 memcpy(cp,(char*)stream->_data,m);
 538                 count(movsize,m);
 539         }
 540         sfsetbuf(stream,cp,sp->stkend-cp);
 541         return((char*)(stream->_next = stream->_data+m));
 542 }