1 /*********************************************************************** 2 * * 3 * This software is part of the ast package * 4 * Copyright (c) 1985-2007 AT&T Knowledge Ventures * 5 * and is licensed under the * 6 * Common Public License, Version 1.0 * 7 * by AT&T Knowledge Ventures * 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 * reset the bottom of the current stack back to <loc> 322 * if <loc> is not in this stack, then the stack is reset to the beginning 323 * otherwise, the top of the stack is set to stkbot+<offset> 324 * 325 */ 326 char *stkset(register Sfio_t * stream, register char* loc, unsigned offset) 327 { 328 register struct stk *sp = stream2stk(stream); 329 register char *cp; 330 register struct frame *fp; 331 register int frames = 0; 332 int n; 333 if(!init) 334 stkinit(offset+1); 335 increment(set); 336 while(1) 337 { 338 fp = (struct frame*)sp->stkbase; 339 cp = sp->stkbase + roundof(sizeof(struct frame), STK_ALIGN); 340 n = fp->nalias; 341 while(n-->0) 342 { 343 if(loc==fp->aliases[n]) 344 { 345 loc = cp; 346 break; 347 } 348 } 349 /* see whether <loc> is in current stack frame */ 350 if(loc>=cp && loc<=sp->stkend) 351 { 352 if(frames) 353 sfsetbuf(stream,cp,sp->stkend-cp); 354 stream->_data = (unsigned char*)(cp + roundof(loc-cp,STK_ALIGN)); 355 stream->_next = (unsigned char*)loc+offset; 356 goto found; 357 } 358 if(fp->prev) 359 { 360 sp->stkbase = fp->prev; 361 sp->stkend = ((struct frame*)(fp->prev))->end; 362 free((void*)fp); 363 } 364 else 365 break; 366 frames++; 367 } 368 /* set stack back to the beginning */ 369 cp = (char*)(fp+1); 370 if(frames) 371 sfsetbuf(stream,cp,sp->stkend-cp); 372 else 373 stream->_data = stream->_next = (unsigned char*)cp; 374 found: 375 return((char*)stream->_data); 376 } 377 378 /* 379 * allocate <n> bytes on the current stack 380 */ 381 char *stkalloc(register Sfio_t *stream, register unsigned int n) 382 { 383 register unsigned char *old; 384 if(!init) 385 stkinit(n); 386 increment(alloc); 387 n = roundof(n,STK_ALIGN); 388 if(stkleft(stream) <= (int)n && !stkgrow(stream,n)) 389 return(0); 390 old = stream->_data; 391 stream->_data = stream->_next = old+n; 392 return((char*)old); 393 } 394 395 /* 396 * begin a new stack word of at least <n> bytes 397 */ 398 char *_stkseek(register Sfio_t *stream, register unsigned n) 399 { 400 if(!init) 401 stkinit(n); 402 increment(seek); 403 if(stkleft(stream) <= (int)n && !stkgrow(stream,n)) 404 return(0); 405 stream->_next = stream->_data+n; 406 return((char*)stream->_data); 407 } 408 409 /* 410 * advance the stack to the current top 411 * if extra is non-zero, first add a extra bytes and zero the first 412 */ 413 char *stkfreeze(register Sfio_t *stream, register unsigned extra) 414 { 415 register unsigned char *old, *top; 416 if(!init) 417 stkinit(extra); 418 old = stream->_data; 419 top = stream->_next; 420 if(extra) 421 { 422 if(extra > (stream->_endb-stream->_next)) 423 { 424 if (!(top = (unsigned char*)stkgrow(stream,extra))) 425 return(0); 426 old = stream->_data; 427 } 428 *top = 0; 429 top += extra; 430 } 431 stream->_next = stream->_data += roundof(top-old,STK_ALIGN); 432 return((char*)old); 433 } 434 435 /* 436 * copy string <str> onto the stack as a new stack word 437 */ 438 char *stkcopy(Sfio_t *stream, const char* str) 439 { 440 register unsigned char *cp = (unsigned char*)str; 441 register int n; 442 while(*cp++); 443 n = roundof(cp-(unsigned char*)str,STK_ALIGN); 444 if(!init) 445 stkinit(n); 446 increment(copy); 447 if(stkleft(stream) <= n && !stkgrow(stream,n)) 448 return(0); 449 strcpy((char*)(cp=stream->_data),str); 450 stream->_data = stream->_next = cp+n; 451 return((char*)cp); 452 } 453 454 /* 455 * add a new stack frame of size >= <n> to the current stack. 456 * if <n> > 0, copy the bytes from stkbot to stktop to the new stack 457 * if <n> is zero, then copy the remainder of the stack frame from stkbot 458 * to the end is copied into the new stack frame 459 */ 460 461 static char *stkgrow(register Sfio_t *stream, unsigned size) 462 { 463 register int n = size; 464 register struct stk *sp = stream2stk(stream); 465 register struct frame *fp= (struct frame*)sp->stkbase; 466 register char *cp, *dp=0; 467 register unsigned m = stktell(stream); 468 int nn=0; 469 n += (m + sizeof(struct frame)+1); 470 if(sp->stkflags&STK_SMALL) 471 #ifndef USE_REALLOC 472 n = roundof(n,STK_FSIZE/16); 473 else 474 #endif /* !USE_REALLOC */ 475 n = roundof(n,STK_FSIZE); 476 /* see whether current frame can be extended */ 477 if(stkptr(stream,0)==sp->stkbase+sizeof(struct frame)) 478 { 479 nn = fp->nalias+1; 480 dp=sp->stkbase; 481 sp->stkbase = ((struct frame*)dp)->prev; 482 } 483 cp = newof(dp, char, n, nn*sizeof(char*)); 484 if(!cp && (!sp->stkoverflow || !(cp = (*sp->stkoverflow)(n)))) 485 return(0); 486 increment(grow); 487 count(addsize,n - (dp?m:0)); 488 if(dp && cp==dp) 489 nn--; 490 fp = (struct frame*)cp; 491 fp->prev = sp->stkbase; 492 sp->stkbase = cp; 493 sp->stkend = fp->end = cp+n; 494 cp = (char*)(fp+1); 495 cp = sp->stkbase + roundof((cp-sp->stkbase),STK_ALIGN); 496 if(fp->nalias=nn) 497 { 498 fp->aliases = (char**)fp->end; 499 fp->aliases[nn-1] = dp + roundof(sizeof(struct frame),STK_ALIGN); 500 } 501 if(m && !dp) 502 { 503 memcpy(cp,(char*)stream->_data,m); 504 count(movsize,m); 505 } 506 sfsetbuf(stream,cp,sp->stkend-cp); 507 return((char*)(stream->_next = stream->_data+m)); 508 } 509