/*
 * Note to mg porters: this is included on the off chance you don't have an
 * alloca, and want to use the regexp code. I seriously recommend not using
 * it if you can avoid it.
 */

/*
 * alloca -- (mostly) portable public-domain implementation -- D A Gwyn
 * 
 * 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 defined 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.
 */
#include "regexp.h"
#ifdef	REGEXP

#include "def.h"		/* Get me lotsa defines */

#ifdef ANSI
#include <stdlib.h>
#endif

typedef VOID   *pointer;	/* generic pointer type */

/*
 * Define 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 undefined => direction of
 * growth unknown
 */


#ifdef STACK_DIRECTION

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

#else				/* STACK_DIRECTION undefined -> need to find
				 * it at compile time */

static int      stack_dir;	/* 1 or -1 once known */
#define	STACK_DIR	stack_dir

static          VOID
find_stack_direction PROTO(( VOID ))
{
	static char    *addr = NULL;	/* address of first `dummy', once
					 * known */
	auto char       dummy;	/* to get stack address */

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

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

#endif				/* STACK_DIRECTION */

/*
 * 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.
 */

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

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

#ifndef STACK_DIRECTION
	if (STACK_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_alloca_header; hp != NULL;)
			if (STACK_DIR > 0 && hp->h.deep > depth
			    || STACK_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_alloca_header = hp;	/* -> last valid storage */
	}

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

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

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

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

		last_alloca_header = (header *) new;

		/* User storage begins just after header. */

		return (pointer) ((char *) new + sizeof(header));
	}
}
#else
#include "nullfile.h"
#endif