1 /*********************************************************************** 2 * * 3 * This software is part of the ast package * 4 * Copyright (c) 1985-2009 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 } 543