/*
	alloca - allocate automatically reclaimed memory

	(mostly) portable public-domain alternative to platform-
	dependent versions.

	created:	1986-01-26	gwyn@arl.army.mil
	last edit:	2012-06-02	D A Gwyn
	SCCS id:	@(#)alloca.c	1.4

	Specification:

		extern void * alloca( size_t size );

	alloca() allocates a contiguous region of storage having at
	least the requested number of bytes (size), properly aligned for
	containing any supported C data type.  It returns a pointer to
	the start of the allocated region.  The allocation will be
	automatically freed after the currently executing function
	terminates.  Behavior is undefined when the requested amount of
	storage cannot be allocated.  (In a perfect world, NULL would be
	returned in that case; however, some existing implementations do
	not guarantee that.)  Behavior is also undefined if alloca() is
	used in a function argument (due to existing implementations).

	alloca() might not operate properly in a multi-threaded
	application (including from asynchronous signal handlers).

	General information:

	This reimplementation of the PWB/Unix library alloca() function,
	which was used to allocate space off the run-time stack so that
	it would be automatically reclaimed upon procedure exit, was
	inspired by discussions with J. Q. Johnson of Cornell.  Later,
	changes were made to accommodate a wider range of environments.

	It should work for any C run-time model that uses a contiguous
	stack (as opposed to a linked list of frames).  There are some
	preprocessor macros that can be predefined when compiling for
	your specific system (see below); however, the defaults should
	be okay in most cases.

	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.

	Note that alloca(0) reclaims storage without allocating any.  It
	may be a good idea to use alloca(0) in your main control loop,
	etc. to force garbage collection.

	Configuration:

	The original behavior of alloca() when it was unable to allocate
	storage was to just run amok and/or abort the program. It would
	be better for it to return NULL, similar to the standard C
	library allocation functions.  This implementation by default
	returns NULL when storage is not allocated; if you predefine
	ALLOCA_ABORT when compiling, it will call abort() when storage
	cannot be allocated.

	As of this writing, the vast majority of C implementations
	maintain run-time procedure call frames as a contiguous array
	commonly called "the stack".  This version of alloca() was
	designed to exploit that model.  Predefine ALLOCA_STACK_DIRECTION
	if you know the direction of stack growth for your system* when a
	function is invoked; otherwise it will be automatically deduced
	at run time.
		*Please do not insert specific platform definitions into
		 this source file.

	ALLOCA_STACK_DIRECTION > 0 => grows toward higher addresses
	ALLOCA_STACK_DIRECTION < 0 => grows toward lower addresses
	ALLOCA_STACK_DIRECTION = 0 => direction of growth unknown

	If you need to port this implementation to a platform where data
	objects in stack frames do not have byte addresses that directly
	reflect the frame nesting sequence (for example, procedure call
	frames may be dynamically allocated from the heap, with links to
	provide the stack-like behavior), then you must predefine
	ALLOCA_LINEARIZE as the name of a helper function* that converts
	the address of a local "auto" object of type int to some
	alternative int-pointer value that does have that property.
	This may not always be possible without changing the C run-time
	system to add stack depth information to the call frame.
		*Please do not insert platform-dependent code into this
		 source file.  Instead, provide the helper function,
		 with external linkage, in a separate file.

	If you want to replace calls to malloc() and/or free() with some
	other function(s) having the same interface, for example PWB's
	xmalloc(), predefine ALLOCA_MALLOC and/or ALLOCA_FREE to the
	desired name(s).

	If you know the storage alignment enforced by malloc() for the
	chunks that it allocates, you should predefine ALLOCA_CHUNK_SIZE
	as that number of bytes.  Otherwise a kludge will be used that
	nearly always works, but is not guaranteed.

	Historical notes:

	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(), so many programmers
	made heavy use of alloca().  (However, it had to be avoided in
	function arguments, because it disrupted the function linkage.)
	Unfortunately, it is hard to implement alloca() on some more
	recent platforms, as indicated above.  Probably the worst issue
	with alloca() is that programmers usually assumed that it would
	always successfully allocate more storage, and it did not report
	when it was unable to perform the allocation.  That could result
	in a trap later on when the program tries to access an
	unavailable storage location.  (C itself has a similar problem
	when there is not enough stack space remaining to complete
	instantiating a function call.)

	As an example, here is the entire PDP-11 Unix implementation:

	/	ptr = alloca(nbytes);
	/ like malloc, but automatic free upon return from calling
	/ function
		.globl	_alloca
	_alloca:
		mov	(sp)+,r1	/ return
		mov	(sp),r0		/ count
		inc	r0
		bic	$1,r0		/ round up
		/ XXX -- should plant SIGSEGV catcher, probe @(r0-sp),
		/ return NULL on trap
		sub	r0,sp		/ take core
		mov	sp,r0
		tst	(r0)+		/ returned pointer value;
		/ may generate a memory fault if there isn't enough
		/ core; otherwise it expands the allocation so there
		/ will be no page fault later upon access
		jmp	(r1)

	Because of these problems, alloca() was not included in the C
	standard, and for improved program portability the standard
	malloc()/free() facility was recommended as a replacement.  The
	original release to the public domain of this C implementation
	of alloca() was meant to aid this transition, and new code
	should not have been written to rely on alloca() in the first
	place.  Unfortunately, the very existence of this "temporary"
	implementation seems to have encouraged many C programmers to
	continue to use alloca() in new code!  For example, a modified
	version of this implementation was included in the GNU Emacs
	distribution.  A search of the World Wide Web shows that it has
	been used, often with slight environmental adaptations, in
	dozens of projects.

	The author has reviewed many of the adaptations, and has tweaked
	his master copy of the source code to incorporate the more
	worthwhile ones.  However, kludges to accommodate *specific*
	platforms have not been included.  Any that are still deemed
	necessary could be reinserted into this version.

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

#ifndef	alloca	/* else probably defined as __builtin_alloca (GCC) */

#ifdef	__STDC__

#include	<stddef.h>		/* NULL, offsetof, size_t */
#include	<stdlib.h>		/* abort, free, malloc */

#if	__STDC_VERSION__ >= 199901
#include	<stdint.h>		/* uintmax_t */
#else	/* C90 */
typedef unsigned long	uintmax_t;	/* may not have long long */
#endif

typedef void *		pointer;	/* generic pointer type */
typedef long double	long_double;

#else	/* !defined(__STDC__) */	/* assume pre-ANSI ("K&R") */

typedef unsigned	size_t;		/* may not have <stdlib.h> */
typedef unsigned long	uintmax_t;	/* may not have <stdint.h> */
typedef char *		pointer;	/* generic pointer type */
typedef double		long_double;	/* may not have long double */

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

#ifndef	NULL	/* (shouldn't need to predefine, but just in case...) */
#define	NULL	0			/* null pointer constant */
#endif

#define	offsetof( t, m )	((size_t)&(((t)*)0)->m)
					/* works on many compilers */

#endif	/* !defined(__STDC__) */

#ifndef	ALLOCA_MALLOC
#define	ALLOCA_MALLOC	malloc
#endif

#ifndef	ALLOCA_FREE
#define	ALLOCA_FREE	free
#endif

/*
	ALLOCA_LINEARIZE is the name of either a function-like macro
	(defined below) or an external function (to which
	ALLOCA_LINEARIZE has been predefined).  It must return
	replacement int-pointer values that 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" int variables whose addresses are passed to
	ALLOCA_LINEARIZE().  This may not always be possible without
	changing the C run-time system to add stack depth information to
	the call frame.
*/

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

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

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

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

#if	ALLOCA_STACK_DIRECTION == 0

/* run-time code to determine stack direction: */

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

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

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

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

#endif	/* ALLOCA_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) be a multiple of the
	widest required alignment (in bytes) for any data type.  This
	can be predefined as ALLOCA_CHUNK_SIZE if you are sure of it;
	otherwise, the following default computation should work okay.
*/

#ifndef	ALLOCA_CHUNK_SIZE

struct al_st
	{
	char		al_cm;
	union	{		/* suggested by Hallvard B. Furuseth */
		uintmax_t	al__m;
		long_double	al__d;
		pointer		al__p;
		void (*		al__f)( /* void */ );
		}	al_um;
	};

#define	ALLOCA_CHUNK_SIZE	offsetof( struct al_st, al_um )

#endif	/* !defined(ALLOCA_CHUNK_SIZE) */

typedef union hdr
	{
	char	align[ALLOCA_CHUNK_SIZE];	/* force padding */
	struct
		{
		union hdr *	next;	/* for chaining headers */
		int *		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.
*/

static header *	last_alloca_header = NULL;
					/* -> last alloca header */

pointer
alloca( size )				/* returns pointer to storage */
	size_t	size;			/* # bytes to allocate */
	{
	auto int	probe;		/* probes stack depth: */
	register int *	depth = ALLOCA_LINEARIZE( &probe );

#if	ALLOCA_STACK_DIRECTION == 0	/* growth direction not known */
	if ( stack_dir == 0 )		/* true only for first entry */
		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_alloca_header; hp != NULL; )
		if (
#if	ALLOCA_STACK_DIRECTION == 0	/* direction wasn't known */
		     stack_dir > 0 && hp->h.deep > depth
		  || stack_dir < 0 && hp->h.deep < depth
#elif	ALLOCA_STACK_DIRECTION > 0
		     hp->h.deep > depth	/* deeper is obsolete */
#else	/* ALLOCA_STACK_DIRECTION < 0 */
		     hp->h.deep < depth	/* deeper is obsolete */
#endif
		   )	{
			register header *	np = hp->h.next;

			/* Recycle trash. */

			ALLOCA_FREE( (pointer)hp );

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

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

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

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

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

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

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

	last_alloca_header = (header *)newa;

	/* User storage begins just after header. */

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

	}

#endif /* !defined(alloca) */