/* replaces @(#)stak.c	1.4 */

/*
 * UNIX shell
 *
 * Stacked-storage allocation.
 * 
 * Maintains a linked stack (of mostly character strings), the top (most
 * recently allocated item) of which is a growing string, which pushstak()
 * inserts into and grows as needed.
 *
 * Each item on the stack consists of a pointer to the previous item
 * (the "stakbsy" pointer; stakbsy points to the top item on the stack), an
 * optional magic number, and the data.  There may be malloc overhead storage
 * on top of this.
 *
 * Pointers returned by these routines point to the first byte of the data
 * in a stack item; users of this module should be unaware of the "stakbsy"
 * pointer and the magic number.  To confuse matters, stakbsy points to the
 * "stakbsy" linked list pointer of the top item on the stack, and the
 * "stakbsy" linked list pointers each point to the corresponding pointer
 * in the next item on the stack.  This all comes to a head in tdystak().
 * 
 * Geoff Collyer
 */

/* see also stak.h */

#include "defs.h"

#undef free				/* refer to free(3) here */

#define STMAGICNUM 0x1235		/* stak item magic */
#define HPMAGICNUM 0x4276		/* heap item magic */
#define MAGICSIZE BYTESPERWORD		/* was once zero */

extern char *malloc(), *realloc();

/* forwards */
char *stalloc(), *growstak(), *getstak();

unsigned brkincr = BRKINCR;		/* used in stak.h only */

static char *
tossgrowing()				/* free the growing stack */
{
	if (stakbsy != 0) {		/* any growing stack? */
		register struct blk *nextitem;

		/* verify magic before freeing */
		if (((int *)Rcheat(stakbsy))[1] != STMAGICNUM)
			error("tossgrowing: bad magic on stack");
		((int *)Rcheat(stakbsy))[1] = 0;	/* erase magic */

		/* about to free the ptr to next, so copy it first */
		nextitem = stakbsy->word;
#ifdef TRACEMEM
		prs("tossgrowing freeing ");
		prn((int)stakbsy);
		prs("\n");
#endif						/* TRACEMEM */
		free((char *)Rcheat(stakbsy));
		stakbsy = nextitem;
	}
}

static char *
stalloc(asize)			/* allocate requested stack space (no frills) */
int asize;
{
	register char *newstack;
	register int size = asize;

#ifdef TRACEMEM
	prs("stalloc allocating ");
	prn(sizeof(struct blk) + MAGICSIZE + size);
	prs(" bytes ");
#endif							/* TRACEMEM */
	newstack = malloc((unsigned)(sizeof(struct blk) + MAGICSIZE + size));
	if (newstack == 0)
		error(nostack);

#ifdef TRACEMEM
	prs("@ ");
	prn((int)newstack);
	prs("\n");
#endif							/* TRACEMEM */
	/* stack this item */
	*((struct blk **)Rcheat(newstack)) = stakbsy;	/* point back at old stack top */
	stakbsy = (struct blk *)Rcheat(newstack);	/* make this new stack top */
	newstack += sizeof(struct blk);			/* point at the data */

	/* add magic number for verification */
	*((int *)Rcheat(newstack)) = STMAGICNUM;
	newstack += MAGICSIZE;

	return newstack;
}

static char *
grostalloc()			/* allocate growing stack */
{
	register int size = BRKINCR;

	/* fiddle global variables to point into this (growing) stack */
	staktop = stakbot = stakbas = stalloc(size);
	stakend = stakbas + size - 1;
}

/*
 * allocate requested stack.
 * staknam() assumes that getstak just realloc's the growing stack,
 * so we must do just that.  Grump.
 */
char *
getstak(asize)
int asize;
{
	register char *newstack;
	register int staklen;

	/* + 1 is because stakend points at the last byte of the growing stack */
	staklen = stakend + 1 - stakbas;	/* # of usable bytes */
#ifdef TRACEMEM
	prs("getstak(");
	prn(asize);
	prs(") calling growstak(");
	prnn(asize - staklen);
	prs("):\n");
#endif						/* TRACEMEM */
	newstack = growstak(asize - staklen);	/* grow growing stack to requested size */
	grostalloc();				/* allocate new growing stack */
	return newstack;
}

#ifdef TRACEMEM
prnn(i)
int i;
{
	if (i < 0) {
		prs("-");
		i = -i;
	}
	prn(i);
}
#endif				/* TRACEMEM */

/*
 * set up stack for local use (i.e. make it big).
 * should be followed by `endstak'
 */
char *
locstak()
{
	if (stakend + 1 - stakbot < BRKINCR) {
#ifdef TRACEMEM
		prs("locstak calling growstak(");
		prnn(BRKINCR - (stakend + 1 - stakbot));
		prs("):\n");
#endif						/* TRACEMEM */
		(void) growstak(BRKINCR - (stakend + 1 - stakbot));
	}
	return stakbot;
}

/*
 * return an address to be used by tdystak later,
 * so it must be returned by getstak because it may not be
 * a part of the growing stack, which is subject to moving.
 */
char *
savstak()
{
	assert(staktop == stakbot);	/* assert empty stack */
	return getstak(1);
}

/*
 * tidy up after `locstak'.
 * make the current growing stack a semi-permanent item and
 * generate a new tiny growing stack.
 */
char *
endstak(argp)
register char *argp;
{
	register char *oldstak;

	*argp++ = 0;				/* terminate the string */
#ifdef TRACEMEM
	prs("endstak calling growstak(");
	prnn(-(stakend + 1 - argp));
	prs("):\n");
#endif						/* TRACEMEM */
	oldstak = growstak(-(stakend + 1 - argp));	/* reduce growing stack size */
	grostalloc();				/* alloc. new growing stack */
	return oldstak;				/* perm. addr. of old item */
}

/*
 * Try to bring the "stack" back to sav,
 * and bring iotemp's stack back to iosav.
 */
tdystak(sav, iosav)
register char *sav;		/* returned by growstak(): points at data */
register struct ionod *iosav;	/* an old copy of iotemp (may be zero) */
{
	rmtemp(iosav);				/* pop temp files */
#ifdef DEBUGSTAK
	if (sav == 0)
		prs("tdystak(0)\n");
	else if (((int *)Rcheat(sav))[-1] == STMAGICNUM) {	/* sav -> data */
		prs("tdystak(data ptr: ");
		prn((int)sav);
		prs(")\n");
	} else {
		prs("tdystak(garbage: ");
		prn((int)sav);
		prs(")\n");
	}
#endif						/* DEBUGSTAK */
	if (sav != 0 && ((int *)Rcheat(sav))[-1] != STMAGICNUM)	/* sav -> data */
		error("tdystak: bad magic in argument");

	/*
	 * pop stack to sav (if zero, pop everything).
	 * sav is a pointer to data, not magic nor stakbsy link.
	 * stakbsy points at the ptr before the data & magic.
	 */
	while (stakbsy != 0 && (sav == 0 ||
	    (char *)stakbsy != sav - sizeof(struct blk) - MAGICSIZE)) {
#ifdef DEBUGSTAK
		debugsav(sav);
#endif						/* DEBUGSTAK */
		tossgrowing();			/* toss the stack top */
	}
#ifdef DEBUGSTAK
	debugsav(sav);
	prs("tdystak: exit\n");
#endif						/* DEBUGSTAK */
	grostalloc();				/* new growing stack */
}

#ifdef DEBUGSTAK
static
debugsav(sav)
char *sav;
{
	if (stakbsy == 0)
		prs("tdystak: stakbsy == 0\n");
	else if (sav != 0 &&
	    (char *)stakbsy == sav - sizeof(struct blk) - MAGICSIZE) {
		prs("tdystak: stakbsy == link ptr of arg: ");
		prn((int)stakbsy);
		prs("\n");
	} else {
		prs("tdystak: stakbsy == link ptr of item above arg: ");
		prn((int)stakbsy);
		prs("\n");
	}
}
#endif /* DEBUGSTAK */

stakchk()			/* reduce growing-stack size if feasible */
{
	if (stakend - staktop > 2*BRKINCR) {	/* lots of unused stack headroom */
#ifdef TRACEMEM
		prs("stakchk calling growstak(");
		prnn(-(stakend - staktop - BRKINCR));
		prs("):\n");
#endif						/* TRACEMEM */
		(void) growstak(-(stakend - staktop - BRKINCR));
	}
}

char *			/* address of copy of newstak */
cpystak(newstak)
char *newstak;
{
	return strcpy(getstak(strlen(newstak) + 1), newstak);
}

char *			/* new address of grown stak */
growstak(incr)		/* grow the growing stack by incr */
int incr;
{
	register char *oldbsy;
	unsigned topoff, botoff, basoff;
	int staklen;

	if (stakbsy == 0)			/* paranoia */
		grostalloc();			/* make a trivial stack */

	/* paranoia: during realloc, point at previous item in case of signals */
	oldbsy = (char *)stakbsy;
	stakbsy = stakbsy->word;

	topoff = staktop - oldbsy;
	botoff = stakbot - oldbsy;
	basoff = stakbas - oldbsy;

	/* + 1 is because stakend points at the last byte of the growing stack */
	staklen = stakend + 1 + incr - oldbsy;

	if (staklen <= sizeof(struct blk) + MAGICSIZE)	/* paranoia */
		staklen = sizeof(struct blk) + MAGICSIZE;

#ifdef TRACEMEM
	prs("growstak growing ");
	prn((int)oldbsy);
	prs(" from ");
	prn(stakend + 1 - oldbsy);
	prs(" bytes; ");
#endif							/* TRACEMEM */
	if (incr < 0) {
		/*
		 * V7 realloc wastes the memory given back when
		 * asked to shrink a block, so we malloc new space
		 * and copy into it in the hope of later reusing the old
		 * space, then free the old space.
		 */
		register char *new = malloc((unsigned)staklen);

		if (new == NIL)
			error(nostack);
		(void) memcpy(new, oldbsy, staklen);
		free(oldbsy);
		oldbsy = new;
	} else {
		/* get realloc to grow the stack to match the stack top */
		if ((oldbsy = realloc(oldbsy, (unsigned)staklen)) == NIL)
			error(nostack);
	}
#ifdef TRACEMEM
	prs("now @ ");
	prn((int)oldbsy);
	prs(" of ");
	prn(staklen);
	prs(" bytes (");
	if (incr < 0) {
		prn(-incr);
		prs(" smaller");
	} else {
		prn(incr);
		prs(" bigger");
	}
	prs(")\n");
#endif						/* TRACEMEM */
	stakend = oldbsy + staklen - 1;		/* see? points at the last byte */
	staktop = oldbsy + topoff;
	stakbot = oldbsy + botoff;
	stakbas = oldbsy + basoff;

	/* restore stakbsy after realloc */
	stakbsy = (struct blk *)Rcheat(oldbsy);

	return stakbas;				/* addr of 1st usable byte */
}

/* ARGSUSED reqd */
addblok(reqd)			/* called from main at start only */
unsigned reqd;
{
	if (stakbot == 0)			/* called from main, 1st time */
		grostalloc();			/* allocate initial arena */
	/* else won't happen */
}

/*
 * Heap allocation.
 */
char *
alloc(size)
unsigned size;
{
	register char *p = malloc(MAGICSIZE + size);

	if (p == NIL)
		error(nospace);

	*(int *)Rcheat(p) = HPMAGICNUM;
	p += BYTESPERWORD;		/* fiddle ptr for the user */

#ifdef TRACEMEM
	prs("alloc allocated ");
	prn(size);
	prs(" bytes @ ");
	prn((int)p);
	prs("\n");
#endif					/* TRACEMEM */
	return p;
}

/*
 * the shell's private "free" - frees only heap storage.
 * only works on non-null pointers to heap storage
 * (below the data break and stamped with HPMAGICNUM).
 * so it is "okay" for the shell to attempt to free data on its
 * (real) stack, including its command line arguments and environment,
 * or its fake stak.
 * this permits a quick'n'dirty style of programming to "work".
 * the use of sbrk is relatively slow, but effective.
 */
shfree(p)
register char *p;
{
	extern char *sbrk();

	if (p != 0 && p < sbrk(0)) {		/* plausible data seg ptr? */
		register int *magicp = (int *)Rcheat(p) - 1;

#ifdef TRACEMEM
		prs("shfree freeing @ ");
		prn((int)p);
		prs("\n");
#endif						/* TRACEMEM */
		/* ignore attempts to free non-heap storage */
		if (*magicp == HPMAGICNUM) {
			*magicp = 0;		/* erase magic */
			p -= BYTESPERWORD;	/* get original ptr back */
			free(p);
		}
	}
}