cde/programs/dtksh/ksh93/src/lib/libast/misc/stak.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: stak.c /main/3 1995/11/01 18:05:08 rswiston $ */
  24 /***************************************************************
  25 *                                                              *
  26 *                      AT&T - PROPRIETARY                      *
  27 *                                                              *
  28 *        THIS IS UNPUBLISHED PROPRIETARY SOURCE CODE OF        *
  29 *                    AT&T BELL LABORATORIES                    *
  30 *         AND IS NOT TO BE DISCLOSED OR USED EXCEPT IN         *
  31 *            ACCORDANCE WITH APPLICABLE AGREEMENTS             *
  32 *                                                              *
  33 *          Copyright (c) 1994 AT&T Bell Laboratories           *
  34 *              Unpublished & Not for Publication               *
  35 *                     All Rights Reserved                      *
  36 *                                                              *
  37 *       The copyright notice above does not evidence any       *
  38 *      actual or intended publication of such source code      *
  39 *                                                              *
  40 *               This software was created by the               *
  41 *           Software Engineering Research Department           *
  42 *                    AT&T Bell Laboratories                    *
  43 *                                                              *
  44 *               For further information contact                *
  45 *                   advsoft@research.att.com                   *
  46 *                 Randy Hackbarth 908-582-5245                 *
  47 *                  Dave Belanger 908-582-7427                  *
  48 *                                                              *
  49 ***************************************************************/
  50
  51 /* : : generated by proto : : */
  52
  53 #line 1
  54
  55 #if !defined(__PROTO__)
  56 #if defined(__STDC__) || defined(__cplusplus) || defined(_proto) || defined(c_plusplus)
  57 #if defined(__cplusplus)
  58 #define __MANGLE__      "C"
  59 #else
  60 #define __MANGLE__
  61 #endif
  62 #define __STDARG__
  63 #define __PROTO__(x)    x
  64 #define __OTORP__(x)
  65 #define __PARAM__(n,o)  n
  66 #if !defined(__STDC__) && !defined(__cplusplus)
  67 #if !defined(c_plusplus)
  68 #define const
  69 #endif
  70 #define signed
  71 #define void            int
  72 #define volatile
  73 #define __V_            char
  74 #else
  75 #define __V_            void
  76 #endif
  77 #else
  78 #define __PROTO__(x)    ()
  79 #define __OTORP__(x)    x
  80 #define __PARAM__(n,o)  o
  81 #define __MANGLE__
  82 #define __V_            char
  83 #define const
  84 #define signed
  85 #define void            int
  86 #define volatile
  87 #endif
  88 #if defined(__cplusplus) || defined(c_plusplus)
  89 #define __VARARG__      ...
  90 #else
  91 #define __VARARG__
  92 #endif
  93 #if defined(__STDARG__)
  94 #define __VA_START__(p,a)       va_start(p,a)
  95 #else
  96 #define __VA_START__(p,a)       va_start(p)
  97 #endif
  98 #endif
  99
 100 #line 21
 101 #include        <sfio_t.h>
 102 #include        <ast.h>
 103 #include        <stak.h>
 104
 105 /*
 106  *  A stack is a header and a linked list of frames
 107  *  The first frame has structure
 108  *      Sfile_t
 109  *      Sfdisc_t
 110  *      struct stak
 111  * Frames have structure
 112  *      struct frame
 113  *      data
 114  */
 115 #define STAK_FSIZE      (1024*sizeof(int))
 116 #define STAK_HDRSIZE    (sizeof(Sfile_t)+sizeof(Sfdisc_t))
 117
 118 typedef char* (*_stak_overflow_) __PROTO__((int));
 119
 120 static int stakexcept __PROTO__((Sfile_t*,int,Sfdisc_t*));
 121 static Sfdisc_t stakdisc = { 0, 0, 0, stakexcept };
 122 Sfile_t _Stak_data=SFNEW((char*)0,0,-1,SF_STATIC|SF_WRITE|SF_STRING,&stakdisc);
 123
 124 struct frame
 125 {
 126         char    *prev;  /* address of previous frame */
 127         char    *end;   /* address of end this frame */
 128 };
 129
 130 struct stak
 131 {
 132         _stak_overflow_ stakoverflow;   /* called when malloc fails */
 133         short           stakref;        /* reference count; */
 134         short           stakflags;      /* stack attributes */
 135         char            *stakbase;      /* beginning of current stack frame */
 136         char            *stakend;       /* end of current stack frame */
 137 };
 138
 139 static int              init;           /* 1 when initialized */
 140 static struct stak      *stakcur;       /* pointer to current stak */
 141 static char             *stakgrow __PROTO__((unsigned));
 142
 143 #define stream2stak(stream)     ((struct stak*)(((char*)(stream))+STAK_HDRSIZE))
 144 #define stak2stream(sp)         ((Sfile_t*)(((char*)(sp))-STAK_HDRSIZE))
 145 #define stakleft()              (staksp->endb-staksp->data)
 146
 147
 148 #ifdef STAKSTATS
 149     static struct
 150     {
 151         int     create;
 152         int     delete;
 153         int     install;
 154         int     alloc;
 155         int     copy;
 156         int     puts;
 157         int     seek;
 158         int     set;
 159         int     grow;
 160         int     addsize;
 161         int     delsize;
 162         int     movsize;
 163     } _stakstats;
 164 #   define increment(x) (_stakstats.x++)
 165 #   define count(x,n)   (_stakstats.x += (n))
 166 #else
 167 #   define increment(x)
 168 #   define count(x,n)
 169 #endif /* STAKSTATS */
 170
 171 static const char Omsg[] = "malloc failed while growing stack\n";
 172
 173 /*
 174  * default overflow exception
 175  */
 176 static char *overflow __PARAM__((int n), (n)) __OTORP__(int n;)
 177 #line 97
 178 {
 179         NoP(n);
 180         write(2,Omsg, sizeof(Omsg)-1);
 181         exit(2);
 182         /* NOTREACHED */
 183         return(0);
 184 }
 185
 186 /*
 187  * initialize staksp, sfio operations may have already occcured
 188  */
 189 static void stakinit __PARAM__((int size), (size)) __OTORP__(int size;)
 190 #line 109
 191 {
 192         register Sfile_t *sp;
 193         init = size;
 194         sp = stakcreate(0);
 195         init = 1;
 196         stakinstall(sp,overflow);
 197 }
 198
 199 static int stakexcept __PARAM__((Sfile_t* sp, int type, Sfdisc_t* dp), (sp, type, dp)) __OTORP__(Sfile_t* sp; int type; Sfdisc_t* dp;)
 200 #line 118
 201 {
 202         NoP(dp);
 203         switch(type)
 204         {
 205             case SF_CLOSE:
 206                 return(stakdelete(sp));
 207             case SF_WRITE:
 208             case SF_SEEK:
 209                 if(init)
 210                 {
 211                         Sfile_t *old = 0;
 212                         if(sp!=staksp)
 213                                 old = stakinstall(sp,NiL);
 214                         stakgrow(sfslen()-(staksp->endb-staksp->data));
 215                         if(old)
 216                                 stakinstall(old,NiL);
 217                 }
 218                 else
 219                         stakinit(sfslen());
 220                 return(1);
 221             case SF_NEW:
 222                 return(-1);
 223         }
 224         return(0);
 225 }
 226
 227 /*
 228  * create a stack
 229  */
 230 Sfile_t *stakcreate __PARAM__((int flags), (flags)) __OTORP__(int flags;)
 231 #line 148
 232 {
 233         register int bsize;
 234         register Sfile_t *stream;
 235         register struct stak *sp;
 236         register struct frame *fp;
 237         register Sfdisc_t *dp;
 238         register char *cp;
 239         if(!(stream=newof((char*)0,Sfile_t, 1, sizeof(*dp)+sizeof(*sp))))
 240                 return(0);
 241         increment(create);
 242         count(addsize,sizeof(*stream)+sizeof(*dp)+sizeof(*sp));
 243         dp = (Sfdisc_t*)(stream+1);
 244         dp->exceptf = stakexcept;
 245         sp = (struct stak*)(dp+1);
 246         sp->stakref = 1;
 247         sp->stakflags = (flags&STAK_SMALL);
 248         sp->stakoverflow = stakcur?stakcur->stakoverflow:overflow;
 249         bsize = init+sizeof(struct frame);
 250 #ifndef USE_REALLOC
 251         if(flags&STAK_SMALL)
 252                 bsize = roundof(bsize,STAK_FSIZE/16);
 253         else
 254 #endif /* USE_REALLOC */
 255                 bsize = roundof(bsize,STAK_FSIZE);
 256         bsize -= sizeof(struct frame);
 257         if(!(fp=newof((char*)0,struct frame, 1,bsize)))
 258         {
 259                 free(stream);
 260                 return(0);
 261         }
 262         count(addsize,sizeof(*fp)+bsize);
 263         cp = (char*)(fp+1);
 264         sp->stakbase = (char*)fp;
 265         fp->prev = 0;
 266         fp->end = sp->stakend = cp+bsize;
 267         if(!sfnew(stream,cp,bsize,-1,SF_STRING|SF_WRITE|SF_STATIC|SF_EOF))
 268                 return((Sfile_t*)0);
 269         sfdisc(stream,dp);
 270         return(stream);
 271 }
 272
 273 /*
 274  * return a pointer to the current stack
 275  * if <stream> is not null, it becomes the new current stack
 276  * <oflow> becomes the new overflow function
 277  */
 278 Sfile_t *stakinstall __PARAM__((Sfile_t *stream, _stak_overflow_ oflow), (stream, oflow)) __OTORP__(Sfile_t *stream; _stak_overflow_ oflow;)
 279 #line 195
 280 {
 281         Sfile_t *old;
 282         register struct stak *sp;
 283         if(!init)
 284         {
 285                 stakinit(1);
 286                 if(oflow)
 287                         stakcur->stakoverflow = oflow;
 288                 return((Sfile_t*)0);
 289         }
 290         increment(install);
 291         old = stakcur?stak2stream(stakcur):0;
 292         if(stream)
 293         {
 294                 sp = stream2stak(stream);
 295                 while(sfstack(staksp, SF_POPSTACK));
 296                 if(stream!=staksp)
 297                         sfstack(staksp,stream);
 298                 stakcur = sp;
 299 #ifdef USE_REALLOC
 300                 /*** someday ***/
 301 #endif /* USE_REALLOC */
 302         }
 303         else
 304                 sp = stakcur;
 305         if(oflow)
 306                 sp->stakoverflow = oflow;
 307         return(old);
 308 }
 309
 310 /*
 311  * increase the reference count on the given <stack>
 312  */
 313 int staklink __PARAM__((register Sfile_t* stream), (stream)) __OTORP__(register Sfile_t* stream;)
 314 #line 229
 315 {
 316         register struct stak *sp = stream2stak(stream);
 317         return(sp->stakref++);
 318 }
 319
 320 /*
 321  * terminate a stack and free up the space
 322  */
 323 int stakdelete __PARAM__((Sfile_t* stream), (stream)) __OTORP__(Sfile_t* stream;)
 324 #line 238
 325 {
 326         register struct stak *sp = stream2stak(stream);
 327         register char *cp = sp->stakbase;
 328         register struct frame *fp;
 329         if(--sp->stakref>0)
 330                 return(1);
 331         increment(delete);
 332         if(stream==staksp)
 333                 stakset((char*)0,0);
 334         else while(1)
 335         {
 336                 fp = (struct frame*)cp;
 337                 if(fp->prev)
 338                 {
 339                         cp = fp->prev;
 340                         free(fp);
 341                 }
 342                 else
 343                 {
 344                         free(fp);
 345                         break;
 346                 }
 347         }
 348         return(0);
 349 }
 350
 351 /*
 352  * reset the bottom of the current stack back to <loc>
 353  * if <loc> is not in this stack, then the stack is reset to the beginning
 354  * otherwise, the top of the stack is set to stakbot+<offset>
 355  *
 356  */
 357 char *stakset __PARAM__((register char* loc, unsigned offset), (loc, offset)) __OTORP__(register char* loc; unsigned offset;)
 358 #line 271
 359 {
 360         register struct stak *sp=stakcur;
 361         register char *cp;
 362         register struct frame *fp;
 363         register int frames = 0;
 364         if(!init)
 365                 stakinit(offset+1);
 366         increment(set);
 367         while(1)
 368         {
 369                 /* see whether <loc> is in current stack frame */
 370                 if(loc>=(cp=sp->stakbase) && loc<=sp->stakend)
 371                 {
 372                         cp += sizeof(struct frame);
 373                         if(frames)
 374                                 sfsetbuf(staksp,cp,sp->stakend-cp);
 375                         staksp->data = (unsigned char*)(cp + roundof(loc-cp,sizeof(char*)));
 376                         staksp->next = (unsigned char*)loc+offset;
 377                         goto found;
 378                 }
 379                 fp = (struct frame*)cp;
 380                 if(fp->prev)
 381                 {
 382                         sp->stakbase = fp->prev;
 383                         sp->stakend = ((struct frame*)(fp->prev))->end;
 384                         free(cp);
 385                 }
 386                 else
 387                         break;
 388                 frames++;
 389         }
 390         /* set stack back to the beginning */
 391         cp = (char*)(fp+1);
 392         if(frames)
 393                 sfsetbuf(staksp,cp,sp->stakend-cp);
 394         else
 395                 staksp->data = staksp->next = (unsigned char*)cp;
 396 found:
 397         return((char*)staksp->data);
 398 }
 399
 400 /*
 401  * allocate <n> bytes on the current stack
 402  */
 403 char *stakalloc __PARAM__((register unsigned int n), (n)) __OTORP__(register unsigned int n;)
 404 #line 316
 405 {
 406         register unsigned char *old;
 407         if(!init)
 408                 stakinit(n);
 409         increment(alloc);
 410         n = roundof(n,sizeof(char*));
 411         if(stakleft() <= (int)n)
 412                 stakgrow(n);
 413         old = staksp->data;
 414         staksp->data = staksp->next = old+n;
 415         return((char*)old);
 416 }
 417
 418 /*
 419  * begin a new stack word of at least <n> bytes
 420  */
 421 char *_stakseek __PARAM__((register unsigned n), (n)) __OTORP__(register unsigned n;)
 422 #line 333
 423 {
 424         if(!init)
 425                 stakinit(n);
 426         increment(seek);
 427         if(stakleft() <= (int)n)
 428                 stakgrow(n);
 429         staksp->next = staksp->data+n;
 430         return((char*)staksp->data);
 431 }
 432
 433 /*
 434  * advance the stack to the current top
 435  * if extra is non-zero, first add a extra bytes and zero the first
 436  */
 437 char    *stakfreeze __PARAM__((register unsigned extra), (extra)) __OTORP__(register unsigned extra;)
 438 #line 348
 439 {
 440         register unsigned char *old, *top;
 441         if(!init)
 442                 stakinit(extra);
 443         old = staksp->data;
 444         top = staksp->next;
 445         if(extra)
 446         {
 447                 if(extra > (staksp->endb-staksp->next))
 448                 {
 449                         top = (unsigned char*)stakgrow(extra);
 450                         old = staksp->data;
 451                 }
 452                 *top = 0;
 453                 top += extra;
 454         }
 455         staksp->next = staksp->data += roundof(top-old,sizeof(char*));
 456         return((char*)old);
 457 }
 458
 459 /*
 460  * copy string <str> onto the stack as a new stack word
 461  */
 462 char    *stakcopy __PARAM__((const char* str), (str)) __OTORP__(const char* str;)
 463 #line 372
 464 {
 465         register unsigned char *cp = (unsigned char*)str;
 466         register int n;
 467         while(*cp++);
 468         n = roundof(cp-(unsigned char*)str,sizeof(char*));
 469         if(!init)
 470                 stakinit(n);
 471         increment(copy);
 472         if(stakleft() <= n)
 473                 stakgrow(n);
 474         strcpy((char*)(cp=staksp->data),str);
 475         staksp->data = staksp->next = cp+n;
 476         return((char*)cp);
 477 }
 478
 479 /*
 480  * add a new stack frame of size >= <n> to the current stack.
 481  * if <n> > 0, copy the bytes from stakbot to staktop to the new stack
 482  * if <n> is zero, then copy the remainder of the stack frame from stakbot
 483  * to the end is copied into the new stack frame
 484  */
 485
 486 static char *stakgrow __PARAM__((unsigned size), (size)) __OTORP__(unsigned size;)
 487 #line 395
 488 {
 489         register int n = size;
 490         register struct stak *sp = stakcur;
 491         register struct frame *fp;
 492         register char *cp;
 493         register unsigned m = staktell();
 494         register int reused = 0;
 495         n += (m + sizeof(struct frame)+1);
 496         if(sp->stakflags&STAK_SMALL)
 497 #ifndef USE_REALLOC
 498                 n = roundof(n,STAK_FSIZE/16);
 499         else
 500 #endif /* !USE_REALLOC */
 501                 n = roundof(n,STAK_FSIZE);
 502         /* see whether current frame can be extended */
 503         if((char*)(staksp->data) == sp->stakbase+sizeof(struct frame))
 504         {
 505                 cp = newof(sp->stakbase,char,n,0);
 506                 reused++;
 507         }
 508         else
 509                 cp = newof((char*)0, char, n, 0);
 510         if(!cp) cp = (*sp->stakoverflow)(n);
 511         increment(grow);
 512         count(addsize,n);
 513         fp = (struct frame*)cp;
 514         if(!reused)
 515         {
 516                 fp->prev = sp->stakbase;
 517         }
 518         sp->stakbase = cp;
 519         sp->stakend = fp->end = cp+n;
 520         cp = (char*)(fp+1);
 521         if(m && !reused)
 522                 memcpy(cp,(char*)staksp->data,m);
 523         count(movsize,m);
 524         sfsetbuf(staksp,cp,sp->stakend-cp);
 525         return((char*)(staksp->next = staksp->data+m));
 526 }
 527