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 */
overflow(int n)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 */
stkinit(int size)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
stkexcept(register Sfio_t * stream,int type,void * val,Sfdisc_t * dp)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 */
stkopen(int flags)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 */
stkinstall(Sfio_t * stream,_stk_overflow_ oflow)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 */
stklink(register Sfio_t * stream)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 */
stkclose(Sfio_t * stream)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 */
stkon(register Sfio_t * stream,register char * loc)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 */
stkset(register Sfio_t * stream,register char * loc,unsigned offset)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 */
stkalloc(register Sfio_t * stream,register unsigned int n)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 */
_stkseek(register Sfio_t * stream,register unsigned n)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 */
stkfreeze(register Sfio_t * stream,register unsigned extra)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 */
stkcopy(Sfio_t * stream,const char * str)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
stkgrow(register Sfio_t * stream,unsigned size)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