/*
	alloca - allocate automatically reclaimed memory
		(Mostly) portable public-domain implementation

	created:	1986		D A Gwyn
	last edit:	2012-06-01	D A Gwyn	reconstructed & tweaked

	This implementation of the PWB library alloca() function,
	which is used to allocate space off the run-time stack so
	that it is automatically reclaimed upon procedure exit, 
	was inspired by discussions with J. Q. Johnson of Cornell.

	It should work under any C implementation that uses an
	actual procedure stack (as opposed to a linked list of
	frames).  There are some preprocessor constants that can
	be predefined when compiling for your specific system, for
	improved efficiency; however, the defaults should be okay.

	The general concept of this implementation is to keep
	track of all alloca()-allocated blocks, and reclaim any
	that are found to be deeper in the stack than the current
	invocation.  This heuristic does not reclaim storage as
	soon as it becomes invalid, but it will do so eventually.

	As a special case, alloca(0) reclaims storage without
	allocating any.  It is a good idea to use alloca(0) in
	your main control loop, etc. to force garbage collection.

	The original behavior of alloca() when it was unable to
	allocate storage was to just run amok or abort the program.
	I much prefer that it return NULL, similar to the standard
	C library allocation functions; to obtain this behavior,
	you must predefine RETURN_NULL_ON_FAILURE when compiling.

	Predefine STACK_DIRECTION if you know the direction of stack
	growth for your system; otherwise it will be automatically
	deduced at run-time.
		STACK_DIRECTION > 0 => grows toward higher addresses
		STACK_DIRECTION < 0 => grows toward lower addresses
		STACK_DIRECTION = 0 => direction of growth unknown

	If you know the byte alignment enforced by malloc() for
	the chunks that it allocates, you should predefine
	ALIGN_SIZE as that integer constant.

	If you need to port this implementation to a platform where
	data objects in stack frames do not have a byte addresses
	that directly reflect the frame nesting sequence, then you
	must predefine LINEARIZE as the name of a helper function
	that converts the address of a local "auto" object to some
	pointer value that does have that property.  Note that
	there can be C implementations on segmented architectures
	where pointer comparison (other than for equality) between
	different segments is not meaningful; in that case, there
	is no simple solution, other than to avoid using alloca().

	This code has not been verified to operate properly in a
	multithreaded environment.

	Author's note:  alloca() was originally implemented by
	simply adjusting the run-time stack pointer and returning
	a pointer to the new portion of the stack.  This was faster
	and somewhat more convenient than using malloc()/free(), and
	many programmers made heavy use of alloca().  Unfortunately,
	it is hard to implement alloca() correctly on some platforms,
	for reasons I won't explain here (but you might find it
	instructive to puzzle out ways in which there could be a
	problem).  Probably the worst issue with alloca() is that it
	was assumed to always successfully allocate more storage,
	and it did not report when it was unable to.  The original
	release of this implementation was meant as a transitional
	measure only; you should not be writing new code that relies
	on alloca(), and you should refit old code to use malloc()/
	free() instead as you get the chance.  Unfortunately, the
	very existence of this "temporary" implementation encouraged
	many C programmers to continue to use alloca() in new code!
	For example, it was included in the GNU Emacs distribution.
	A search of the World Wide Web shows its use, usually with
	a few slight environmental adaptations, in dozens of projects.

	I have reviewed many of the adaptations, and have tweaked
	my master copy of the source code to incorporate the more
	worthwhile ones.  However, I did not pick up modifications
	that J. Otto Tennant had made to provide alloca() on Cray
	platforms that use linked activation-record segments instead
	of contiguous stack frames; that is because it incorporated
	a large amount of highly platform-specific code.  I did adopt
	part of the Cray modifications, in the form of LINEARIZE().

	The 1999 revision of the C standard introduced support for
	variable-length arrays (VLAs), which could be used much the
	same as alloca() had been used.  However, compilers were slow
	to implement the VLA facility (and some other C99 features).
	Therefore, this implementation may still be of use.
*/

#if	! (defined(lint) || defined(_lint_) || defined(LINT))
static char	SCCSid[] = "@(#)alloca.c\t1.3"; /* for the "what" utility */
#endif

#ifndef	alloca	/* else probably defined as _builtin_alloca */

#ifdef	__STDC__

#include	<stdlib.h>

typedef void *	pointer;		/* generic pointer type (Std C) */

#else	/* !defined(__STDC__) */	/* assume pre-ANSI; no prototypes */

extern void		abort( /* void */ );
extern void		free( /* pointer */ );
extern pointer	malloc( /* size_t */ );

typedef char *	pointer;		/* generic pointer type (K&R C) */

#define	NULL	0			/* null pointer constant */

#endif	/* !defined(__STDC__) */

/*
	LINEARIZE is the name of either a function-like macro or an
	actual function (to which LINEARIZE has been predefined).
	It must return pointer values with the property that they
	can be directly compared for inequality resulting in an
	ordering that consistently (in one direction or the other)
	reflects the actual stack hierarchy for the local "auto"
	variables whose arguments are passed to LINEARIZE().

	On some platforms, such a mapping may be infeasible to
	implement.  In that case, you should avoid using alloca().
*/

#ifdef	LINEARIZE			/* name of a helper function */
extern char *	LINEARIZE( /* char* */ );
#else	/* don't need help: cross-frame comparison works */
#define	LINEARIZE( p )	(p)
#define
#endif

/*
	Predefine STACK_DIRECTION if you know the direction of stack
	growth for your system; otherwise it will be automatically
	deduced at run-time.

	STACK_DIRECTION > 0 => grows toward higher addresses
	STACK_DIRECTION < 0 => grows toward lower addresses
	STACK_DIRECTION = 0 => direction of growth unknown
*/

#ifndef	STACK_DIRECTION
#define	STACK_DIRECTION	0		/* initially unknown */
#endif

#if	STACK_DIRECTION != 0

#define	STK_DIR	STACK_DIRECTION	/* known at compile-time */

#else	/* STACK_DIRECTION == 0; need run-time probe */

static int	stack_dir = 0;			/* 1 or -1 once known */
#define	STK_DIR	stack_dir

static void
find_stack_direction( /* void */ )
	{
	static char *	addr = (char *)NULL;	/* address for
								   first "dummy",
								   once known */
	auto char		dummy;		/* to get stack address */

	if ( addr == NULL )
		{					/* initial entry */
      	addr = LINEARIZE( &dummy );

		find_stack_direction();		/* recurse once */
		}
	else						/* second entry */
		if ( LINEARIZE( &dummy ) > addr )	/* crucial test */
			stack_dir = 1;		/* stack grew upward */
		else
			stack_dir = -1;		/* stack grew downward */
	}

#endif	/* STACK_DIRECTION == 0 */

/*
	An "alloca header" is used to:
	(a) chain together all alloca()ed blocks;
	(b) keep track of stack depth.

	It is very important that sizeof(header) agree with malloc()
	alignment chunk size.  The following default should work okay.
*/

#ifndef	ALIGN_SIZE
#define	ALIGN_SIZE	sizeof(double)
#endif

typedef union hdr
	{
	char		align[ALIGN_SIZE];	/* to force sizeof(header) */
	struct
		{
		union hdr *	next;			/* for chaining headers */
		char *	deep;			/* for stack depth measure */
		}	h;
	}	header;

/*
	alloca( size ) returns a pointer to at least "size" bytes of
	storage which will be automatically reclaimed upon exit from
	the procedure that called alloca().  Originally, this space
	was supposed to be taken from the current stack frame of the
	caller, but that method cannot be made to work for some
	implementations of C, for example under Gould's UTX/32.
*/

pointer
alloca( size )				/* returns pointer to storage */
	unsigned		size;			/* # bytes to allocate */
	{
	static header *	last = NULL;	/* -> last alloca header */
	auto char		probe;		/* probes stack depth: */
	register char *	depth = &probe;

#if	STACK_DIRECTION == 0
	if ( STK_DIR == 0 )			/* unknown growth direction */
		find_stack_direction();
#endif

	/* Reclaim garbage, defined as all alloca()ed storage that
	   was allocated from deeper in the stack than currently. */

		{
		register header *	hp;		/* traverses linked list */

		for ( hp = last; hp != NULL; )
			if ( STK_DIR > 0 && hp->h.deep > depth
			  || STK_DIR < 0 && hp->h.deep < depth
			   )	{
				register header *	np = hp->h.next;

				free( (pointer)hp );	/* collect garbage */

				hp = np;		/* -> next header */
				}
			else
				break;		/* rest are not deeper */

		last = hp;				/* -> last valid storage */
		}

	if ( size == 0 )
		return (pointer)NULL;		/* no allocation required */

	/* Allocate combined header + user data storage. */

		{
		register pointer	newa = malloc( sizeof(header) + size );
							/* address of header */

		if ( newa == NULL )
#ifdef	RETURN_NULL_ON_FAILURE
			return (pointer)NULL;
#else
			abort();			/* abort() is traditional */
#endif

		((header *)newa)->h.next = last;
		((header *)newa)->h.deep = depth;

		last = (header *)newa;

		/* User storage begins just after header. */

		return (pointer)((char *)newa + sizeof(header));
		}
	}

#endif /* !defined(alloca) */