1/*
2	alloca -- (mostly) portable public-domain implementation -- D A Gwyn
3
4	last edit:	86/05/30	rms
5	   include config.h, since on VMS it renames some symbols.
6	   Use xmalloc instead of malloc.
7
8	This implementation of the PWB library alloca() function,
9	which is used to allocate space off the run-time stack so
10	that it is automatically reclaimed upon procedure exit,
11	was inspired by discussions with J. Q. Johnson of Cornell.
12
13	It should work under any C implementation that uses an
14	actual procedure stack (as opposed to a linked list of
15	frames).  There are some preprocessor constants that can
16	be defined when compiling for your specific system, for
17	improved efficiency; however, the defaults should be okay.
18
19	The general concept of this implementation is to keep
20	track of all alloca()-allocated blocks, and reclaim any
21	that are found to be deeper in the stack than the current
22	invocation.  This heuristic does not reclaim storage as
23	soon as it becomes invalid, but it will do so eventually.
24
25	As a special case, alloca(0) reclaims storage without
26	allocating any.  It is a good idea to use alloca(0) in
27	your main control loop, etc. to force garbage collection.
28*/
29#ifndef lint
30static char	SCCSid[] = "@(#)alloca.c	1.1";	/* for the "what" utility */
31#endif
32
33#ifdef emacs
34#include "config.h"
35#ifdef static
36/* actually, only want this if static is defined as ""
37   -- this is for usg, in which emacs must undefine static
38   in order to make unexec workable
39   */
40#ifndef STACK_DIRECTION
41you
42lose
43-- must know STACK_DIRECTION at compile-time
44#endif /* STACK_DIRECTION undefined */
45#endif /* static */
46#endif /* emacs */
47
48#ifndef alloca      /* If compiling with GCC, this file's not needed.  */
49
50#ifdef __STDC__
51typedef void	*pointer;		/* generic pointer type */
52#else
53typedef char	*pointer;		/* generic pointer type */
54#endif
55
56#define	NULL	0			/* null pointer constant */
57
58extern void	free();
59extern pointer	xmalloc();
60
61/*
62	Define STACK_DIRECTION if you know the direction of stack
63	growth for your system; otherwise it will be automatically
64	deduced at run-time.
65
66	STACK_DIRECTION > 0 => grows toward higher addresses
67	STACK_DIRECTION < 0 => grows toward lower addresses
68	STACK_DIRECTION = 0 => direction of growth unknown
69*/
70
71#ifndef STACK_DIRECTION
72#define	STACK_DIRECTION	0		/* direction unknown */
73#endif
74
75#if STACK_DIRECTION != 0
76
77#define	STACK_DIR	STACK_DIRECTION	/* known at compile-time */
78
79#else	/* STACK_DIRECTION == 0; need run-time code */
80
81static int	stack_dir;		/* 1 or -1 once known */
82#define	STACK_DIR	stack_dir
83
84static void
85find_stack_direction (/* void */)
86{
87  static char	*addr = NULL;	/* address of first
88				   `dummy', once known */
89  auto char	dummy;		/* to get stack address */
90
91  if (addr == NULL)
92    {				/* initial entry */
93      addr = &dummy;
94
95      find_stack_direction ();	/* recurse once */
96    }
97  else				/* second entry */
98    if (&dummy > addr)
99      stack_dir = 1;		/* stack grew upward */
100    else
101      stack_dir = -1;		/* stack grew downward */
102}
103
104#endif	/* STACK_DIRECTION == 0 */
105
106/*
107	An "alloca header" is used to:
108	(a) chain together all alloca()ed blocks;
109	(b) keep track of stack depth.
110
111	It is very important that sizeof(header) agree with malloc()
112	alignment chunk size.  The following default should work okay.
113*/
114
115#ifndef	ALIGN_SIZE
116#define	ALIGN_SIZE	sizeof(double)
117#endif
118
119typedef union hdr
120{
121  char	align[ALIGN_SIZE];	/* to force sizeof(header) */
122  struct
123    {
124      union hdr *next;		/* for chaining headers */
125      char *deep;		/* for stack depth measure */
126    } h;
127} header;
128
129/*
130	alloca( size ) returns a pointer to at least `size' bytes of
131	storage which will be automatically reclaimed upon exit from
132	the procedure that called alloca().  Originally, this space
133	was supposed to be taken from the current stack frame of the
134	caller, but that method cannot be made to work for some
135	implementations of C, for example under Gould's UTX/32.
136*/
137
138static header *last_alloca_header = NULL; /* -> last alloca header */
139
140pointer
141alloca (size)			/* returns pointer to storage */
142     unsigned	size;		/* # bytes to allocate */
143{
144  auto char	probe;		/* probes stack depth: */
145  register char	*depth = &probe;
146
147#if STACK_DIRECTION == 0
148  if (STACK_DIR == 0)		/* unknown growth direction */
149    find_stack_direction ();
150#endif
151
152				/* Reclaim garbage, defined as all alloca()ed storage that
153				   was allocated from deeper in the stack than currently. */
154
155  {
156    register header	*hp;	/* traverses linked list */
157
158    for (hp = last_alloca_header; hp != NULL;)
159      if ((STACK_DIR > 0 && hp->h.deep > depth)
160	  || (STACK_DIR < 0 && hp->h.deep < depth))
161	{
162	  register header	*np = hp->h.next;
163
164	  free ((pointer) hp);	/* collect garbage */
165
166	  hp = np;		/* -> next header */
167	}
168      else
169	break;			/* rest are not deeper */
170
171    last_alloca_header = hp;	/* -> last valid storage */
172  }
173
174  if (size == 0)
175    return NULL;		/* no allocation required */
176
177  /* Allocate combined header + user data storage. */
178
179  {
180    register pointer	new = xmalloc (sizeof (header) + size);
181
182    /* address of header */
183
184    ((header *)new)->h.next = last_alloca_header;
185    ((header *)new)->h.deep = depth;
186
187    last_alloca_header = (header *)new;
188
189    /* User storage begins just after header. */
190
191    return (pointer)((char *)new + sizeof(header));
192  }
193}
194
195#endif /* no alloca */
196