cde/programs/dtksh/ksh93/src/lib/libast/misc/stk.c

   1 /*
   2  * CDE - Common Desktop Environment
   3  *
   4  * Copyright (c) 1993-2012, The Open Group. All rights reserved.
   5  *
   6  * These libraries and programs are free software; you can
   7  * redistribute them and/or modify them under the terms of the GNU
   8  * Lesser General Public License as published by the Free Software
   9  * Foundation; either version 2 of the License, or (at your option)
  10  * any later version.
  11  *
  12  * These libraries and programs are distributed in the hope that
  13  * they will be useful, but WITHOUT ANY WARRANTY; without even the
  14  * implied warranty of MERCHANTABILITY or FITNESS FOR A PARTICULAR
  15  * PURPOSE. See the GNU Lesser General Public License for more
  16  * details.
  17  *
  18  * You should have received a copy of the GNU Lesser General Public
  19  * License along with these librararies and programs; if not, write
  20  * to the Free Software Foundation, Inc., 51 Franklin Street, Fifth
  21  * Floor, Boston, MA 02110-1301 USA
  22  */
  23 /* $XConsortium: stk.c /main/2 1996/05/08 19:45:44 drk $ */
  24 /***************************************************************
  25 *                                                              *
  26 *                      AT&T - PROPRIETARY                      *
  27 *                                                              *
  28 *         THIS IS PROPRIETARY SOURCE CODE LICENSED BY          *
  29 *                          AT&T CORP.                          *
  30 *                                                              *
  31 *                Copyright (c) 1995 AT&T Corp.                 *
  32 *                     All Rights Reserved                      *
  33 *                                                              *
  34 *           This software is licensed by AT&T Corp.            *
  35 *       under the terms and conditions of the license in       *
  36 *       http://www.research.att.com/orgs/ssr/book/reuse        *
  37 *                                                              *
  38 *               This software was created by the               *
  39 *           Software Engineering Research Department           *
  40 *                    AT&T Bell Laboratories                    *
  41 *                                                              *
  42 *               For further information contact                *
  43 *                     gsf@research.att.com                     *
  44 *                                                              *
  45 ***************************************************************/
  46
  47 /* : : generated by proto : : */
  48
  49 #if !defined(__PROTO__)
  50 #if defined(__STDC__) || defined(__cplusplus) || defined(_proto) || defined(c_plusplus)
  51 #if defined(__cplusplus)
  52 #define __MANGLE__      "C"
  53 #else
  54 #define __MANGLE__
  55 #endif
  56 #define __STDARG__
  57 #define __PROTO__(x)    x
  58 #define __OTORP__(x)
  59 #define __PARAM__(n,o)  n
  60 #if !defined(__STDC__) && !defined(__cplusplus)
  61 #if !defined(c_plusplus)
  62 #define const
  63 #endif
  64 #define signed
  65 #define void            int
  66 #define volatile
  67 #define __V_            char
  68 #else
  69 #define __V_            void
  70 #endif
  71 #else
  72 #define __PROTO__(x)    ()
  73 #define __OTORP__(x)    x
  74 #define __PARAM__(n,o)  o
  75 #define __MANGLE__
  76 #define __V_            char
  77 #define const
  78 #define signed
  79 #define void            int
  80 #define volatile
  81 #endif
  82 #if defined(__cplusplus) || defined(c_plusplus)
  83 #define __VARARG__      ...
  84 #else
  85 #define __VARARG__
  86 #endif
  87 #if defined(__STDARG__)
  88 #define __VA_START__(p,a)       va_start(p,a)
  89 #else
  90 #define __VA_START__(p,a)       va_start(p)
  91 #endif
  92 #endif
  93 #include        <sfio_t.h>
  94 #include        <ast.h>
  95 #include        <stk.h>
  96
  97 /*
  98  *  A stack is a header and a linked list of frames
  99  *  The first frame has structure
 100  *      Sfio_t
 101  *      Sfdisc_t
 102  *      struct stk
 103  * Frames have structure
 104  *      struct frame
 105  *      data
 106  */
 107 #define STK_FSIZE       (1024*sizeof(int))
 108 #define STK_HDRSIZE     (sizeof(Sfio_t)+sizeof(Sfdisc_t))
 109
 110 typedef char* (*_stk_overflow_) __PROTO__((int));
 111
 112 static int stkexcept __PROTO__((Sfio_t*,int,Sfdisc_t*));
 113 static Sfdisc_t stkdisc = { 0, 0, 0, stkexcept };
 114
 115 #if _DLL_INDIRECT_DATA && !_DLL
 116 static Sfio_t _Stk_data_data =
 117 #else
 118 Sfio_t _Stk_data =
 119 #endif
 120
 121 SFNEW((char*)0,0,-1,SF_STATIC|SF_WRITE|SF_STRING,&stkdisc);
 122
 123 #if _DLL_INDIRECT_DATA && !_DLL
 124 Sfio_t _Stk_data = &_Stk_data_data;
 125 #endif
 126
 127 struct frame
 128 {
 129         char    *prev;  /* address of previous frame */
 130         char    *end;   /* address of end this frame */
 131 };
 132
 133 struct stk
 134 {
 135         _stk_overflow_  stkoverflow;    /* called when malloc fails */
 136         short           stkref; /* reference count; */
 137         short           stkflags;       /* stack attributes */
 138         char            *stkbase;       /* beginning of current stack frame */
 139         char            *stkend;        /* end of current stack frame */
 140 };
 141
 142 static int              init;           /* 1 when initialized */
 143 static struct stk       *stkcur;        /* pointer to current stk */
 144 static char             *stkgrow __PROTO__((Sfio_t*, unsigned));
 145
 146 #define stream2stk(stream)      ((stream)==stkstd? stkcur:\
 147                                  ((struct stk*)(((char*)(stream))+STK_HDRSIZE)))
 148 #define stk2stream(sp)          ((Sfio_t*)(((char*)(sp))-STK_HDRSIZE))
 149 #define stkleft(stream)         ((stream)->endb-(stream)->data)
 150
 151
 152 #ifdef STKSTATS
 153     static struct
 154     {
 155         int     create;
 156         int     delete;
 157         int     install;
 158         int     alloc;
 159         int     copy;
 160         int     puts;
 161         int     seek;
 162         int     set;
 163         int     grow;
 164         int     addsize;
 165         int     delsize;
 166         int     movsize;
 167     } _stkstats;
 168 #   define increment(x) (_stkstats.x++)
 169 #   define count(x,n)   (_stkstats.x += (n))
 170 #else
 171 #   define increment(x)
 172 #   define count(x,n)
 173 #endif /* STKSTATS */
 174
 175 static const char Omsg[] = "malloc failed while growing stack\n";
 176
 177 /*
 178  * default overflow exception
 179  */
 180 static char *overflow __PARAM__((int n), (n)) __OTORP__(int n;){
 181         NoP(n);
 182         write(2,Omsg, sizeof(Omsg)-1);
 183         exit(2);
 184         /* NOTREACHED */
 185         return(0);
 186 }
 187
 188 /*
 189  * initialize stkstd, sfio operations may have already occcured
 190  */
 191 static void stkinit __PARAM__((int size), (size)) __OTORP__(int size;){
 192         register Sfio_t *sp;
 193         init = size;
 194         sp = stkopen(0);
 195         init = 1;
 196         stkinstall(sp,overflow);
 197 }
 198
 199 static int stkexcept __PARAM__((register Sfio_t *stream, int type, Sfdisc_t* dp), (stream, type, dp)) __OTORP__(register Sfio_t *stream; int type; Sfdisc_t* dp;){
 200         NoP(dp);
 201         switch(type)
 202         {
 203             case SF_CLOSE:
 204                 return(stkclose(stream));
 205             case SF_WRITE:
 206             case SF_SEEK:
 207                 if(init)
 208                 {
 209                         Sfio_t *old = 0;
 210                         if(stream!=stkstd)
 211                                 old = stkinstall(stream,NiL);
 212                         stkgrow(stkstd,sfslen()-(stkstd->endb-stkstd->data));
 213                         if(old)
 214                                 stkinstall(old,NiL);
 215                 }
 216                 else
 217                         stkinit(sfslen());
 218                 return(1);
 219             case SF_NEW:
 220                 return(-1);
 221         }
 222         return(0);
 223 }
 224
 225 /*
 226  * create a stack
 227  */
 228 Sfio_t *stkopen __PARAM__((int flags), (flags)) __OTORP__(int flags;){
 229         register int bsize;
 230         register Sfio_t *stream;
 231         register struct stk *sp;
 232         register struct frame *fp;
 233         register Sfdisc_t *dp;
 234         register char *cp;
 235         if(!(stream=newof((char*)0,Sfio_t, 1, sizeof(*dp)+sizeof(*sp))))
 236                 return(0);
 237         increment(create);
 238         count(addsize,sizeof(*stream)+sizeof(*dp)+sizeof(*sp));
 239         dp = (Sfdisc_t*)(stream+1);
 240         dp->exceptf = stkexcept;
 241         sp = (struct stk*)(dp+1);
 242         sp->stkref = 1;
 243         sp->stkflags = (flags&STK_SMALL);
 244         sp->stkoverflow = stkcur?stkcur->stkoverflow:overflow;
 245         bsize = init+sizeof(struct frame);
 246 #ifndef USE_REALLOC
 247         if(flags&STK_SMALL)
 248                 bsize = roundof(bsize,STK_FSIZE/16);
 249         else
 250 #endif /* USE_REALLOC */
 251                 bsize = roundof(bsize,STK_FSIZE);
 252         bsize -= sizeof(struct frame);
 253         if(!(fp=newof((char*)0,struct frame, 1,bsize)))
 254         {
 255                 free(stream);
 256                 return(0);
 257         }
 258         count(addsize,sizeof(*fp)+bsize);
 259         cp = (char*)(fp+1);
 260         sp->stkbase = (char*)fp;
 261         fp->prev = 0;
 262         fp->end = sp->stkend = cp+bsize;
 263         if(!sfnew(stream,cp,bsize,-1,SF_STRING|SF_WRITE|SF_STATIC|SF_EOF))
 264                 return((Sfio_t*)0);
 265         sfdisc(stream,dp);
 266         return(stream);
 267 }
 268
 269 /*
 270  * return a pointer to the current stack
 271  * if <stream> is not null, it becomes the new current stack
 272  * <oflow> becomes the new overflow function
 273  */
 274 Sfio_t *stkinstall __PARAM__((Sfio_t *stream, _stk_overflow_ oflow), (stream, oflow)) __OTORP__(Sfio_t *stream; _stk_overflow_ oflow;){
 275         Sfio_t *old;
 276         register struct stk *sp;
 277         if(!init)
 278         {
 279                 stkinit(1);
 280                 if(oflow)
 281                         stkcur->stkoverflow = oflow;
 282                 return((Sfio_t*)0);
 283         }
 284         increment(install);
 285         old = stkcur?stk2stream(stkcur):0;
 286         if(stream)
 287         {
 288                 sp = stream2stk(stream);
 289                 while(sfstack(stkstd, SF_POPSTACK));
 290                 if(stream!=stkstd)
 291                         sfstack(stkstd,stream);
 292                 stkcur = sp;
 293 #ifdef USE_REALLOC
 294                 /*** someday ***/
 295 #endif /* USE_REALLOC */
 296         }
 297         else
 298                 sp = stkcur;
 299         if(oflow)
 300                 sp->stkoverflow = oflow;
 301         return(old);
 302 }
 303
 304 /*
 305  * increase the reference count on the given <stack>
 306  */
 307 int stklink __PARAM__((register Sfio_t* stream), (stream)) __OTORP__(register Sfio_t* stream;){
 308         register struct stk *sp = stream2stk(stream);
 309         return(sp->stkref++);
 310 }
 311
 312 /*
 313  * terminate a stack and free up the space
 314  */
 315 int stkclose __PARAM__((Sfio_t* stream), (stream)) __OTORP__(Sfio_t* stream;){
 316         register struct stk *sp = stream2stk(stream);
 317         register char *cp = sp->stkbase;
 318         register struct frame *fp;
 319         if(--sp->stkref>0)
 320                 return(1);
 321         increment(delete);
 322         if(stream==stkstd)
 323                 stkset(stream,(char*)0,0);
 324         else while(1)
 325         {
 326                 fp = (struct frame*)cp;
 327                 if(fp->prev)
 328                 {
 329                         cp = fp->prev;
 330                         free(fp);
 331                 }
 332                 else
 333                 {
 334                         free(fp);
 335                         break;
 336                 }
 337         }
 338         return(0);
 339 }
 340
 341 /*
 342  * reset the bottom of the current stack back to <loc>
 343  * if <loc> is not in this stack, then the stack is reset to the beginning
 344  * otherwise, the top of the stack is set to stkbot+<offset>
 345  *
 346  */
 347 char *stkset __PARAM__((register Sfio_t * stream, register char* loc, unsigned offset), (stream, loc, offset)) __OTORP__(register Sfio_t * stream; register char* loc; unsigned offset;){
 348         register struct stk *sp = stream2stk(stream);
 349         register char *cp;
 350         register struct frame *fp;
 351         register int frames = 0;
 352         if(!init)
 353                 stkinit(offset+1);
 354         increment(set);
 355         while(1)
 356         {
 357                 /* see whether <loc> is in current stack frame */
 358                 if(loc>=(cp=sp->stkbase) && loc<=sp->stkend)
 359                 {
 360                         cp += sizeof(struct frame);
 361                         if(frames)
 362                                 sfsetbuf(stream,cp,sp->stkend-cp);
 363                         stream->data = (unsigned char*)(cp + roundof(loc-cp,sizeof(char*)));
 364                         stream->next = (unsigned char*)loc+offset;
 365                         goto found;
 366                 }
 367                 fp = (struct frame*)cp;
 368                 if(fp->prev)
 369                 {
 370                         sp->stkbase = fp->prev;
 371                         sp->stkend = ((struct frame*)(fp->prev))->end;
 372                         free(cp);
 373                 }
 374                 else
 375                         break;
 376                 frames++;
 377         }
 378         /* set stack back to the beginning */
 379         cp = (char*)(fp+1);
 380         if(frames)
 381                 sfsetbuf(stream,cp,sp->stkend-cp);
 382         else
 383                 stream->data = stream->next = (unsigned char*)cp;
 384 found:
 385         return((char*)stream->data);
 386 }
 387
 388 /*
 389  * allocate <n> bytes on the current stack
 390  */
 391 char *stkalloc __PARAM__((register Sfio_t *stream, register unsigned int n), (stream, n)) __OTORP__(register Sfio_t *stream; register unsigned int n;){
 392         register unsigned char *old;
 393         if(!init)
 394                 stkinit(n);
 395         increment(alloc);
 396         n = roundof(n,sizeof(char*));
 397         if(stkleft(stream) <= (int)n)
 398                 stkgrow(stream,n);
 399         old = stream->data;
 400         stream->data = stream->next = old+n;
 401         return((char*)old);
 402 }
 403
 404 /*
 405  * begin a new stack word of at least <n> bytes
 406  */
 407 char *_stkseek __PARAM__((register Sfio_t *stream, register unsigned n), (stream, n)) __OTORP__(register Sfio_t *stream; register unsigned n;){
 408         if(!init)
 409                 stkinit(n);
 410         increment(seek);
 411         if(stkleft(stream) <= (int)n)
 412                 stkgrow(stream,n);
 413         stream->next = stream->data+n;
 414         return((char*)stream->data);
 415 }
 416
 417 /*
 418  * advance the stack to the current top
 419  * if extra is non-zero, first add a extra bytes and zero the first
 420  */
 421 char    *stkfreeze __PARAM__((register Sfio_t *stream, register unsigned extra), (stream, extra)) __OTORP__(register Sfio_t *stream; register unsigned extra;){
 422         register unsigned char *old, *top;
 423         if(!init)
 424                 stkinit(extra);
 425         old = stream->data;
 426         top = stream->next;
 427         if(extra)
 428         {
 429                 if(extra > (stream->endb-stream->next))
 430                 {
 431                         top = (unsigned char*)stkgrow(stream,extra);
 432                         old = stream->data;
 433                 }
 434                 *top = 0;
 435                 top += extra;
 436         }
 437         stream->next = stream->data += roundof(top-old,sizeof(char*));
 438         return((char*)old);
 439 }
 440
 441 /*
 442  * copy string <str> onto the stack as a new stack word
 443  */
 444 char    *stkcopy __PARAM__((Sfio_t *stream, const char* str), (stream, str)) __OTORP__(Sfio_t *stream; const char* str;){
 445         register unsigned char *cp = (unsigned char*)str;
 446         register int n;
 447         while(*cp++);
 448         n = roundof(cp-(unsigned char*)str,sizeof(char*));
 449         if(!init)
 450                 stkinit(n);
 451         increment(copy);
 452         if(stkleft(stream) <= n)
 453                 stkgrow(stream,n);
 454         strcpy((char*)(cp=stream->data),str);
 455         stream->data = stream->next = cp+n;
 456         return((char*)cp);
 457 }
 458
 459 /*
 460  * add a new stack frame of size >= <n> to the current stack.
 461  * if <n> > 0, copy the bytes from stkbot to stktop to the new stack
 462  * if <n> is zero, then copy the remainder of the stack frame from stkbot
 463  * to the end is copied into the new stack frame
 464  */
 465
 466 static char *stkgrow __PARAM__((register Sfio_t *stream, unsigned size), (stream, size)) __OTORP__(register Sfio_t *stream; unsigned size;){
 467         register int n = size;
 468         register struct stk *sp = stream2stk(stream);
 469         register struct frame *fp;
 470         register char *cp;
 471         register unsigned m = stktell(stream);
 472         register int reused = 0;
 473         n += (m + sizeof(struct frame)+1);
 474         if(sp->stkflags&STK_SMALL)
 475 #ifndef USE_REALLOC
 476                 n = roundof(n,STK_FSIZE/16);
 477         else
 478 #endif /* !USE_REALLOC */
 479                 n = roundof(n,STK_FSIZE);
 480         /* see whether current frame can be extended */
 481         if((char*)(stream->data) == sp->stkbase+sizeof(struct frame))
 482         {
 483                 cp = newof(sp->stkbase,char,n,0);
 484                 reused++;
 485         }
 486         else
 487                 cp = newof((char*)0, char, n, 0);
 488         if(!cp) cp = (*sp->stkoverflow)(n);
 489         increment(grow);
 490         count(addsize,n);
 491         fp = (struct frame*)cp;
 492         if(!reused)
 493         {
 494                 fp->prev = sp->stkbase;
 495         }
 496         sp->stkbase = cp;
 497         sp->stkend = fp->end = cp+n;
 498         cp = (char*)(fp+1);
 499         if(m && !reused)
 500                 memcpy(cp,(char*)stream->data,m);
 501         count(movsize,m);
 502         sfsetbuf(stream,cp,sp->stkend-cp);
 503         return((char*)(stream->next = stream->data+m));
 504 }
 505