1/***********************************************************************
2*                                                                      *
3*               This software is part of the ast package               *
4*          Copyright (c) 1985-2011 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(char*))
57#define STK_HDRSIZE	(sizeof(Sfio_t)+sizeof(Sfdisc_t))
58
59typedef char* (*_stk_overflow_)(int);
60
61static int stkexcept(Sfio_t*,int,void*,Sfdisc_t*);
62static Sfdisc_t stkdisc = { 0, 0, 0, stkexcept };
63
64Sfio_t _Stak_data = SFNEW((char*)0,0,-1,SF_STATIC|SF_WRITE|SF_STRING,&stkdisc,0);
65
66__EXTERN__(Sfio_t, _Stak_data);
67
68struct 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
76struct 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
85static int		init;		/* 1 when initialized */
86static struct stk	*stkcur;	/* pointer to current stk */
87static 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
118static const char Omsg[] = "malloc failed while growing stack\n";
119
120/*
121 * default overflow exception
122 */
123static 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 */
135static 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
144static 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 */
213Sfio_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 */
263Sfio_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 */
297int 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 */
309int 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 */
323int 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 */
338char *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;
386found:
387	return((char*)stream->_data);
388}
389
390/*
391 * allocate <n> bytes on the current stack
392 */
393char *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 */
410char *_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 */
425char	*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 */
450char	*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
495static 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